Bentley-Ottmann 算法用于计算线段的交点。
但是，我不想找到所有线之间的交点，而是要找到两组线之间的交点。也就是说，对于线组中的每条线A，我都想知道这些线与线组中的线之间的交点B。
无论如何我可以为此扩展Bentley-Ottmann 算法吗？我已经实现了现有的 Bentley-Ottmann 算法（在 CGAL 库中），我不想修改它。然而，我渴望找到重用和扩展它的方法。
编辑：欢迎任何其他算法（不一定基于 Bentley-Ottmann）。如果这些算法已经在现有库中实现会更好。
您可以找到 中所有线之间的所有交点A+B，然后删除同一集合中的线之间的交点。您不会增加太多复杂性，这允许您使用未经修改的 CGAL 库函数，只需一个简单的包装函数。
在 Bentley-Ottman 保留按当前垂直位置排序的线段树的情况下，您不能保留两棵树，A 组和 B 组各一棵吗？然后，在原始算法检查当前点上方和下方的邻居的地方，您将检查上方的 A 邻居与下方的 B 邻居，反之亦然。
这是基于对维基百科文章的快速浏览；在过去的十年里，我没有写过多少几何代码。
添加此答案以确保完整性，即使它可能不是二维的最有效方法。
在 3D 图形中，它共有 2 个 KD 树，可用于检测所有重叠节点（可用于几何上的布尔运算）。
工作示例（C 代码）。 https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $1089
如果有很多小段（例如手绘线的路径），这将是相当有效的。但是，如果有很多长边（想想拾音器） ......这会表现得很糟糕，你会想要分裂 BVH 树中的叶节点以获得更好的性能。但是，如果是这种情况，最好使用其他答案中建议的不同方法。
是的，可以扩展 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 数据等）或需要通用算法，那么这类算法可能值得一试。