CODEWITHSUNDEEP
c++cdelphigis
Leo
Leo

Reputation: 1957

Calculation of accumulation area

I'm looking for a GIS/Geometric algorithm:

I have 1000 points randomly distributed in a large area(such as a city), How can I find out all the small areas which have more than 15 points? Like this picture below:

enter image description here

Each point has its own latitude and longitude coordinates. The small area less than 200m x 200m.

Upvotes: 16

Views: 346

Answers (2)

Thorsten Engler
Thorsten Engler

Reputation: 2361

Not sure what your performance requirements are. But a naive implementation would be, for each point, to sum up the inverse of the distance to all other points:

for i := 0 to 999 do
  for j := 0 to 999 do
    if i<>j then
      Point[i].Score := Point[i].Score + ( 1 / Distance(Point[i], Point[j]) );

The points near the center of each accumulation area will have the highest score.

Upvotes: 0

Arnaud Bouchez
Arnaud Bouchez

Reputation: 43033

You should take a look at RTREE structures. See http://en.wikipedia.org/wiki/R-tree

You've such algorithms implemented e.g. in the SQlite3 engine. See http://www.sqlite.org/rtree.html

Our Open Source version already includes the RTREE extension for Delphi 6 up to XE, compiled by default since rev. 1.8.

Upvotes: 10

Related Questions