在一组不断变化的线段中进行最近邻搜索

Question

我有一组线段。我想对它们执行以下操作：

1. 插入一个新的线段。
2. 在给定点的半径R内找到所有线段。
3. 查找给定点的镭R1中的所有点。
4. 给定一个线段，查找它是否与任何现有的线段相交。精确的交点是不必要的(尽管这可能不会简化任何事情)。

问题是，像kd/bd树或BSP树这样的算法是假设一个静态的点集，在我的例子中，这些点会不断地被新的点增强，这就需要重建树。

什么样的数据结构/算法最适合这种情况？

编辑:接受最简单的答案，解决我的问题。谢谢大家！

Answer 1

一种可能是将你的空间划分成一个方格--也许是y轴中的10个，x轴中的10个，总共100个。

将这些框存储在一个数组中，因此确定相邻的框非常容易/快速。每个框将包含一个位于该框中的线段的列表向量。

当计算一个段的R内的线段时，只能检查相关的相邻框。

当然，您可以创建多个不同粒度的地图，可能是100×100个较小的盒子。在您的设计中，只需考虑空间与时间和维护的权衡。

• 更新段位置很便宜:只是整数除以x和y方向上的方框大小。例如，如果盒子大小在两个方向都是20，而你的新坐标是145,30.145/20=7，30/20=1，因此它进入方框(7，1)，用于基于0的系统。

Answer 2

维护动态树可能没有您想象的那么糟糕。

当您在集合中插入新的点/行等时，很明显，您需要改进当前的树，但我不明白为什么每次添加新实体时都必须从头重新构建整个树，正如您所建议的那样。

使用动态树方法，您将在任何时候都有一个有效的树，因此您可以使用树类型所支持的快速范围搜索来查找您提到的几何实体。

针对你的特殊问题：

• 您可以设置一个动态几何树，其中叶元素维护与该叶关联的几何实体(点和线)列表。
• 在将一行插入集合中时，应将其推送到与其相交的所有叶元素的列表中。您可以通过从与行相交的根遍历树的子集来有效地做到这一点。
• 要在指定的径向晕中找到所有点/线，首先需要找到该区域的所有叶子。同样，这可以通过从被包围的根遍历树的子集或与晕相交来实现。由于可能有一些重叠，所以您需要检查与这组叶元素相关的实体是否实际上位于光环内。
• 一旦将一行插入到一组叶子元素中，就可以通过扫描与刚刚找到的叶子框子集相关的所有行来确定它是否与另一行相交。然后，您可以对这个子集进行行交测试。

一种基于与树中每片叶子相关联的实体数量上限的动态树求精算法可能会按照以下思路工作：

function insert(x, y)

find the tree leaf element enclosing the new entitiy at (x,y) based on whatever 
fast search algorithm your tree supports

if (number of entities per leaf > max allowable) do

    refine current leaf element (would typically either be a bisection 
    or quadrisection based on a 2D tree type)

    push all entities from the old leaf element list onto the new child element
    lists, based on the enclosing child element

else

    push new entity onto list for leaf element

endif

这种类型的细化策略只对树进行局部更改，因此在实践中通常是相当快的。如果您也要从集合中删除实体，您还可以支持动态聚合，方法是强制每个叶最少数量的实体，并在必要时将叶元素折叠到它们的父元素。

我在四叉树/八叉树中多次使用这种方法，在这个阶段我无法理解为什么类似的方法不能与octrees等一起工作。

希望这能有所帮助。

Answer 3

而不是插入和删除到树中，你可以计算出一条曲线，完全填充平面。这样的曲线将2d复杂度降低到一维复杂度，您就可以找到最近的邻居了。你可以找到像z曲线和hilbert曲线这样的例子。下面是对我的问题问题的更好的描述。