c# - Donut 二维空间的二进制空间分区数据结构

Question

我有一个 2D map ，它在边缘处环绕。因此，如果您离开右边缘，您将重新出现在 map 的左侧。其他三个边也是如此。

这是我用来在点范围内查找元素的 KDTree 的可继承问题。通常，您会检查超球体是否与超平面碰撞，以查看是否应该继续搜索树的另一侧，但此检查不适用于环绕边。

有什么方法可以修改 KD 树以使用 donut 2D 空间吗？

Answer 1

数据结构不必改变，但搜索过程需要改变。用[0, w) * [0, h)中的坐标(x, y)表示每个点，其中w是 map 的宽度，h是高度，*表示笛卡尔积。将这些点存储在普通 KD 树中。

搜索 KD 树的基本原语是，给定一个点 (x, y) 和一个矩形 [a, b] * [c, d]，确定点到矩形的距离(平方)。通常这是 g(x, a, b)² + g(y, c, d)²，其中

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)² + g(y, c, d, h)²。我希望此变体的运行时间具有可比性。 (我会重做循环，但常规 KD 树的最坏情况比大部分时间的实践要糟糕得多 - O(n^1/2) 用于识别 n 中 2D 中的最近邻居点。)