algorithm - 两组线段的 Bentley-Ottmann 算法

Question

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

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

无论如何我可以扩展 Bentley-Ottmann algorithm为了这？我已经实现了现有的 Bentley-Ottmann 算法 ( in the library of CGAL )，我不想修改它。然而，我很想找到重用和扩展它的方法。

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

Answer 1

您可以找到A+B 中所有线之间的所有交点，然后删除同一组中线之间的交点。您并没有增加太多的复杂性，这允许您使用 CGAL 的库函数而无需修改，只需一个简单的包装函数。