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

Question

我有一个包裹在边缘的二维地图。因此，如果您离开右边缘，您将重新出现在地图的左侧。其他三个边缘也是如此。

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

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

Answer 1

数据结构不必改变，但搜索过程会。用 [0, w) * [0, h) 中的坐标 (x, y) 表示每个点，其中 w 是地图的宽度，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 中的最近邻居。）

Answer 2

Jitamaro 建议但没有解释基于“2x 大小”四叉树的方法。这是一个合理的建议，除了四叉树使用的节点数量是两个节点的四倍之外，我将在下面解释，然后再试探性地提出一种替代方法。

假设每个 (x,y) 坐标具有-.5 < x <= .5并且-.5 < y <= .5并且只要j, k是整数，点 (x+j,y+k) 与点 (x,y) 相同。让四叉树 T 覆盖坐标在 范围内的点-1 < x,y <= 1。每次将 (x,y) 处的项目添加到 T 时， where -.5 < x,y <= .5， let x' = {x-1if x>0elsex+1}和y' = {y-1if y>0else y+1}。还要在 (x,y')、(x',y') 和 (x',y) 处添加项目。[当您稍后删除点时，再次计算 (x', y') 等并删除它们。] 很容易看出最近点查找将正常工作，只要(-.5,.5]适当调整区间外的任何查找坐标。

如果四倍数量的节点是一个交易破坏者，请注意，如果上述坐标用于高于 level 的子树中k=3，并且相对坐标存储在 level 之下k，则应该可以在 level 之下维护子树的单个副本k。也就是说，级别的每个子树k将有四个父级。（我没有充分考虑这一点，不知道这是否完全有效；如果我发现它没有，我会编辑答案。）

Answer 3

四叉树是具有 4 个叶子的 KD 树。四叉树无助于包装，因为它的数据结构本身就是一个包装。您只需要使用结构的 2 倍大小的四叉树。