5

Bentley-Ottmann 算法用于计算线段的交点。

但是,我不想找到所有线之间的交点,而是要找到两组线之间的交点。也就是说,对于线组中的每条线A,我都想知道这些线与线组中的线之间的交点B

无论如何我可以为此扩展Bentley-Ottmann 算法吗?我已经实现了现有的 Bentley-Ottmann 算法(在 CGAL 库中),我不想修改它。然而,我渴望找到重用和扩展它的方法。

编辑:欢迎任何其他算法(不一定基于 Bentley-Ottmann)。如果这些算法已经在现有库中实现会更好。

4

4 回答 4

4

您可以找到 中所有线之间的所有交点A+B,然后删除同一集合中的线之间的交点。您不会增加太多复杂性,这允许您使用未经修改的 CGAL 库函数,只需一个简单的包装函数。

于 2010-12-30T01:31:29.697 回答
0

在 Bentley-Ottman 保留按当前垂直位置排序的线段树的情况下,您不能保留棵树,A 组和 B 组各一棵吗?然后,在原始算法检查当前点上方和下方的邻居的地方,您将检查上方的 A 邻居与下方的 B 邻居,反之亦然。

这是基于对维基百科文章的快速浏览;在过去的十年里,我没有写过多少几何代码。

于 2011-02-02T22:20:50.577 回答
0

添加此答案以确保完整性,即使它可能不是二维的最有效方法。

在 3D 图形中,它共有 2 个 KD 树,可用于检测所有重叠节点(可用于几何上的布尔运算)。

工作示例(C 代码)。 https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $1089

如果有很多小段(例如手绘线的路径),这将是相当有效的。但是,如果有很多长边(想想拾音器) ......这会表现得很糟糕,你会想要分裂 BVH 树中的叶节点以获得更好的性能。但是,如果是这种情况,最好使用其他答案中建议的不同方法。

于 2015-08-02T03:38:04.070 回答
0

是的,可以扩展 Bentley-Ottmann 算法以及其他方法来执行此操作。

在文献中,您描述的任务是报告红线和蓝线之间的交点

这是一篇将 BO 扫描扩展到最优算法的论文。 http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

我不同意@marcog 关于复杂性的说法。链接的论文声称 O(n log(n+k)) 的最佳时间,如果过滤交叉点,则必须对所有行执行 BO 扫描,它将是 ((n+k) log n)。

还有其他类似的算法可能不需要复杂的数据结构http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

对于更少的边缘和边缘之间的交叉点,@marcog 的答案中的解决方案可能效果很好。(这里是 CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html的一个例子)。

如果您需要处理复杂的多边形(GIS 数据等)或需要通用算法,那么这类算法可能值得一试。

于 2016-01-10T19:27:58.443 回答