自相交多边形的面积 [英] Area of self-intersecting polygon
问题描述
计算简单不规则多边形的面积并计算面积，我们得到了右上方多边形 ABEDCF 的错误区域.
如何才能最好地找到自相交多边形的可见区域?(如果答案需要为每个交叉点创建虚拟点，请提供有关如何最好地找到交叉点以及如何以正确顺序遍历它们的详细信息.)
在为我的 带有以下来自此页面 Bentley-Ottmann 算法 Bentley-Ottmann 算法的输入是线段 Li 的集合 OMEGA={Li}，其输出将是一组 LAMBDA={Ij} 的交点.该算法被称为扫描线算法"，因为它的操作可以被形象化为具有另一条线，一条扫描线"SL，扫描集合 OMEGA 并在它通过各个段 Li 时收集信息.为SL的每个位置收集的信息基本上是欧米茄中当前与SL相交的所有段的有序列表.维护此信息的数据结构通常也称为扫描线".该类结构还可以在发现交叉点时检测并输出它们.发现交点的过程是算法及其效率的核心. 要实现扫描逻辑，我们必须首先对 OMEGA 的段进行线性排序，以确定 SL 遇到它们的顺序.也就是说，我们需要对所有段 Li 的端点 {Ei0,Ei1}i=1,n 进行排序，以便我们可以检测 SL 何时开始和停止与 OMEGA 的每个段相交.传统上，端点的排序是先增加 x 然后增加 y 坐标值，但任何线性顺序都可以(一些作者更喜欢先减少 y 然后增加 x).在传统排序中，扫描线是垂直的，在遇到每个线段时从左向右移动，如图所示: 图片扫描线 在算法中的任何一点，扫描线 SL 仅与一个端点在其左侧(或在其上)而另一个端点在其右侧的线段相交.SL 数据结构通过以下方式保持这些段的动态列表:(1) 在遇到最左边的端点时添加段，以及 (2) 在遇到最右边的端点时删除段.此外，SL 对具有上下"关系的段列表进行排序.因此，要添加或删除段，必须确定其在列表中的位置，这可以通过对列表中当前段的最坏情况 O(log-n) 二进制搜索来完成.另外，除了增加或删除segment外，还有一个改变list结构的事件；即，每当两个段相交时，它们在有序列表中的位置必须交换.给定两个段，它们必须是列表中的邻居，这个交换是一个 O(log-n) 操作. 为了组织所有这些，该算法维护了一个有序的事件队列"EQ，其元素会导致 SL 段列表发生变化.最初，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 算法实现的顶层逻辑由以下伪代码给出: 该例程输出所有交点的完整有序列表. Calculating the area of a simple irregular polygon is trivial. However, consider the self-intersecting polygon ABCDEF shown at left below: If we use the linked-to formula above traversing the points in polygon order, we get an area of 0. (The 'clockwise' area cancels out the 'counter-clockwise' area.) However, if we sort the points radially around a center and calculate the area, we get the incorrect area of the polygon ABEDCF at right above. How can I best find the visible area of a self-intersecting polygon? (If the answer requires creating phantom points for each intersection, please provide details for how to best find the intersections and how then to traverse them in correct order.) This question arose when investigating edge cases for my solution to this question. I define the 'area' as the amount of pixels visible when filling the polygon using either the "nonzero" or "evenodd" rules. I will accept an answer for either of these, though both would be better. Note that I explicitly do not define the area for self-overlapping to count the overlapping area twice. You can try Bentley–Ottmann with the following pseudo code from this page The Bentley-Ottmann Algorithm The input for the Bentley-Ottmann algorithm is a collection OMEGA={Li} of line segments Li, and its output will be a set LAMBDA={Ij} of intersection points. This algorithm is referred to as a "sweep line algorithm" because it's operation can be visualized as having another line, a "sweep line" SL, sweeping over the collection OMEGA and collecting information as it passes over the individual segments Li. The information collected for each position of SL is basically an ordered list of all segments in OMEGA that are currently being intersected by SL. The data structure maintaining this information is often also called the "sweep line". This class structure also detects and outputs intersections as it discovers them. The process by which it discovers intersections is the heart of the algorithm and its efficiency. To implement the sweep logic, we must first linearly order the segments of OMEGA to determine the sequence in which SL encounters them. That is, we need to order the endpoints {Ei0,Ei1}i=1,n of all the segments Li so we can detect when SL starts and stops intersecting each segment of OMEGA. Traditionally, the endpoints are ordered by increasing x first and then increasing y-coordinate values, but any linear order will do (some authors prefer decreasing y first and then increasing x). With the traditional ordering, the sweep line is vertical and moves from left to right as it encounters each segment, as shown in the diagram: Pic-sweepline At any point in the algorithm, the sweep line SL intersects only those segments with one endpoint to the left of (or on) it and the other endpoint to the right of it. The SL data structure keeps a dynamic list of these segments by: (1) adding a segment when its leftmost endpoint is encountered, and (2) deleting a segment when its rightmost endpoint is encountered. Further, the SL orders the list of segments with an "above-below" relation. So, to add or delete a segment, its position in the list must be determined, which can be done by a worst-case O(log-n) binary search of the current segments in the list. In addition, besides adding or deleting segments, there is another event that changes the list structure; namely, whenever two segments intersect, then their positions in the ordered list must be swapped. Given the two segments, which must be neighbors in the list, this swap is an O(log-n) operation. To organize all this, the algorithm maintains an ordered "event queue" EQ whose elements cause a change in the SL segment list. Initially, EQ is set to the sweep-ordered list of all segment endpoints. But as intersections between segments are found, then they are also added to EQ in the same sweep-order as used for the endpoints One must test, though, to avoid inserting duplicate intersections onto the event queue. The example in the above diagram shows how this can happen. At event 2, segments S1 and S2 cause intersection I12 to be computed and put on the queue. Then, at event 3, segment S3 comes between and separates S1 and S2. Next, at event 4, S1 and S3 swap places on the sweep line, and S1 is brought next to S2 again causing I12 to be computed again. But, there can only be one event for each intersection, and I12 cannot be put on the queue twice. So, when an intersection is being put on the queue, we must find its potential x-sorted location in the queue, and check that it is not already there. Since there is at most one intersect point for any two segments, labeling an intersection with identifiers for the segments is sufficient to uniquely identify it. As a result of all this, the maximum size of the event queue = 2n+k.le.2n+n2, and any insertion or deletion can be done with a O(log(2n+n2)) = O(log-n) binary search. But, what does all this have to do with efficiently finding the complete set of segment intersections? Well, as segments are sequentially added to the SL segment list, their possible intersections with other eligible segments are determined. When a valid intersection is found, then it is inserted into the event queue. Further, when an intersection-event on EQ is processed during the sweep, then it causes a re-ordering of the SL list, and the intersection is also added to the output list LAMBDA. In the end, when all events have been processed, LAMBDA will contain the complete ordered set of all intersections. However, there is one critical detail, the heart of the algorithm, that we still need to describe; namely, how does one compute a valid intersection? Clearly, two segments can only intersect if they occur simultaneously on the sweep-line at some time. But this by itself is not enough to make the algorithm efficient. The important observation is that two intersecting segments must be immediate above-below neighbors on the sweep-line. Thus, there are only a few restricted cases for which possible intersections need to be computed: When a segment is added to the SL list, determine if it intersects with its above and below neighbors. When a segment is deleted from the SL list, its previous above and below neighbors are brought together as new neighbors. So, their possible intersection needs to be determined. At an intersection event, two segments switch positions in the SL list, and their intersection with their new neighbors (one for each) must be determined.
This means that for the processing of any one event (endpoint or intersection) of EQ, there are at most two intersection determinations that need to be made. One detail remains, namely the time needed to add, find, swap, and remove segments from the SL structure. To do this, the SL can be implemented as a balanced binary tree (such as an AVL, a 2-3, or a red-black tree) which guarantees that these operations will take at most O(log-n) time since n is the maximum size of the SL list. Thus, each of the (2n+k) events has at worst O(log-n) processing to do. Adding up the initial sort and the event processing, the efficiency of the algorithm is: O(nlog-n)+O((2n+k)log-n)=O((n+k)log-n). Pseudo-Code: Bentley-Ottmann Algorithm Putting all of this together, the top-level logic for an implementation of the Bentley-Ottmann algorithm is given by the following pseudo-code: This routine outputs the complete ordered list of all intersection points. 这篇关于自相交多边形的面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ 初始化事件队列 EQ = 所有段端点；通过增加 x 和 y 对 EQ 进行排序；将扫描线SL初始化为空；将输出交集列表IL初始化为空；While (EQ 非空) {令 E = EQ 的下一个事件；如果(E 是左端点){让 segE = E 的片段；将 segE 添加到 SL；让 segA = SL 中高于 segE 的部分；让 segB = SL 中低于 segE 的部分；如果 (I = Intersect( segE with segA) 存在)将 I 插入 EQ；如果 (I = Intersect( segE 与 segB) 存在)将 I 插入 EQ；}Else If(E 是右端点){让 segE = E 的片段；让 segA = SL 中高于 segE 的部分；让 segB = SL 中低于 segE 的部分；从 SL 中删除 segE；如果 (I = Intersect( segA with segB) 存在)如果(我已经不在情商中了)将 I 插入 EQ；}Else {//E 是一个相交事件将 E 的交点添加到输出列表 IL 中；设 segE2 上方的 segE1 为 E 在 SL 中的相交段；交换它们的位置，使 segE2 现在高于 segE1；令 segA = SL 中 segE2 以上的段；令 segB = SL 中 segE1 以下的段；如果 (I = Intersect(segE2 with segA) 存在)如果(我已经不在情商中了)将 I 插入 EQ；如果 (I = Intersect(segE1 with segB) 存在)如果(我已经不在情商中了)将 I 插入 EQ；}从 EQ 中删除 E；}返回 IL；}Defining the Area
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;
}
