Bentley-Ottmann算法用于计算线段的交点。
然而，我希望找到两组线段之间的交点，而不是找到所有线段之间的交点。也就是说，对于线段组A中的每条线段，我想知道它们与线段组B中的线段相交的交点。
有没有办法扩展Bentley-Ottmann算法来实现这个功能？我已经实现了现有的Bentley-Ottmann算法（在CGAL库中），并且我不想修改它。但是，我非常愿意找到重用和扩展它的方法。
编辑：欢迎使用任何其他算法（不一定基于Bentley-Ottmann），最好是已经在现有库中实现的算法。
A+B 中找到所有线段的交点，然后移除同一组中线段之间的交点。这样做并不会显著增加复杂度，并且只需要编写一个简单的包装函数，就可以直接使用 CGAL 库函数而不需要进行修改。是的，Bentley-Ottmann算法可以扩展到做这个任务，还有其他方法。
在文献中，您描述了沿着报告红线和蓝线之间的交点的任务。
这里有一篇论文将B-O扫描扩展到最优算法。 http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf
我不同意@marcog关于复杂性的说法。链接的论文声称最优时间为O(n log(n+k))，如果您过滤交点，则必须对所有线进行B-O扫描，它将是((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数据等）或需要一般算法，则这类算法可能值得一试。
为了完整性而添加此答案，即使它可能不是二维最有效的方法。
在3D图形中，常见的是2个KD树，可以用于检测所有重叠节点（可用于几何布尔运算）。
工作示例（C代码）。 https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089
如果有许多小段（例如手绘线的路径），这将是相当高效的。但是，如果有许多长边缘（想象一下拾起木棍）... 这将表现不佳，并且您需要分割BVH树中的叶节点以获得更好的性能。但是，如果是这种情况，最好使用其他答案中建议的不同方法。
在 Bentley-Ottman 中，根据当前垂直位置对线段树进行排序，你不能保留 两个 树吗？一个树用于 A 组，另一个树用于 B 组。然后，在原始算法检查当前点上下邻居的位置时，您将检查 A-邻居上方与 B-邻居下方，并反之亦然。
这基于快速浏览维基百科文章而来；在过去的十年中，我没有编写过太多几何代码。