处理多边形裁剪中的退化交点：计算机图形学中的重要算法问题

计算机图形：X 2（2019）100007技术部分裁剪具有退化交点的简单多边形6Erich L Fostera， Kai Hormannb， Romeo Traian PopacaCarnegie Robotics，LLC，4501 Hat Field Street，Pittsburgh，PA 15201，USAb瑞士卢加诺6904，Via Giuseppe Bu 13，意大利Svizzera大学信息学院机械工程和机械学专业，布氏动力学专业，独立自主专业，布氏060042专业，罗马尼亚Ar ticlei n f o ab st ract文章历史记录：收到2019年2019年5月29日修订2019年6月3日接受在线提供2019年MSC：68U05保留字：多边形裁剪退化交点多边形裁剪在许多领域都是一种常见的操作，包括计算机图形学、CAD和GIS。因此，高效、通用的多边形裁剪算法具有重要意义。Greiner和Hormann（1998）提出了一种简单且时间效率高的算法，可以裁剪任意多边形，包括凹多边形和带孔的自相交多边形。然而，Greiner-Hormann算法不能正确处理退化相交的情况，而不需要扰动顶点。我们提出了一个扩展的Greiner-Hormann多边形裁剪算法，妥善处理这种退化的情况。© 2019作者（S）。由Elsevier Ltd.发布。这是CC BY-NC-ND许可下的开放获取文章。（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。1. 介绍多边形裁剪是计算机图形学[2]、计算机辅助设计（CAD）[3]、地理信息系统（GIS）[4]和计算科学[5]中不可或缺的工具。诸如VLSI电路设计[6]以及数值模拟之类的应用通常需要进行数千次多边形裁剪，并且在GIS中，待裁剪的多边形通常是非凸的，可能具有孔并且可能具有数千个顶点[7]。因此，高效、通用的多边形裁剪算法是非常重要的。Weiler和Atherton[8]是第一个提出带孔凸多边形和凹多边形的裁剪算法的人。Greiner和Hormann[1]进一步发展了他们的想法，他们提出了一种简单而有效的算法，也可以处理自相交多边形，就像Vatti与Vatti算法相比，Greiner-Hormann算法的主要优点如果一个多边形的顶点位于另一个多边形的边上或与另一个多边形的顶点重合，则算法失败。Greiner和Hormann建议扰动多边形顶点来处理退化情况，这在计算机图形学中是足够的，因为结果在视觉上保持不变。6这篇文章是由L.巴特∗通讯作者。电子邮件地址：kai. usi.ch（K.Hormann）。只要扰动小于屏幕像素的大小，就可以校正然而，在大多数其他应用中，由扰动引起的不准确性是不期望的。Kim和Kim[3]提出了Greiner-Hormann算法的扩展，该算法处理这些退化情况，而无需扰动多边形顶点。然而，该方法需要计算邻近交点的所有边的中点的内部/外部状态，从而导致相当大的额外计算成本。在接下来的章节中，我们提出了一种处理简并的替代方法，避免了这些昂贵的计算。另一种可以处理这些情况的方法是Wang和Manocha[11]的基于裁剪的裁剪算法，尽管效率较低。我们首先简要概述了问题（第2节）和原始的特别地，详细讨论了所有可能的退化交点的检测和分类（第4.1节）以及交点的标记（第4.2节）。在给出了一些例子（第5节）之后，我们在论文的最后讨论了我们算法2. 多边形裁剪让美国开始通过正式定义的削波问题.平面多边形P =[P1，P2，. . . ，Pn]，其中n ≥ 3个顶点Pi∈R2 是 已定义 作为的分段线性的，关闭路径的通过连接边[P1，P2]，[P2，P3]，.. . . ，[Pn-1，P n]，[P n，P1]，其以给定顺序连续连接顶点Pihttps://doi.org/10.1016/j.cagx.2019.1000072590-1486/© 2019作者。由Elsevier Ltd.发布。这是CC BY-NC-ND许可下的开放获取文章。（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。可在ScienceDirect上获得目录列表图形：X期刊首页：www.elsevier.com/locate/cagx2E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）100007\\Pab cdFig. 1. 单个简单多边形（a）、具有三个组件和一个孔的简单复杂多边形（b）、单个自相交多边形（c）和具有三个组件的复杂自相交多边形（d）的示例，其内部已着色。a B C图二. 多边形裁剪的例子：有三个分量和一个洞（a）的简单多边形P和有一个分量的自相交多边形Q的相交(b)给出了一个结果多边形R，它有两个分量，其中一个是简单的，另一个是自交的（c）。a B C图3. 对于两个给定的多边形P和Q（a），Greiner-Hormann算法首先计算所有交点（），然后将它们标记为入口（）或出口（）点，并最终生成结果多边形R（c）。(see图la、c）。复多边形P={P1，P2，. . . ，Pm}是m≥1个多边形Pj的集合，称为P的分支（见图1b，d）。我们遵循这样的惯例，即P的内部由奇偶规则[2]确定，并且由不位于P的任何边上的所有点p∈R2组成，并且从p在任何方向上的无穷大都与P相交奇数次。由于这一定义，位于其他组件内部的组件通常被称为孔（见图1b）。为了简洁起见，我们将单个多边形视为具有一个组件的复杂多边形，并将复杂多边形简称为多边形。一个多边形被称为简单多边形，如果它不交叉自己，也就是说，它的边缘只相交于公共端点，这反过来又相当于它的半开边根本不相交的性质。因此，简单多边形的每个组成部分在拓扑上都等价于一个圆（见图2）。 1a、b）。多边形裁剪通常是指计算两个多边形P和Q的内部的交集PQ，通常称为剪辑和主题多边形，其本身是由多边形R限定的区域（参见图2）。大多数裁剪算法都可以修改也可以计算其他多边形集合运算，如并集P≠Q和差集PQ和QP. 尤其是在计算机绘图方面-多边形裁剪也可以更具体地指将主题多边形分割成位于裁剪多边形内部的那些部分和位于裁剪多边形外部的那些部分的过程[12]。然而，我们遵循更常见的惯例，即裁剪P并且Q产生P<$Q，并且注意结果关于P和Q是对称的。3. Greiner–HormannGreiner-Hormann多边形裁剪算法[1]由三个相交阶段计算P和Q之间的所有交点，并将它们作为新顶点插入到两个多边形中。在图3中，有八个这样的交点I1，. ，I8，并且该算法例如在P1和P2之间添加I1作为P的新顶点，并且在Q3和Q4之间依次添加I1、I6、I8和I3作为Q的新顶点。Greiner和Hormann提出用循环双向链表表示所有多边形分量，以便于顶点插入操作，并使用第三阶段所需的附加相邻指针链接相应的相交顶点对（见图11）。 4）。标记阶段将Q的每个交叉点I标记为入口或出口点，这取决于是否有人以给定的顺序沿着P行进在I处进入或离开Q的内部，并且对于Q的交叉点也是类似的。为此，该算法从P的第一个顶点P开始，确定P是在Q的内部还是外部[13]，然后按照给定的顺序遍历P的所有顶点，将相交顶点交替标记为入口或出口。对于图3中的例子，P的第一个分量的第一个顶点P1被识别为说谎。E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）10000731212见图4。Greiner-Hormann算法使用双向链表来表示多边形组件。在插入和标记相交顶点之后（参见图3b），R的每个分量R通过从P（阴影）上的交叉点开始，以正确的顺序沿着P移动，在下一个交叉点切换到Q，并重复这个过程直到R闭合。切换步骤需要将P和Q的对应相交顶点与相邻指针（虚线）链接。a B C图五. Greiner-Hormann算法不能处理像P3（a）那样的退化交点，虽然扰动顶点有助于克服这一限制，但不同的扰动方向可能导致几何和拓扑上不同的对于P的第二个分量，它的第一个顶点P6位于Q之外，因此I5得到一个入口，I6得到一个出口标签，等等。对于Q，该算法确定Q1位于P之外，然后将I2 标 记 为入口，然后将I7标记为出口，等等。跟踪阶段最终生成结果多边形R的所有分量。从P的交叉点I开始，根据I的标号是入口还是出口，al-tam分别沿着P的相应分量向前或向后移动，直到遇到下一个交叉点。使用相邻指针，该算法然后切换到Q的对应相交顶点，并重复该过程，直到它返回到I。所有以这种方式和顺序访问的顶点构成R的一个分量，并且算法继续生成分量，直到所有相交顶点都被访问。对于图3中的示例，第一个分量的跟踪从I1开始。由于I1被标记为出口点，我们向后遍历P，首先遇到P1，然后是I4，在那里我们切换到Q。作为Q的一个顶点，I4的标签是exit，因此我们向后继续到I5并切换回P。观察P上的I5是一个入口点，我们向前推进到I6，切换，沿着Q移动到I1，然后切换回来，我们得到P上的初始顶点I1。这就完成了R的第一个分量R1的追踪，其中顶点R1 = I1，R2= P1，R3 = I4，R4 = I5，R5=I6（见图1和图2）。3 c和4）。在以与P上的I2相同的方式生成第二分量R2=[R6，R7，R8，R9]=[I2，I3，I8，I7]之后，初始顶点、所有相交顶点已经被访问并且算法终止。3.1. 简并尽管其有利的简单性，一个严重的限制，例如，如果图中的P3。 5a是检测为交叉点，因此插入为交叉点对于顶点，扰动方法可以根据扰动方向产生不同的解。在前面的例子中，将P3稍微移向Q的内部，得到一个有五个顶点的多边形（见图5b），任何相反方向的扰动都会产生一个有两个三角形分量的相交多边形（见图5c）。这使得扰动方法不确定，不适合各种应用，如数值模拟[5]。4. Greiner-Hormann算法的推广受Kim和Kim[3]工作的启发，我们发现Greiner-Hormann算法的上述限制事实上，我们的扩展主要需要在算法的标记阶段对相交顶点进行更精细的分析，前提是在相交阶段检测并正确处理退化相交。我们的修订标签策略使用本地方向测试，以确定和标记的一个子集的所有交叉点的交叉路口。然后，这些被交替地标记为入口点和出口点，与原始Greiner-Hormann算法完全相同4.1. 相交相位我们算法的第一阶段基本上与Greiner-Hormann算法相同，因为它找到P和Q的所有交点，但我们必须适当地为此，我们针对Q的半开边测试P的半开边以寻找潜在的交叉点，从而避免在顶点处检测到可能的交叉点两次。在不损失推广的情况下，让我们考虑半开边[P1，P2）和[Q1，Q2），并区分两种情况。如果两条边不平行，则存在由两条边定义的两条线的唯一相交点I=（1 −α）P+αP=（1 −β）Q +βQ，α，β∈R，如果一个顶点同时进入P和Q，那么结果将是不正确的，因为在这种情况下，交替地将相交顶点标记为入口和出口的策略给出了错误的标记虽然这个问题可以通过稍微扰动任何这样的退化相交来解决，且边相交于I，当且仅当0≤α，β1。<参数α和β分别描述I在P1和P2之间以及在Q1和Q2它们可以被确定为4E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）100007=PQPQ（）下一页a b c d见图6。两条非平行边[P1，P2）和[Q1，Q2）的可能相交类型：X相交（a）、T相交（b，c）和V相交（d）。请注意，P2和Q2用空心圆表示，以强调我们考虑的是半开边。a B C图第七章 两条 共线边[P1，P2）和[Q1，Q2）的可能重叠类型：X重叠（a）、T重叠（b，c）和V重叠（d）。αA（P1，Q1，Q2），A（P1，Q1，Q2）− A（P2，Q1，Q2）• T重叠：如果α0或α≥1，且0β 1，则我们将P1的一个拷贝添加到Q，与P1相连。<<<同样，Q1的一个拷贝，A（Q1，P1，P2）β=A（Q， P， P）− A（Q， P， P），（1）如果β<0或β≥1，且0 <α <1，则将Q 1加到P上。• V重叠：如果α=β=0，则P1=Q1，并且我们将P1与Q1联系起来。哪里112212同样，我们不考虑涉及P2或Q2的重叠情况，A（P， Q， R）=（Qx-Px）（Ry-Py）-（Qy-Py）（Rx-Px），是计算三角形[P，Q，R]的有符号面积的两倍的函数。注意，只要[P1，P2）和[Q1，Q2）不平行，则（1）我们对可能的交叉口类型进行了分类，如图所示。第六章：• X相交：当且仅当0 α，β 1时，这种非退化相交发生<<。在这种情况下，我们将I添加到和， 并使用邻居指针链接两个副本，如[1]所述。• T-交：如果α=0且0β 1，则P1位于边[Q1，Q2]上，但不与Q1或Q2重合。<<在本例中，我们将P1的一个副本添加到Q，并将其与P1链接。同样，若β=0且0α 1，则Q1加到P上并与Q1<<• V-相交：如果α=β=0，则两条边相交于P1=把P1和Q1联系起来。我们不考虑涉及P2的退化相交情况，因为只要我们移动到P的下一个边[P2，P3），它们就会被检测到，这同样适用于涉及Q2的退化情况。如果两条边是平行的，那么它们可以相交，或者更确切地说，在-如果它们共线，即如果A（P1，Q1，Q2）= A（P2，Q1，Q2）= A（Q1，P1，P2）= A（Q2，P1，P2）= 0.在这个假设下，我们可以表示Q1相对于[P1，P2），P1相对于[Q1，Q2），Q1=（1 −α）P1+αP2，P1=（1−β）Q1+βQ2，参数α和β可以确定为：α=（Q1−P1，P2−P1），β=（P1−Q1，Q2−Q1），原因同上。在执行我们算法的第一阶段之后，保证和的所有交点都发生在公共交点顶点处，这些交点由相邻指针链接，或者沿着公共线段，这些线段现在表示为两个中的公共边P和Q，其公共相交顶点作为端点。图8示出了示例。4.2.标记阶段如在Greiner-Hormann算法中如果假设P和Q的所有交点都是非退化的X-交点，那么标记这些顶点是简单的，因为入口交点顶点后面总是跟着出口交点顶点，反之亦然（见第3节）。然而，退化交叉点需要对每个交叉点顶点周围的局部情况进行更仔细的调查。为此，让我们首先回忆一下，如果A（Q，P1，P2）>0，则点Q位于边[P1，P2]的左侧，如果A（Q，P1，P2）0，则点Q位于边[P1，P2]的右侧<如果我们现在考虑两个相邻的边[P1，P2]和[P2，P3]，则 我们可以通过计算来确定Q是位于多边形链（P1，P2，P3s1=A（Q，P1，P2），s2= A（Q，P2，P3），s3= A（P1，P2，P3）如图所示，区分三种情况。 九：• 左转：如果s3>0，则链在P2处左转，如果s1>0且s2>0，Q位于（P1，P2，P3）的左边，如果s10或s20，Q位于（P1，P2<<（P2−P1，P2−P1）（Q2−Q1，Q2−Q1）• 直：如果s3=0，则sign（s1）= sign（s2），Q位于左侧其中，·，·表示R 2中的标准点积。 我们对可能的重叠类型进行分类，类似于上面的交叉类型，如图所示。第七章：• X重叠：当且仅当0α，β1时，这种类型的重叠发生<<在这种情况下，我们将P1的一个副本添加到Q，与P1链接，Q1到P的拷贝，与Q1相连如果s1> 0，则为（P1，P2，P3）的 ;如果s1 <0，则为右。• 右转：如果s30，则链在P2处右转，并且如果s1>0或s2>0，则Q位于（P 1，P2，P3）的左侧，如果s10和s20，则Q位于（P1，P2<<<显然，为了简化代码，直多边形链的情况可以包括在其他两种情E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）1000075况中的6E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）100007a B见图8。 执行相交阶段之前（a）和之后（b）的两个多边形示例。请注意，我们在（b）中重新编号两个多边形的顶点以简化符号该算法检测九个公共相交顶点（），并且P和Q的两个公共段现在被表示为边[P2，P3]=[Q5，Q6]，[P8，P9]=[Q12，Q13]。a B C图第九章多边形链（P1，P2，P3）的左侧（浅灰色）和右侧（深灰色）区域，用于三种可能的情况：左转（a）、直行（b）和右转（c）。a B C图10. 在第一阶段之后，在交叉点I周围没有重叠的可能的局部配置：交叉（a）和反弹（b，c）。现在设I是P的一个交点，前面是P−，后面是P+。作为第一阶段的结果，我也是一个Q的顶点与邻居Q−和Q+。然后我们区分两种可能的情况。如果与I相邻的四条边不重叠，则P在I处相对于Q的局部行为可以分类为如图2所示。 10点整：• 交叉：如果Q−和Q+位于（P−，I， P+）的不同侧，则P在I处与Q相交，我们将I标记为相交。• 跳跃：如果Q−和Q+位于（P−，I， P+）的同一侧，则P在I处不与Q相交，我们将I标记为反弹。对于图8 b中的示例，该分类方案将P7、P13、P14标记为交叉，将P5、P11标记为弹跳（见图8 b）。 12 a）。情况稍微复杂一点，如果我是一个共同的部分。如果P的边[I， P+]与Q重叠，那么它要么等于[Q-，I]要么等于[I， Q+]，因为所有公共段都表示为相位1之后的公共边。因此，这种情况可以通过检查P+本身是否是一个相交顶点并链接到Q-或Q+来检测，并且类似的测试显示P的边[P-，I]是否与Q重叠。考虑到这些因素，我们可以区分图11所示的五种情况，以描述P在I周围相对于Q的局部位置：• 左/开：如果P+连接到Q+（或Q−），Q−（或Q+）位于（P-，I， P+）的右边，则P从Q的左边变为在I处的Q上。• 右/开：如果P+连接到Q+（或Q-），Q-（或Q+）位于（P-，I， P+）的左边，则P从Q的右边变为在I处的Q上。• 开/开：如果P+连接到Q+（或Q-），P-连接到Q-（或Q+），则P在Q上I的两侧。• 在/左：如果P−与Q−（或Q+）相连，Q+（或Q−）位于（P−，I， P+）的右边，则P从在Q上变为在I处的Q的左边。• 开/右：如果P−连接到Q−（或Q+），并且Q+（或Q−）位于（P-，I， P+）的左边，则P从在Q上变为在I处在Q的右边。在此分析之后，所有相交顶点 的P 与相邻重叠边形式 多边形路口链I=（I1，I2，. . . ，Ik），其中k> 1，其中I1被标记为x/on，I2，. . . ，Ik−1被标记为on/on，而Ik被标记为on/y，其中x，y∈ {left，right}。每个多边形相交链I可以分类如下：• 延迟交叉：如果x/=y，则P在I处与Q交叉。 在这种情况下，我们标记交点I1，. . . ，Ik−1为弹跳，Ik为穿越。• 延迟反弹：如果x=y，则P在I处不与Q相交，并且我们标记所有相交顶点I1，. . . ，我认为是弹跳。请注意，在延迟交叉的情况下，我们实际上可以将I中的任何相交顶点标记为交叉，只要I中的所有其他顶点都标记为反弹。对于图8中的示例，上述策略识别出在（P8，P9）处的延迟交叉和在（P 8，P 9）处的延迟交叉。E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）1000077PPQPQPP=++a b c d e图十一岁在第一阶段之后，在P关于Q的相交顶点I周围具有重叠的可能局部构型：左/上（a）右/上（b），上/上（c），上/左（d），上/右（e）。a B见图12。第二阶段（a）之后的图8示例。该算法将相交顶点标记为crossing（）或bouncing（），并将相交顶点标记为进入（）和退出（）点。算法的第三阶段最终创建相交多边形（b）。a b c d图十三. 一些特殊情况的例子。如果一个多边形组件仅在阶段一（a）之后由相交顶点组成，那么我们将第一个非相交顶点的中点添加到第二个相交顶点的中点。重叠边到多边形，因为第二阶段中的入口/出口分类需要初始的非相交顶点。对于（a）中的两个多边形，结果具有一个非简单分量R=[R1，. ，R9]（b）.如果某个面组件在标注阶段之后不包含任何交叉折点，则该组件不相交另一个多边形（c），或者它包含或包含在另一个多边形（d）的分量中，然后将内部分量添加到R。在（P2，P3）处放置弹跳，并因此将P9标记为交叉和P2，P3，P8作为弹跳（见图1）。 12 a）。一旦相交顶点已经被标记为交叉-ing或bouncing，我们可以简单地将这些标签复制到Q的相交顶点，因为Q在相交顶点I处与P相交当且仅当与I相交。交叉顶点的标记最终如第3所述通过跟踪两个多边形的所有组件并标记相对于另一个多边形内部的入口和出口对于图8中的示例，该算法将顶点P7、P13、Q2、Q9标记为入口点，并且将顶点P9、P14、Q7、Q12标记为出口点（参见图8）。 12 a）。请注意，最终标记阶段需要至少一个顶点每个多边形分量的每个多边形分量都是不相交的，使得可以明确地执行内侧/外侧测试，这在像图1为了解释如何克服这个问题，让我们假设在执行我们算法的第一阶段之后，P的某个分量P完全由相交顶点组成，并区分两种情况。如果P的所有边表示公共线段，则P和Q的某个分量Q包围相同的区域，并且我们可以模拟：层加P=Q 作为相交多边形R的分量，如果并且仅当两个组件都是孔或者两个组件都不是孔时。否则，P的相交顶点中的至少一个不是on/on顶点，并且因此与边相邻，比如[Pi， Pi+1]，不与Q重叠。 因此，我们可以添加中点P（PiPi1）/2作为P的临时顶点，并将其用作入口/出口分类的初始非相交顶点。4.3.追踪阶段用于创建相交多边形R的算法的第三阶段与原始Greiner-Hormann算法相比基本上保持不变唯一的区别是，每个结果组件的生成开始于和的交叉交点I，我们像往常一样遍历，如果I是入口点则向前，否则向后，但这次直到我们到达P的具有相反入口/出口标记的顶点，并且在切换到Q之后同样如此。在没有退化交叉点的情况下，这相当于继续到下一个交叉点，但通常我们可以在切换多边形之前通过一个或多个反弹交叉点。对于图12b中的例子，我们因此从P7开始，向前遍历P，直到我们到达P9=Q12，然后沿着Q向后直到Q9=P13，依此类推。如果P的某个分量P不包含任何交叉，截面顶点，那么我们遇到了图13c和13d所示的一种特殊情况，可以如下处理。 设P是P的一个不相交的顶点或一条边的中点不与Q重叠。当且仅当P位于Q内，则整个分量P也是，我们把它作为R在这种情况下相同的策略适用于Q不包含任何交叉相交顶点，并通过ex-8E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）100007RQ-Pa b c d图14. 两个多边形（a）的示例，对于这两个多边形，没有顶点分裂的算法生成具有一个分量R1=[R1，. . . ，R7]，它包含一个重复顶点R2=R6（b）.在对顶点对（P， Q）=（P3，Q2）进行分裂，设置入口/出口标记，并连接新的顶点Pr和Qr（c）之后，算法的第三阶段生成两个简单分量R1=[R1，R2，R3]和R2=[R4，R5，R6，R7]的正确结果（d）。在所有可能的情况下，很明显，即使在嵌套孔的情况下，该过程也给出了正确的结果4.4.改进和推广与Greiner-Hormann算法相反首先，可以有三个或三个以上连续的共线顶点的链，并且除了这样的链的第一个和最后一个顶点之外的所有顶点都可以省略而不修改结果的正确性。一个例子是图 中 的交叉多边形。12 b，其中顶点R3、R9和R11应该被删除。一般来说，当且仅当A（R-，R， R+）= 0时，顶点R应该被移除，这可以在后处理步骤中完成，该步骤访问结果的每个顶点一次。第二，可能发生顶点在结果多边形中出现两次，如图14b所示。然后，多边形应该在这样的顶点处分成两部分，以便使所有组件简单。请注意，这种情况只能发生在一个反弹的相交顶点，其中P的相邻边位于Q内，反之亦然。为了检测这些情况，我们扩展了第二阶段的最终标记阶段，以标记所有弹跳顶点 其位于入口和出口点之间作为分裂候选者。对于图14a中的示例，分裂候选是弹跳顶点P3、P4、Q2和Q3，但不是P6、P9、Q5和Q8。在标记之后，我们遍历P的分裂候选，如果我们遇到一个候选P，其邻居Q已被标记为Q的分裂候选，我们准备这个顶点对（P，Q）的分裂。为此，我们在P之后插入P的一个拷贝Pr到P中，对于Q也是如此，如图14 c所示。然后将P和Q标记为出口点，将Pr和Qr标记为入口点，并将所有四个顶点标记为交叉点，以便它们可以作为在第三阶段生成相交多边形的初始顶点。最后，我们需要把它们连接起来正确的方式。如果P在P处的局部取向和Q在Q处的局部取向不同，即，sign（ A（P−，P， P+））/= sign（ A（Q−，Q， Q+）），如图14c中的例子，那么我们保持P和Q和链接Pr与Qr。否则，我们将P与Qr联系起来，将Q与Pr联系起来。第三，结果可能包含虽然这也可以在后处理步骤中完成，但优选的是：能够提前避开他们事实上，我们实现这两个mi-也不修改我们算法的第二阶段中的标记策略，这是从[14]中的观察中得到启发和调整的。一方面，在对相交链I =（I1，I2，. . . ，Ik），我们将I1和Ik标记为延迟交叉或延迟弹跳的端点，并且将相交顶点I2，. . . ，我k 1、像跳。另一方面，在跟踪和设置进入/退出标记时，我们以与常规交叉交叉点相同的方式标记延迟反弹的端点，而延迟交叉点的端点标记为ei。两者都作为入口或两者都作为出口。此外，我们将退出延迟交叉的第一个顶点和进入延迟交叉的最后一个顶点标记为交叉。在延迟反弹的情况下，我们将两个端点标记为交叉，当且仅当adjaP的中心边位于Q内部，反之亦然。类似于上面的顶点分裂，这需要在遍历期间识别交叉候选项，并在之后标记匹配候选项。 由于遍历从非相交顶点开始，因此从不在相交链的内部顶点，因此相交链的两个端点总是成对访问，并且很容易区分第一个端点和最后一个端点。如图2所示。图15和16 c表明，这种改进的标记策略能够有效地去除胶合边缘，并且对P和Q的顺时针或逆时针方向分量、进入或退出延迟交叉以及内部或外部延迟反弹的所有可能组合的详尽检查表明，该策略正确地处理了所有情况;详见[14]。最后，我们注意到，就像原始的Greiner-Hormann al-出租m[1]一样 P和Q经过一些小的修改。关键的变化是在跟踪阶段反转遍历方向，并沿着多边形从出口点向前行进到入口点，从入口点向后行进到出口点。此外，整个组件必须添加到R，如果它们位于外部而不是内部的其他多边形，和分裂顶点和标记的延迟交叉和延迟反弹的端点的规则必须颠倒。可以进行类似的改变以用于确定差异P\QQ\P。5. 示例我们用C++实现了该算法，并对各种输入多边形进行了广泛的测试。代码和所有示例都是可 在 第 二 作 者 的 网 页 www.example.com 上 获 得https://www.inf.usi。ch/hormann/polyclip/.E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）1000079a B C图15. 对于来自图13a的示例，改进的标记策略不仅针对交叉顶点，而且针对交叉链的所有端点设置进入/退出标记，对于P（a）和Q（b），使得算法的第三阶段生成具有两个分量R1=[R1，R2，R3]和R2=[R4，R5，R6]的结果多边形（c）。a B C图16. 两个多边形（a）的示例，算法为其生成具有胶合边[R1，R2]和[R6，R1]的退化结果（b）。两者都被改进的标记策略（c）去除。a B C图17. 一条封闭的五阶希尔伯特曲线（a）与其旋转后的副本（b）相交，在右上方对齐，得到116个简单多边形（c）。a B C图18. 该算法还处理具有多个嵌套组件（a，b）的复杂输入多边形，并正确计算交集（c）。图17中的第一个例子是退化交叉点的真实应力测试，因为每个具有820个顶点的两个输入多边形内插规则32× 32网格的所有节点。该算法的第一阶段发现14个非退化和1010个退化相交（176个T-和432个V-相交，以及208个T-和194个V-重叠），并为两个多边形添加206个顶点。第二阶段检测42个弹跳交叉点和396个延迟交叉点，并分裂21个弹跳顶点对。第三阶段创建116个具有804个顶点的简单多边形，并且通过消除共线顶点的后处理步骤来移除其中的164个。图中的第二个例子。 18说明了该算法还处理具有多个嵌套组件的复杂输入多边形，内部由奇偶规则定义[2]。在这次考试中有46个非退化和21个退化交叉点Ple，后者对应于4个弹跳交叉顶点、2个延迟交叉和5个延迟弹跳。没有反弹顶点对需要被分割，并且在移除3个共线顶点之后，结果由14个具有64个顶点的简单多边形组成最后两个例子证明了需要能够处理退化的情况下，在现实世界中的应用。在图19中，我们显示了代表瑞士一个州（5个组成部分，1322个顶点）和一个自然公园（1个组成部分，2602个顶点）边界的多边形。特写镜头放大到算法发现的交叉点和延迟交叉点（右）。将相交结果（1240个顶点）的面积与自然公园的面积进行比较，发现46.6%的公园属于这个州。在图20的最后一个例子中，我们考虑了代表阿尔伯克基地区美国学区的多边形，按学校评级进行排名。我们首先计算5个最佳多边形的并集10E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）100007图19. Gruyère Pays-d 'Enhaut地区自然公园边界（虚线和点顶点）与奥布拉州边界的交叉点（阴影部分）弗里堡（实线和圆圈顶点），两个边界相交的区域的特写。(Data本例中使用的是www.openstreetmap.org，在开放数据库许可证（ODbL）下提供。a b c d图20. 为了找到五个小学学区（a）、三个中学学区（b）和两个高中学区（c）的公共区域，我们首先计算它们各自的并集，最后计算它们的交集（d）。排名最好的小学（需要运行算法四次，每次运行时添加一个多边形），同样，对于3所排名最好的中学和2所排名最好的高中，结果是多边形E，M和H。然后我们计算E与M的交，并进一步将结果与H交。 这最终给出了图20d中的阴影多边形，它表示 在所有三个教育级别上都有机会进入顶级学校的社区。6. 讨论和结论裁剪平面多边形是几个领域的核心，Weiler和Atherton[8]指出需要一种通用算法，能够裁剪具有多个组件和孔的凸多边形和凹多边形。他们的算法是第一个具有此功能的算法，并且与我们的工作类似，因为它包括一个交叉点和一个追踪阶段，基本上和我们的一样。Weiler-Atherton算法没有标记阶段，因为它假设所有多边形组件的顶点都是一致的，即外部边界是顺时针的，而洞是逆时针的通过添加标记阶段，Greiner和Hormann[1]设法避免这种对顶点顺序的限制，并推广了然而，这两种算法都不能处理退化相交的情况，这在许多应用中是一个严重的限制Weiler相反，我们表明，退化相交的情况下，也可以有效地处理通过仔细细化标记阶段的Greiner-Hormann算法。我们的新标记阶段（4.2和4.4节）是有效的，因为它依赖于严格的局部操作以及检测和区分少量病例。实际上，这个阶段的运行时间是O（k），其中k是P和Q之间的交集数，根据根据我们的经验，它只需要大约两倍的时间，Greiner-Hormann算法的最终标记阶段。在此阶段结束时，正确标记所有入口/出口标记所需的唯一全局信息是内部/外部测试，该测试应用于每个多边形组件的一个非相交顶点，通常需要O（n）操作，其中n是另一个多边形的顶点注意，Kim的算法E.L. 福斯特，K。Hormann和R. T.Popa/Computers Graphics：X 2（2019）10000711a b c d见图21。 我们的算法正确处理自交多边形，只要自交不位于其他多边形（a），但可能会失败，否则（b，c，d）。和Kim[3]，也扩展了总的来说，我们的算法只是稍微慢于原始的正如Greiner和Hor- mann[1]所提出的，我们采用强力方法进行相交阶段，并通过简单地测试所有P的n条边对Q的所有m条边，这显然需要当k∈O（nm）时，在最坏的情况下是最好的.然而，如果交叉点的数 量 很 小 ， 那 么 用 平 面 扫 描 方 法 在 O （ （ n+m+k ） log（n+m））时间内计算它们更有效[15]。后一种做法是Vatti当k∈O（n+m）[16，17]时，我们的实验证实了这些时间，以及[1]中的时间，这表明Greiner-Hormann和我们的算法都后者不必计算。此外，我们的算法在中等大小的多边形（mn≤1 000 000，k≤10 000）的情况下是最快的，这很可能是因为非常高效的标记和跟踪阶段，这两个阶段都需要不到1ms。案子很有可能，该算法可以进一步加快采用平面扫描方法在相交阶段，但它仍然是未来的工作来验证这一猜想。通过采用Liu等人[4]的思想，可能会进一步提高记忆效率，他们建议维护一个交叉点的双重链表，而不是将它们插入P和Q中。我们的算法的唯一限制是退化相交，涉及自交点。事实上，如果一个多边形的自交位于另一个多边形的边上或与另一个多边形的顶点重合，那么算法可能会失败（见图21）。然而，这个问题可以通过在预处理步骤中解决自相交来避免，例如通过将图21中的P分成两个三角形。它仍然是未来的工作，以找到一个更优雅的解决方案，上述限制，并扩展本文提出的想法，以三维设置，使他们可以用于布尔实体建模、模型修复和其他几何处理应用中的操作[11]。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作补充材料与本 文相关 的补充资 料可以 在doi：10.1016/j.cagx.2019.100007引用[1] 放大图片作者：Greiner G，Hormann K.任意多边形的高效裁剪。 ACM TransGraph1998;17（2）：71-83.[2] Foley JD，van Dam A，Feiner SK，Hughes JF.计算机图形学：原理与实践。Addison-Wesley系统编程系列月2 Reading：Addis-on-Wesley;1990.[3] 李文，李文，等.一种改进的多边形裁剪算法.北京：科学出版社，2001.计算机辅助应用2006;3（1-4）：447-56.[4] Liu Yk，Wang XQ，Bao SZ，Gomboši M，Zhaolik B.多边形裁剪和求交、求并的算法. Comput Geosci 2007;33（5）：589-98.[5] Farrell PE，Piggott MD，Pain CC，Gorman GJ，Wilson CR.通过超网格构造实现非结构网格之间的守恒插值。 计算方法应用机械工程2009;198（33-36）：2632-42.[6] Simonson LJ.工业强度多边形裁剪：一种新的算法及其在VLSI CAD中的应用.计算机辅助设计2010;42（12）：1189[7] 谢蒂诺A球面拓扑学中的多边形相交：在板块构造中的应用。ComputGeosci1999;25（1）：61-9.[8] Weiler K ， Atherton P. 使 用 多 边 形 区 域 排 序 去 除 隐 藏 表 面 。 SIG- GRAPHComput Graph1977;11（2）：214-22.[9] 华帝BR。多边形裁剪的通用解决方案。Commun ACM 1992;35（7）：56-63.[1