二维圆最近邻居的最佳动态数据结构 [英] Best dynamic data structure for 2d circle nearest neighbor

问题描述

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

The title is most of the problem. I have a set of circles, each given by a center C and radius r. The distance between two circles is the Euclidean distance between their centers minus both their radii. For circles a and b,

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

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

请注意，如果圆圈重叠，则此参数可以为负.

Note this can be negative if the circles overlap.

那么，用于查找集合中给定圆的最近(最小距离)邻居的最快数据结构是什么?

Then what is the quickest data structure for finding the nearest (minimum distance) neighbor of a given circle in the set?

必须支持以任意顺序插入和删除带有查找最近"查询的圈子.事先对集合的几何分布一无所知.

Adding and deleting circles with "find nearest" queries interleaved in arbitrary order must be supported. Nothing is known about the set's geometric distribution in advance.

这将是系统的核心，该系统的典型圈子数为50,000，并且需要十万个查询，插入和删除，最好以高端用户交互速度(一秒钟或更短)进行平板电脑设备.

This will be the heart of a system where a typical number of circles is 50,000 and 10's of thousands of queries, inserts, and deletes will be needed, ideally at user-interaction speed (a second or less) on a high end tablet device.

point 最近的邻居已经被研究处死，但是这个带有圆圈的版本似乎更难.

The point nearest neighbor has been studied to death, but this version with circles seems somewhat harder.

我看过kd树，quad树，r树以及这些树的一些变体.不管是关于哪种建议最好的尝试，还是提出新的建议都会有很大帮助.

I have looked at kd-trees, quad trees, r-trees, and some variations of these. Both advice on which of these might be the best to try and also new suggestions would be a terrific help.

推荐答案

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

Thanks to @David Eisenstadt for the idea of a 3d search structure. This is part of the best answer, though his strange metric is not needed.

关键在于详细研究最近邻居搜索的工作方式.我将显示四分之一. k = 3的Kd树是相似的.这是伪代码:

The key is to look in detail at how nearest neighbor search works. I'll show this for quadrees. Kd-trees with k=3 are similar. Here is pseudocode:

# 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包含最近的邻居及其距离.

When this is done, nearest_info contains the nearest neighbor and its distance.

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

The key is if S contains any point P where dist(P,T) < nearest_info.distance. In a 3d space, of (x,y,r) triples that describe circles, we have

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):

Here P is an arbitrary point in an octant of an octree cuboid. How to consider all points in the cuboid? Note all components of T are effectively fixed for a given search, so it's clearer if we write the target as a constant point (a, b, c):

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

我们完全省略了c = T.r的地方，因为可以在算法完成后将其减去最小距离.换句话说，目标的半径不会影响结果.

Where we have left out c = T.r completely because it can be subtracted out of the minimum distance after the algorithm is complete. In other words, the radius of the target does not affect the result.

由此很容易看出，P我们需要获得与长方体的最小距离是相对于x和y且最大半径表示的最接近目标的欧几里得距离.这非常容易且快速地进行计算:2d点-矩形距离和1d max运算.

With this it is pretty easy to see that the P we need to obtain minimum dist to the cuboid is Euclidean closest to the target with respect to x and y and with the max represented radius. This is very easy and quick to compute: a 2d point-rectangle distance and a 1d max operation.

事后看来，所有这些都是显而易见的，但是花了一段时间才从正确的角度看待它.谢谢你的想法.

In hindsight all this is obvious, but it took a while to see it from the right point of view. Thanks for the ideas.

这篇关于二维圆最近邻居的最佳动态数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！