使用容差值查找所有线段交点（最好使用现有的实现）

Question

Bentley-Ottmann算法可用于扫描一组线段中的所有交点，时间复杂度为n log n。但是否有一种版本可以使用可变精度进行此操作？即，如果线段靠近某个距离，则被认为相交。

- Sideshow Bob

---

你是在谈论直线还是线段？ - sloriot

Answer 1

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

据我所知，这没有什么特别之处。您只需调整LineSegment类/对象的intersects(...)函数即可。不再返回表示“真实”交点的boolean（或其他）值，而是如果两个线段之间的最小距离低于您预定义的阈值，则返回true，表示您对交点的定义。算法没有变化。

---

¹ 请参见：

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

- Bart Kiers

---

这对于两条线段来说还好，但并不能像 Bentley-Ottmann 算法那样在 n log n 的时间内解决所有相交的线段对问题。（抱歉，我应该在原帖中说明这一点 - 我会修复的）。 - Sideshow Bob

Answer 2

如果两个线段不相交，则它们之间的最小距离至少在一个线段端点处。因此，在您的情况下，只需测试一对线段是否相交或某个线段端点是否靠近其他线段即可。

第一次测试是 Bentley-Ottmann 算法的标准部分，第二部分可以通过向扫描线添加和删除线段来完成。当线段被添加到扫描线（左端点）时，只需要测试靠近左端点的扫描线上的线段和从扫描线到左边给定距离结束的线段。从扫描线中删除线段时也类似。

我认为，由于对称性，只需要测试一侧，例如将线段添加到扫描线。

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

- Ante