甜甜圈二维空间的二进制空间划分数据结构

本文关键字：空间 二进制 划分 数据结构 二维 甜甜圈 | 更新日期: 2023-09-27 18:13:41

我有一个2D地图，在边缘处包裹。所以如果你从右边移开，你会重新出现在地图的左边。其他三条边也一样。

这是可继承的KDTree的问题，我用它来查找点范围内的元素。通常情况下，你会检查超球体是否与超平面碰撞，看看是否应该继续搜索树的另一边，但这种检查不适用于包裹边。

是否有办法修改KD树与甜甜圈二维空间的工作?

甜甜圈二维空间的二进制空间划分数据结构

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

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

为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树的最坏情况比大多数情况下的实践要糟糕得多——在n个点中识别2D中最近的邻居为O(n1/2)

Jitamaro建议但没有解释一种基于"2倍大小"四叉树的方法。这是一个合理的建议，除了四叉树使用的节点数量是原来的四倍而不是两个，我将在下面解释这一点，然后试试性地提出另一种方法。

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

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

四叉树是有4个叶子的kd树。四叉树对换行没有帮助，因为它的数据结构本身就是换行。你只需要使用结构的2倍大小的四叉树。

相关文章：