algorithm - 多边形-多边形-交集在特殊情况下失败

Question

我已经实现了 Bentley-Ottmann-algorithm检测多边形-多边形交叉点。这通常非常有效:由于多边形不自相交，因此两个多边形的线段并集中的任何线段相交表明两个多边形相交。

但是如果我看这个案例:

没有路段交叉点。但显然两个多边形相交。

如果不使用朴素算法检查其他多边形中每个多边形的每个点的多边形内点并因此在 O(m*n) 中运行，我该如何检测这种情况。

Answer 1

提示:

处理特殊情况(例如边上的顶点或两条重叠边)是一个棘手的话题，因为配置多种多样并且情况可以伸缩(想想几个重叠的共线边)。

我最好的建议是通过为每个顶点分配一个内部或外部状态(相对于另一个多边形)来加强一致性。然后，当您将一条边与另一个多边形相交时，相交数的奇偶性必须与端点状态的变化相匹配(相同状态 => 偶数相交)。

我没有指定您分配状态的方式，这将取决于您的特定算法(实际上状态是在您进行时分配的)。重要的是，当状态经过测试时，您可能无法再更改它。

如果出现异常(交叉路口数量的奇偶性与状态变化不匹配)，您必须通过牺牲交叉路口或复制交叉路口(或您认为合适的任何其他规则)来解决该问题。

例子:

在此示例中，绿点表示被认为在蓝色多边形外部的顶点，数字表示分配给相应边的可接受的交点数。

下面的黑色轮廓表示由此状态分配产生的联合多边形。