3

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

  1. 插入新的线段。
  2. 查找给定点半径 R 内的所有线段。
  3. 找到给定点的半径 R1 内的所有点。
  4. 给定一条线段，找出它是否与任何现有线段相交。不需要确切的交点（尽管这可能不会简化任何事情。）

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

哪种数据结构/算法最适合这种情况？

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

4

4 回答 4

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

这种类型的细化策略仅对树进行局部更改，因此在实践中通常非常快。如果您还从集合中删除实体，您还可以通过对每个叶子施加最小实体数并在必要时将叶子元素折叠到其父元素来支持动态聚合。

我已经多次对四叉树/八叉树使用这种类型的方法，但在这个阶段我无法理解为什么类似的方法不适用于 kd-trees 等。

希望这可以帮助。

于 2012-01-26T06:51:14.007 回答
1

一种可能性是将您的空间划分为一个网格 - y 轴上可能有 10 个，x 轴上可能有 10 个，总共 100 个。

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

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

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

  • 更新段位置很便宜：只需在 x 和 y 方向上除以框大小。例如，如果 box-size 在两个方向上都是 20，而您的新坐标是 145,30。145/20==7 和 30/20==1，所以它进入 box(7,1)，用于基于 0 的系统。
于 2012-01-26T02:53:33.793 回答
1

您可以计算完全填充平面的曲线，而不是插入和删除到树中。这样的曲线将 2d 复杂度降低到 1d 复杂度，您将能够找到最近的邻居。您可以找到一些示例，例如 z 曲线和希尔伯特曲线。这是对我的问题http://en.wikipedia.org/wiki/Closest_pair_of_points_problem的更好描述。

于 2012-01-26T02:56:16.440 回答
1

虽然第 2 项和第 3 项相对容易，但在插入每一行时使用带有距离检查的简单线性搜索，第 4 项涉及更多。

我倾向于使用受约束的三角剖分来解决这个问题，其中所有输入线都被视为约束，并且三角剖分使用最近邻而不是 Delaunay 标准来平衡。Øyvind Hjelle、Morten Dæhlen和Joseph O'Rourkes Computational Geometry in C在 Triangulations and applications 中很好地涵盖了这一点。 两者都有可用的源代码，包括获取所有交集的集合。

我过去动态执行此操作的方法如下；

  • 创建由围绕数据范围（当前 + 未来）的两个三角形组成的任意三角剖分 (TIN)。

  • 对于每个新行

  • 将两个点都插入 TIN。这可以通过遍历三角形找到插入点，并根据新点和旧三角形将找到的三角形替换为三个新三角形来非常快速地完成。

  • 根据两个端点通过 TIN 切割一个截面，保留一个点列表，该截面切割任何先前插入的线。将交点详细信息添加到针对两条线存储的列表中，并将它们插入 TIN。

  • 强制插入的行作为约束

  • 使用最近邻准则平衡在上述过程中修改的所有相邻三角形对，并重复直到所有三角形都被平衡。

对于分布不佳的数据，这比基于网格的方法效果更好，但更难实现。将端点和线分组到重叠的网格中可能是 2 和 3 的一个很好的优化。

请注意，我认为在您的问题中使用“最近邻”一词会产生误导，因为这与“一条线给定距离内的所有点”或“另一点的给定半径内的所有点”不同。最近的邻居通常意味着单个结果，并不等同于“在给定的点到点或点到线的距离内”。

于 2012-01-26T08:19:37.790 回答