两组线段的 Bentley-Ottmann 算法
Bentley-Ottmann 算法用于计算线段的交点。
但是，我不想找到所有线之间的交点，而是想找到两组线之间的交点。这就是说，对于线组 A 中的每条线，我想知道这些线与组 B 中的线之间的交点。
无论如何，我可以为此扩展 Bentley-Ottmann 算法吗？我已经实现了现有的 Bentley-Ottmann 算法（ 在库中CGAL），我并不热衷于修改它。然而，我热衷于找到重用它并扩展它的方法。
编辑：欢迎任何其他算法（不一定基于 Bentley-Ottmann）。如果这些算法已经在现有库中实现，那就更好了。
The Bentley-Ottmann algorithm is used for the computation of intersection of line segments.
However, instead of finding the intersecting points of all the lines among themselves, I want to find the intersecting points between two groups of lines. This is to say that for every line in line group A, I want to know the intersection points between those lines and the lines in group B.
Is there anyway I can extend the Bentley-Ottmann algorithm for this? I already have the existing Bentley-Ottmann algorithm implemented ( in the library of CGAL), and I am not keen to modify it. I am, however, am keen to find ways to reuse it and extend it.
Edit: Any other algorithms ( not necessarily based on Bentley- Ottmann) are welcome. It would be better if those algorithms are already implemented in the existing library.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以找到
A+B中所有线之间的所有交集，然后删除同一组中线之间的交集。您不会增加太多的复杂性，这允许您仅通过简单的包装函数即可使用未修改的 CGAL 库函数。You could find all intersections between all lines in
A+B, then remove intersections between lines in the same set. You're not increasing the complexity by much and this allows you to use CGAL's library function unmodified with only a simple wrapper function.是的，可以扩展 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 数据等）或需要通用算法，此类算法可能值得。
Yes Bentley-Ottmann algorithm can be extended to do this, along with other methods.
In literature, the task you described along the lines of reporting intersections between red and blue lines.
Here is a paper extending B-O sweep to an optimal algorithm.
http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf
I would disagree with @marcog's claim about complexity. The paper linked claims optimal time of O(n log(n+k)), if you filter the intersections, you will have to perform a B-O sweep on all lines, and it would be ((n+k) log n).
There are other similar algorithms which may not require complex data-structures http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf
For fewer edges and fewer intersections between edges, the solution in @marcog's answer might work well. (Here is an example from CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).
If you need to process complex polygons (GIS data etc.) or need a general algorithm, this class of algorithms might be worth while.
Bentley-Ottman 保留一棵按当前垂直位置排序的线段树，难道您不能保留两棵树，A 组和 B 组各一棵吗？然后，在原始算法检查当前点上方和下方的邻居的情况下，您需要检查上方的 A 邻居和下方的 B 邻居，反之亦然。
这是基于对维基百科文章的快速浏览；在过去的十年里我没有写太多几何代码。
Where Bentley-Ottman keeps a tree of line segments ordered by their current vertical position, couldn't you keep two trees, one each for groups A and B? Then where the original algorithm checks the neighbors above and below the current point, you'd check the A-neighbor above against the B-neighbor below, and vice versa.
This is based on a quick skim of the Wikipedia article; I haven't written much geometrical code in the past decade.
添加此答案是为了完整性，尽管它可能不是二维最有效的方法。
在 3D 图形中，常见的是 2 个 KD 树，可用于检测所有重叠节点（可用于几何体上的布尔运算）。
工作示例（C 代码）。
https://developer.blender .org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089
如果有很多小线段（例如手绘线的路径），这将是相当有效。但是，如果有许多长边（想想拾取棒）...这将表现得很差，并且您可能希望拆分 BVH 树中的叶节点以获得更好的性能。但是，如果是这样的话，最好使用其他答案中建议的不同方法。
Adding this answer for completeness, even though it may not be the most efficient method for 2 dimensions.
In 3D graphics its common to 2 KD-trees, which can be used to detect all overlapping nodes (can be used for boolean operations on geometry).
Working example (C code).
https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089
If there are many small segments (such as the path of a hand drawn line), this will be reasonably efficient. However if there are many long edges (think pickup-sticks)... this will perform badly, and you would want to split leaf nodes in the BVH tree to get better performance. However if thats the case, its probably better to use a different method as suggested in other answers.