I have many points scattered on a sphere surface. I need to find which of them are inside an arbitrary circle drawn on the surface.
This looks like it'd require some sort of space partitioning but I'm not sure what's the best way to partition. My current idea is to do equirectangular un-projection of the points and then use a standard quadtree on them.
Any suggestions for a better approach?
Use stereographic projection to map the points from the sphere's surface to an infinite plane. Then construct an ordinary Delaunay Triangulation on these points, before mapping the edges back to the original points on your sphere surface. You'll now have a Delaunay Triangulation of the sphere surface points.
Now insert your points into a standard KD-tree or other 3D+ space partitioning data structure, and query for the nearest point to the center of your circle on the surface. From that point, run a breadth-first search on the graph constructed earlier and test if each point falls within your circle as already explained in the other answers / comments. Only expand the frontier from nodes within the circle.