computational-geometry - 查找所有具有公差的线交点（最好是预先存在的实现）

Question

Bentley-Ottmann 算法可用于及时扫描一组线段中的所有交点n log n。但是有没有一个版本可以以可变的精度做到这一点？即，如果它们比某个距离更近，则认为它们相交？

Answer 1

假设您正在谈论 2D 中的线段。

AFAIK，这没什么特别的。您只需调整类/对象的intersects(...)功能。如果两个线段之间的最小距离低于预定义的阈值，则不会返回指示“真实”交叉点LineSegment的（或其他）值，以指示交叉点的定义。算法没有变化。booleantrue

---

¹见：

• 两条线段之间的最短距离
• 连接两个线段

Answer 2

如果 2 个线段不相交，则它们之间的最小距离至少在一个线段端点上。因此，在您的情况下，测试一对线段是否相交或某个线段端点是否靠近其他线段就足够了。

第一个测试是 Bentley-Ottmann 算法的标准测试，第二部分可以在扫描线上添加和删除线段。当段被添加到 SL（左端点）时，足以测试 SL 上靠近左端点的段以及在从 SL 到左的给定距离处结束的段。当从 SL 中删除段时类似。

我认为，由于对称性，仅测试一侧就足够了，例如将段添加到 SL。

由于端点已排序，因此此搜索应该很快。如果有一些关于公差的片段不密集的保证，那么这种变化不会改变n log n原始算法的运行时间。