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.