自相交多边形的面积

Question

计算简单不规则多边形的面积是微不足道的.但是,请考虑左下方显示的自相交多边形ABCDEF:

                   

如果我们使用上面的链接到公式以多边形顺序遍历点,我们得到一个区域为0.('顺时针'区域取消'逆时针'区域.)

但是,如果我们将点径向围绕中心排序并计算面积,我们会在右上方得到多边形ABEDCF的错误区域.

如何才能最好地找到自相交多边形的可见区域？(如果答案需要为每个交叉点创建幻像点,请提供有关如何最好地找到交叉点以及如何以正确顺序遍历它们的详细信息.)

在调查此问题解决方案的边缘案例时出现了这个问题.

定义区域

我将'area'定义为使用"非零"或"偶数"规则填充多边形时可见的像素数量.我会接受其中任何一个的答案,尽管两者都会更好.请注意,我明确地没有定义自重叠区域来重复计算两次重叠区域.

Answer 1

您可以使用此页面中的以下伪代码尝试Bentley-Ottmann

Bentley-Ottmann算法

Bentley-Ottmann算法的输入是线段Li的集合OMEGA = {Li},其输出将是交集点的集合LAMBDA = {Ij}.该算法被称为"扫描线算法",因为它的操作可以被视为具有另一条线,"扫描线"SL,扫过集合OMEGA并在通过各个段Li时收集信息.为SL的每个位置收集的信息基本上是OMEGA中当前与SL相交的所有段的有序列表.保持该信息的数据结构通常也称为"扫描线".此类结构还会在发现交叉点时检测并输出交叉点.它发现交叉点的过程是算法的核心和效率.

为了实现扫描逻辑,我们必须首先对OMEGA的段进行线性排序,以确定SL遇到它们的顺序.也就是说,我们需要对所有段Li的端点{Ei0,Ei1} i = 1,n进行排序,以便我们可以检测SL何时开始和停止与OMEGA的每个段相交.传统上,端点是通过先增加x然后增加y坐标值来排序的,但任何线性顺序都会这样做(某些作者更喜欢首先减小y然后增加x).使用传统排序时,扫描线是垂直的,并在遇到每个线段时从左向右移动,如图所示:

PIC-扫掠迹线

在算法中的任何点,扫描线SL仅与那些具有一个端点的那些段相交(或在其上)和另一个端点在其右侧.SL数据结构通过以下方式保留这些段的动态列表:(1)在遇到其最左端点时添加段,以及(2)在遇到其最右端点时删除段.此外,SL以"上下"关系命令段列表.因此,要添加或删除段,必须确定其在列表中的位置,这可以通过列表中当前段的最坏情况O(log-n)二进制搜索来完成.此外,除了添加或删除段之外,还有另一个更改列表结构的事件; 也就是说,每当两个段相交时,必须交换它们在有序列表中的位置.给定两个段,它们必须是列表中的邻居,此交换是O(log-n)操作.

为了组织所有这些,该算法维护有序的"事件队列"EQ,其元素导致SL段列表的改变.最初,EQ设置为所有段端点的扫描顺序列表.但是当找到段之间的交叉点时,它们也会以与用于端点的扫描顺序相同的方式添加到EQ中.但是,必须测试以避免在事件队列中插入重复的交叉点.上图中的示例显示了这种情况的发生方式.在事件2处,段S1和S2导致交叉点I12被计算并放入队列.然后,在事件3处,段S3进入并分离S1和S2.接下来,在事件4处,S1和S3交换扫描线上的位置,并且S1再次接近S2,导致再次计算I12.但是,每个交叉点只能有一个事件,并且I12不能两次放入队列.因此,当交叉点被放入队列时,我们必须在队列中找到其潜在的x排序位置,并检查它是否已存在.由于任何两个段最多只有一个交叉点,因此用段的标识符标记交叉点就足以唯一地标识它.由于这一切,事件队列的最大大小= 2n + k.le.2n + n2,任何插入或删除都可以使用O(log(2n + n2))= O(log-n)完成)二分搜索.

但是,所有这些与高效地找到完整的段交叉点有什么关系呢？好吧,由于段被顺序添加到SL段列表中,因此确定了它们与其他符合条件的段的可能交叉点.找到有效的交集时,会将其插入到事件队列中.此外,当在扫描期间处理EQ上的交叉事件时,它导致SL列表的重新排序,并且交叉点也被添加到输出列表LAMBDA.最后,当所有事件都已处理完毕后,LAMBDA将包含所有交叉点的完整有序集.

然而,我们仍然需要描述一个关键细节,即算法的核心; 即,如何计算有效的交叉点？显然,如果两个段在某个时间同时出现在扫描线上,则它们只能相交.但这本身并不足以使算法有效.重要的观察结果是,两条相交的区段必须位于扫描线上方的邻居之上.因此,只有少数受限情况需要计算可能的交叉点:

将段添加到SL列表时,确定它是否与其上下邻居相交.

当从SL列表中删除段时,其先前的上方和下方邻居将作为新邻居聚集在一起.因此,需要确定它们可能的交叉点.

在交叉点事件中,两个段在SL列表中切换位置,并且必须确定它们与它们的新邻居(每个一个)的交集.这意味着对于EQ的任何一个事件(端点或交叉点)的处理,最多需要进行两个交叉点确定.

还有一个细节,即从SL结构中添加,查找,交换和删除段所需的时间.为此,SL可以实现为平衡二叉树(例如AVL,2-3或红黑树),这保证了这些操作从n开始最多需要O(log-n)时间是SL列表的最大大小.因此,(2n + k)事件中的每一个都在最坏的情况下进行O(log-n)处理.加上初始排序和事件处理,算法的效率为:O(nlog-n)+ O((2n + k)log-n)= O((n + k)log-n).

伪码:Bentley-Ottmann算法

将所有这些放在一起,Bentley-Ottmann算法实现的顶层逻辑由以下伪代码给出:

    Initialize event queue EQ = all segment endpoints;
    Sort EQ by increasing x and y;
    Initialize sweep line SL to be empty;
    Initialize output intersection list IL to be empty;

    While (EQ is nonempty) {
        Let E = the next event from EQ;
        If (E is a left endpoint) {
            Let segE = E's segment;
            Add segE to SL;
            Let segA = the segment Above segE in SL;
            Let segB = the segment Below segE in SL;
            If (I = Intersect( segE with segA) exists) 
                Insert I into EQ;
            If (I = Intersect( segE with segB) exists) 
                Insert I into EQ;
        }
        Else If (E is a right endpoint) {
            Let segE = E's segment;
            Let segA = the segment Above segE in SL;
            Let segB = the segment Below segE in SL;
            Delete segE from SL;
            If (I = Intersect( segA with segB) exists) 
                If (I is not in EQ already) 
                    Insert I into EQ;
        }
        Else {  // E is an intersection event
            Add E’s intersect point to the output list IL;
            Let segE1 above segE2 be E's intersecting segments in SL;
            Swap their positions so that segE2 is now above segE1;
            Let segA = the segment above segE2 in SL;
            Let segB = the segment below segE1 in SL;
            If (I = Intersect(segE2 with segA) exists)
                If (I is not in EQ already) 
                    Insert I into EQ;
            If (I = Intersect(segE1 with segB) exists)
                If (I is not in EQ already) 
                    Insert I into EQ;
        }
        remove E from EQ;
    }
    return IL;
}

该例程输出所有交叉点的完整有序列表.