标题是最大的问题。我有一组圆，每个圆都有一个圆心 C 和半径 r。两个圆之间的距离是它们的圆心之间的欧几里得距离减去它们的半径。对于圆 a 和 b，
d_ab = |C_a - C_b| - r_a - r_b。
请注意，如果圆圈重叠，则该值可能为负。
那么，查找集合中给定圆的最近（最小距离）邻居的最快数据结构是什么？
必须支持以任意顺序交错的“查找最近”查询添加和删除圆圈。事先不知道该集合的几何分布。
这将成为系统的核心，其中圆圈的典型数量为 50,000 个，并且需要数十万次查询、插入和删除，理想情况是在高端平板电脑设备上以用户交互速度（一秒或更短）进行操作。
The point最近的邻居已经被研究得很死了，但是这个带圆圈的版本似乎有点难。
我研究过 kd 树、四叉树、r 树以及它们的一些变体。关于其中哪一个可能是最好尝试的建议以及新的建议都会有很大的帮助。
覆盖树木 http://en.wikipedia.org/wiki/Cover_tree是邻近结构的另一种可能性。它们不支持删除（？），但您可以在后台进行软删除和重建，以防止垃圾堆积，这对于其他结构可能是一种有用的技术。
使用如下所示的时髦度量将 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 树和 Voronoi 图的经验，从头开始实现 kd 树会容易得多。即使您重复使用其他人强大的几何图元（如果您走这条路，请这样做，以保存您的理智），Voronoi/点位置的退化边缘情况也需要时间才能正确。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
