I'm interested in build a prototype that needs this sort of thing:

  • Point A (xa, ya) with a radius of 500 meters.
  • Point B (xb, yb) with a radius of 700 meters.
  • Point C (xc, yc) with a radius of 1200 meters.
  • Point D (xd, yd) with a radius of 200 meters.
  • Person 123 is in some certain point.

Question: which points 123 is in? For example, the person is both inside A, B and D areas, but not on C.

All points are geographic coordinates, i.e. lat/long. I want to understand what are the best algorithms and strategies to implement a good index. My current idea (not implemented yet) is:

The hole map is divided in quadrants, small as (for example) 50~100 > meters. When a point is marked, all quadrants inside their area will > be marked as well. Then, when I search using "Person 123", I'll just > find its quadrant and retrieve all points marked into it.

Basically I'll build a huge prefix tree based on geohashes of all points (+10k points). Problem is, for a single point, there will be numerous entries inside the Tree (though it would be better for searching, I think). Note I lack the formal understanding of spatial indexes.

  • When you say "point," do you really mean "area" or "quadrant?" I don't understand how a "point" can cover an area of 500 meters unless it's a really fat point. – Robert Harvey Dec 17 '13 at 17:23
  • 2
    @RobertHarvey I think he wants to do collision testing. What you really want is to use a quad-tree for collision detection, this is a well-known high performance approach, there's a variety of blog articles you can find on how to do it and here's an SO Q about it with good info stackoverflow.com/questions/9762476/… - it sounds like your description of your planned approach (quadrants) is similar conceptually to how quadtrees do collision detection. I'd write an answer but honestly I don't remember the details of it super well. – Jimmy Hoffa Dec 17 '13 at 17:25
  • @RobertHarvey, it's a point with a radius of 500 meters. Sorry, I wasn't very clear in that point =S – Lucas Sampaio Dec 17 '13 at 17:27
  • Can you provide more details about the data & how you want to search? Are we talking 10 points, or 100,000? Is it all in memory or in a database? – GrandmasterB Dec 17 '13 at 17:48
  • @GrandmasterB, +10k points. It's open if it'll be in memory or db-backed, I really can't decide anything right now. – Lucas Sampaio Dec 17 '13 at 18:00

Although the Quadtree suggested in the comments is the canonical solution, you might be able to get away with the design you propose yourself, except that I would store the points in a Hashtable-based Dictionary. The dictionary is nice as it only costs space proportional with the amount of Points Of Interest. You dont need to reseve memory for the empty sahara desert.

You simply define a numbering scheme for your quadrants, and the quadrant number is then the key for the hashtable. For each quadrant you store a list of POI's in the hashtable. Each of your points of interest will get an entry in the poi list in each of the quadrants it touches.

If you reduce the resolution of your grid a bit, that will reduce the memory use even more, but you will need to iterate through more points, especcially if they are close together. I think your current grid is too dense as each poi touches about a 100 quadrants. i would strive for a figure below 10, on average.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.