二叉空间分割数据结构用于环形的2D空间（Donut 2D Space）。

Question

我有一个二维地图，边缘是环形的。因此，如果你走到右边缘，你会出现在地图的左侧。其他三个边缘也是如此。

这对于我使用的KD树来查找点范围内的元素是一个问题。通常，您会检查超球体是否与超平面碰撞，以确定是否应该继续搜索树的另一侧，但这种检查在环形边缘上不起作用。

有没有办法修改KD树以适用于甜甜圈型的2D空间？

- Kasper Holdum

Answer 1

数据结构不需要改变，但是搜索过程需要改变。将每个点表示为坐标(x,y)，其中w是地图的宽度，h是高度，在[0，w）* [0，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

这里的g是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树的最坏情况要比实践更糟糕 - 在n个点中识别2D最近邻的时间复杂度为O(n^1/2）。）

- Per

Answer 2

Jitamaro提出了一种基于“2倍大小”四叉树的方法，但并没有解释。这是一个合理的建议，除了四叉树使用的节点数量增加了四倍而不是两倍，如下所述，然后试探性地提出另一种替代方法。

假设每个（x，y）坐标具有-.5<x<=.5和-.5<y<=.5，并且每当j，k为整数时，点（x + j，y + k）与点（x，y）相同。让四叉树T覆盖坐标范围在-1<x，y<=1之间的点。每次您将项目添加到T的（x，y）位置，其中-.5<x，y<=.5，让x'={x-1如果x>0则x+1}，y'={y-1如果y>0则y+1}。还在（x，y'），（x'，y'）和（x'，y）处添加项目。[稍后删除点时，请再次计算（x'，y'）等并将它们删除。]很容易看出，最近点查找将正常工作，只要任何查找坐标在区间（-.5，.5] 之外的都得到适当调整。

如果四倍的节点数量是一个难以接受的问题，请注意，如果在k = 3级别以上的子树中使用上述坐标，并且在k级别以下存储相对坐标，则应该能够维护k级别以下子树的单个副本。也就是说，每个k级别的子树将有四个父级。（我还没有想过这是否完全有效；如果发现不行，将编辑答案。）

- James Waldby - jwpat7

---

我假设四叉树具有与kd树相同的操作（和运行时间）（查找最近邻居/查找范围内的节点）？ - Kasper Holdum

@jwpat7：我有一个“2倍大小”四叉树的想法，因为我可以从分形维度看到四叉树。例如，Z曲线或希尔伯特曲线是解释四叉树的一种方式。 - Micromega

Answer 3

一个四叉树是一棵带有4个叶子节点的KD树。四叉树不需要帮助进行包裹，因为它的数据结构本身就是一个包裹。你只需要使用一个比你的结构体大两倍的四叉树即可。

- Micromega

---

这句话与包装有什么关系？ - Kasper Holdum