2d圆最近邻的最佳动态数据结构

Question

标题是大多数问题.我有一组圆圈,每个圆圈由中心C和半径r给出.两个圆之间的距离是它们中心之间的欧氏距离减去它们的半径.对于圆圈a和b,

d_ab = | C_a - C_b | - r_a - r_b.

请注意,如果圆圈重叠,这可能是负数.

那么找到集合中给定圆的最近(最小距离)邻居的最快数据结构是什么？

必须支持添加和删除以"任意顺序交错"的"查找最近"查询的圆圈.事先没有人知道该集的几何分布.

这将是系统的核心,其中典型的圈数为50,000,并且将需要成千上万的查询,插入和删除,理想情况是高端平板设备上的用户交互速度(一秒或更短).

该点最近的邻居进行了研究,死亡,但这个版本与圈似乎有点困难.

我看过kd-trees,四棵树,r-trees以及这些变种.关于哪些可能是最好的尝试以及新建议的建议都将是一个非常好的帮助.

Answer 1

覆盖树是邻近结构的另一种可能性.它们不支持删除(？),但您可以在后台软删除和重建以防止垃圾堆积,这可能是其他结构的有用技术.

从2D圆问题到3D点问题的减少,具有如此的时髦度量.(您命名的邻近结构应该是可适应的.)将以(x,y)为中心的圆以半径r映射到点(x,y,r).将矢量(dx,dy,dz)的长度定义为sqrt(dx**2 + dy**2)+ abs(dz).这导致了一个指标.要找到距离中心最近的圆(x,y)(查询圆的半径不相关),请在(x,y,R)处进行邻近搜索,其中R大于或等于最大半径一个圆圈(可以修改你的邻近结构,这样就不必跟踪R).

根据我在点上实现kd-trees和Voronoi图的经验,从头开始实现kd-tree将更加容易.即使你重复使用其他人强大的几何原语(如果你走这条路线,请尽量保存你的理智),Voronoi /点位置的退化边缘情况需要时间才能正确.

Answer 2

感谢 @David Eisenstadt 提出 3D 搜索结构的想法。这是最佳答案的一部分，尽管不需要他奇怪的指标。

关键是要详细了解最近邻搜索的工作原理。我将展示四边形。k=3 的 Kd 树是相似的。这是伪代码：

# Let nearest_info be a record containing the current nearest neighbor (or nil 
# if none yet) and the distance from point to that nearest neighbor.
def find_nearest_neighbor(node, target, nearest_info)
  if node is leaf
    update nearest_info using target and the points found in this leaf
  else
    for each subdivision S of node
      if S contains any point P where dist(P,T) < nearest_info.distance,
        find_neareast(S, target, nearest_info)
      end
    end
  end
end

完成此操作后，nearest_info将包含最近的邻居及其距离。

关键是if S contains any point P where dist(P,T) < nearest_info.distance。在 3d 空间中，由(x,y,r)描述圆的三元组组成，我们有

def dist(P,T)
  return sqrt( (P.x - T.x)^2 + (P.y - T.y)^2 ) - P.r - T.r 
end

这里 P 是八叉树长方体的八分圆中的任意点。如何考虑长方体中的所有点？请注意，对于给定的搜索，T 的所有分量都有效固定，因此如果我们将目标写为常量点，则会更清楚(a, b, c)：

def dist(P)
  return sqrt( (P.x - a)^2 + (P.y - b)^2 ) - P.r
end

我们完全忽略了这一点c = T.r，因为在算法完成后可以从最小距离中减去它。换句话说，目标的半径不影响结果。

由此很容易看出，P我们需要获得长方体的最小距离是关于 x 和 y 以及最大表示半径的最接近目标的欧几里得距离。这是非常容易和快速计算的：2d 点-矩形距离和 1dmax操作。

事后看来，这一切都是显而易见的，但需要一段时间才能从正确的角度看待它。感谢您的想法。