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

我有一个包裹在边缘的2D地图。所以如果你离开右边缘，你会重新出现在地图的左侧。同样与三个其他边缘。二进制空间对甜甜圈二维空间的分区数据结构

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

有什么方法可以修改KD树来与甜甜圈2D空间一起工作吗？

来源

2011-11-06 Kasper Holdum

四叉树是一棵有4片叶子的KD树。四叉树无助于换行，因为它的数据结构本身就是一个换行。你只需要使用你的结构的四叉树2x大小。

来源

2011-11-06 01:13:14 Bytemain

这是如何帮助包装？ –

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>0其他x+1}和y' = {y-1如果y>0其他y+1}则设x' = {x-1。还要在（x，y'），（x'，y'）和（x'，y）处添加项目。 [稍后删除点时，再次计算（x'，y'）等并删除它们。]只要在区间(-.5,.5]之外的任何查找坐标得到适当调整，很容易看到最近点查找将正常工作。

如果节点的四倍数是交易断路器，请注意，如果在上述子树中使用上述坐标，说明水平为k=3，并且相对坐标存储在水平k以下，则应该可以保持单个k以下的子树副本。也就是说，级别为k的每个子树都有四个父母。（我没有想过这足以知道这是否完全有效;如果我发现它不会，将编辑答案）。

来源

2011-11-06 05:46:20

我假设四叉树与kdtree具有相同的操作（和运行时间）（在范围x中查找最近邻居/查找节点）？ –

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

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

用于搜索KD树的基本原型是给定点（x，y）和矩形[a，b] * [c，d]，确定从点到矩形的距离（平方）。通常，这是克（X，A，B） +克（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） +克（Y，C，d，H）。我预计这个变体的运行时间将是可比的。（我会重做复发，但是对于常规KD树来说最糟糕的情况比大多数情况下的糟糕 - O（n ^1/2）用于在n个点中识别2D中最近的邻居。）

来源

2011-11-15 22:55:29 Per

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

回答

相关问题