algorithm - 自相交多边形的面积

Question

计算简单的不规则多边形is trivial的面积。但是，请考虑下面左图所示的自相交多边形ABCDEF：



如果使用上面链接的公式以多边形顺序遍历点，则面积为0。（“顺时针”区域抵消了“逆时针”区域。）

但是，如果我们sort the points radially around a center并计算面积，则会在右上方获得多边形ABEDCF的不正确面积。

如何最好地找到自相交多边形的可见区域？ （如果答案要求为每个路口创建幻像点，请提供有关如何最好地找到路口以及如何以正确顺序遍历它们的详细信息。）

在调查我的this question解决方案的极端案例时出现了这个问题。

定义区域

我将“区域”定义为使用“非零”或“均等”规则填充多边形时可见的像素数量。我会接受以上任何一个的答案，尽管两者都会更好。请注意，我没有明确定义自重叠区域以对重叠区域进行两次计数。

Answer 1

您可以使用Bentley–Ottmann中的以下伪代码尝试this page

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）。按照传统的排序方式，扫掠线是垂直的，并且在遇到每个线段时从左向右移动，如下图所示：

横扫线

在算法中的任何点，扫掠线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;
}

此例程输出所有交点的完整有序列表。