我有一个 2D map ，它在边缘处环绕。因此，如果您离开右边缘，您将重新出现在 map 的左侧。其他三个边也是如此。
这是我用来在点范围内查找元素的 KDTree 的可继承问题。通常，您会检查超球体是否与超平面碰撞，以查看是否应该继续搜索树的另一侧，但此检查不适用于环绕边。
有什么方法可以修改 KD 树以使用 donut 2D 空间吗？
最佳答案
数据结构不必改变，但搜索过程需要改变。用[0, w) * [0, h)中的坐标(x, y)表示每个点，其中w是 map 的宽度，h是高度，*表示笛卡尔积。将这些点存储在普通 KD 树中。
搜索 KD 树的基本原语是，给定一个点 (x, y) 和一个矩形 [a, b] * [c, d]，确定点到矩形的距离(平方)。通常这是 g(x, a, b)2 + g(y, c, d)2，其中
g(z, e, f) = e - z if z < e
0 if e <= z <= f
z - f if f < z
是 z 到 [e, f] 的一维距离。在环形空间中，我们稍微修改 g 以解决环绕问题。
g(z, e, f, v) = min(e - z, (z + v) - f) if z < e
0 if e < z < f
min(z - f, (e + v) - z) if f < z.
距离的平方是 g(x, a, b, w)2 + g(y, c, d, h)2。我希望此变体的运行时间具有可比性。 (我会重做循环，但常规 KD 树的最坏情况比大部分时间的实践要糟糕得多 - O(n1/2) 用于识别 n 中 2D 中的最近邻居点。)
关于c# - Donut 二维空间的二进制空间分区数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8024552/