我应该使用什么数据结构来索引地理坐标？

Question

我有一组具有纬度和经度坐标的对象，我需要能够将另一组对象与最近的项目相匹配。简单的最近邻的东西。我最好的想法是将经纬度/lng坐标转换为3D坐标，然后存储在K-d树或八叉树中以供以后查找。它应该工作，并且对于所有的实际目的都是足够好的(参见：kdtree for geospatial point search)，但这方面的一些东西让人感觉不对劲。我认为这只是3D空间中的2D流形。

有没有更合适的结构可以使用，或者我只是想得太多了？

Answer 1

甚至维基百科都说：

k-d树(k-

树的缩写)是一种空间分区数据结构，用于在k维空间中组织点。

所以，继续使用你的2D点(不要将它们投影到3D，或者类似的东西)。

将它们插入到树中，然后在对数时间内查询树-就这样，一切都很顺利！