What approaches would be best for space partitioning on a sphere? I'm working with a visualizing data on the surface of the earth.
Some operations that would be relevant
- Find the closest stored point to a given point
- See if a the given point is within a region
- Adding and removing points and regions
Currently, some of the approaches that I've thought of taking are:
- Start with a octahedron and do triangle tessellation, 4 triangles to each parent triangle. I'm not sure how to approach indexing nodes from latitude, longitude. The pros would be that the partitions would be basically equal area.
- Quadtree, with the first level separated by north/south hemisphere (positive/negative y) and then a normal quadtree based on the x, z coordinates. This might be a bit easier to index, but leaves might not be balanced well.
Are there any other common approaches that you guys know of or can think of?