I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude.
I want to quickly get all points within a distance
d of a particular sphere point
- The points are mostly concentrated at places where humans go often.
- Some points have the exact same latitude and longitude.
dis orders of magnitude smaller than the Earth's radius
r, so using arc instead of distance is totally OK
- Getting a few extra points is OK (even a rectangle area instead of a circle area is better than nothing). Missing points is not OK
- No persistence needed.
What data structure would give these points quickly consistently, even if the set is large?
What I tried:
- Simple list: Checking all points is too slow.
- Quadtree on latitude, longitude: Does not find points around the poles.