问找到所有具有容差的线交点(最好是预先存在的实现)

EN

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

在Bentley-Ottmann算法中，第一步测试是标准的，第二步是在扫描线上添加和删除线段。当段被添加到SL (左端点)时，它足以测试SL上靠近左端点的段以及在从SL到左的给定距离结束的段。类似于从SL中删除段时的情况。

我认为，由于对称性的原因，这足以测试一侧，例如向SL添加分段。

因为端点是排序的，所以这个搜索应该很快。如果可以保证片段在容差方面不是密集的，那么这种改变不会改变原始算法的n log n运行时间。