1
$\begingroup$

I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree, but as far as I can tell, quadtrees and k-d trees are confined to working in Euclidean space. How can I efficiently do a nearest-neighbor lookup in spherical space?

One solution I've considered is projection into 3d space and then using an octree, but I'd prefer not to do that if a space-partitioning tree (or alternative algorithm) that works with spherical coordinates directly exists.

$\endgroup$
1
  • $\begingroup$ Picking a point and calling it the north pole, you can map the complement of that point to the plane using, for example, the stereographic projection. The same use that you would do for those data structures on the plane, you can pull back to the sphere using the inverse of the projection. Either one chooses the north pole to not be one the points or the computations for that point could be done separately. $\endgroup$
    – plop
    Oct 20 '20 at 23:03
1
$\begingroup$

First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate.

You've already worked out that if all you need is nearest neighbour on points, then using 3D distance as a proxy for great circle distance is probably the most efficient approach. To be honest, this is probably the best solution for your specific problem, but not if you had to do distance queries involving non-point geometry (e.g. "find me all lines within 200km of this point").

The usual practice for spatial indexing in GIS is to use some variant on a bounding volume hierarchy.

In Cartesian space, that would mean an R-tree, and in geographic space, you would use circles of a sphere or ellipsoid as the bounding volume shape. In the case of a binary tree index, you can use a great circle as the splitting criteria for each node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.