两组线段的Bentley-Ottmann算法

Question

Bentley-Ottmann算法用于计算线段的交集.

但是,我想找到两组线之间的交叉点,而不是找到它们之间所有线的交叉点.这就是说,对于线组中的每一行A,我想知道这些线与组中的线之间的交叉点B.

无论如何我可以为此扩展Bentley-Ottmann算法吗？我已经实现了现有的Bentley-Ottmann算法(在CGAL库中),我并不热衷于修改它.但是,我很想找到重用它并扩展它的方法.

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

Answer 1

您可以找到 中所有线之间的所有交点A+B，然后删除同一组中的线之间的交点。您不会增加太多的复杂性，这允许您仅通过简单的包装函数即可使用未修改的 CGAL 库函数。