简短版本：给定两个k-d树，它们包含相似但不完全相同的2d点集，并且它们可能没有相同的根，您是否可以利用它们都是树的事实，用比逐个查找节点更少的查找步骤将一个树中的点匹配到另一个树中最近的点？
我们有一个公共的API，可以将几何图形（WKT格式的拉长坐标，可以是点或多边形）发送到客户端应用程序，它们进行修改并将修改后的WKT发送回我们最近我们遇到了一个问题，一个客户端应用程序在保存之前投影和取消投影所有点，这会导致所有点由于浮点数学精度限制而稍微偏移，即使对于用户不打算移动的点也是如此客户机应该做的是保留未修改的原始值的副本，并且只更新用户实际移动的点。
显然这需要在客户端应用程序中修复但我想知道将来什么时候会发生这样的事情，这样我们就可以“抓住”正在做这件事的客户这只能是一个启发式的方法，但是如果我们看到90%的点只是移动了一小部分，我们可以记录一个警告如果点的移动量超过一个很小的数量，我们可以假设用户打算移动点。
一个复杂的因素是，客户端可以按照不同于我们发送它的顺序将点或多边形顶点序列化返回给我们-但是它可能仍然代表相同的形状并且是有效的此外，用户可能会分割多边形，点或顶点可能会被删除或添加到数据中。如果只是多边形，我们可以旋转顶点列表，直到它们“匹配”，但考虑到多边形可能被编辑，而且我们也有同样多的数据只是点，而不是多边形，我认为这是一个简化的假设，只是将所有数据作为点集进行验证。
我提出的一种算法是将其中一组点放入k-d树中进行快速查找，然后查找第二组中每个点的最近邻。但是我可以把它们都放到k-d树中，我想知道是否有一个快速算法来比较两个k-d树？
最佳答案
不管你的距离公差是用来声明两个点是相同的（称为d），对于第一个集合中的给定点（x，y），你可以散列并存储（x/d，y/d）的整数部分，并在散列表中存储指向该点的指针，然后对于第二个集合中的每个点（x，y），你可以散列（x/d，y/d）与所有邻域（每个值加0或+/-1），如果从第一个集合中找到散列点，则将第二个集合中的点与从第一个集合中找到的所有点进行比较，以查看第一个集合中的某个点是否在第二个集合中特定点的距离d内。如果两组点彼此之间的距离d内没有点对，则这应该在基本上是线性时间内运行。
关于c# - 将两个k-d树(2D点)相互比较的快速算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25025840/