[Solved]: Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

Problem Detail: 

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 latC, lonC.

• The points are mostly concentrated at places where humans go often.
• Some points have the exact same latitude and longitude.
• d is 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.

Asked By : Nicolas Raoul

Answered By : GEL

Geographic information systems use spherical triangular quadtrees to solve this problem. They are analogous to a quadtree, but defined over a sphere using triangular patches.

There are different variants with different bells and whistles, but you can refer to Quaternary Triangular Meshes (Dutton. "Encoding and Handling Geospatial Data with Hierarchical Triangular Meshes"), Sphere Quadtrees (Fekete. "Rendering and managing spherical data with sphere quadtree") and HTMs (Kunszt. "The Hierarchical Triangular Mesh") as approaches you can extrapolate from.

The basic idea is that you partition the sphere into coarse triangular patches, then subdivide those patches into smaller triangular patches recursively as needed. You can then perform basic queries like you would on a quadtree.

See Chen. "An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM" for a survey of different techniques, and related problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51616

3.2K people like this

 Download Related Notes/Documents