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

Question

我有一个包裹在边缘的2D地图.因此,如果您偏离右边缘,您将重新出现在地图的左侧.与其他三个边缘一样.

对于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

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