查找线交叉点算法

Question

可能的重复：
查找所有线段的交点 < /p>

嗨，

我有一组由 2 个点定义的线。您能给我推荐一种可以找到所有交叉点的快速算法吗？

谢谢

Answer 1

如果您指的是线段，则可以使用 Bentley-Ottmann 算法 查找 O((n+k)*log(n)) 中的所有交叉点，其中 k 是交叉点总数，n是集合中的段数。