4

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

4

2 回答 2

1

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

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


1见:

于 2012-09-18T08:15:22.883 回答
1

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

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

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

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

于 2012-09-19T09:00:24.480 回答