计算机图形中简单多边形的切环剖分方法

摘要

计算机图形中简单多边形的切环剖分方法：1.连接多边形的第1顶点与多边形的外包菱形的4个顶点；对于多边形的第n顶点，n＝1；2.令n＝n+1，若第n顶点与第1顶点重合且第n-1顶点与第1顶点已连接为一条边，则执行3；否则，2.1.以自第n-1顶点至第n顶点的有向边为探头，若探头与某一附加边重叠，则删除重叠的附加边并进行共线处理，返回2；否则，2.2.若探头穿越某一附加边，则分别处理探头两侧的三条边并删除该附加边，重复2.2；若第n顶点与第1顶点重合，则分别处理探头两侧的三条边后执行3；若探头有前方共线顶点，则进行共线处理，否则进行常规处理；返回2；3.校正多边形的方向。

说明书

技术领域：

本发明应用于计算机图形处理、模式识别、曲面逼近以及有限元网络生成等方面的数据处理。

背景技术：

多边形剖分问题在许多领域都有非常重要的实用价值。目前所提出的剖分方法大致有如下几种：三角剖分、四边形剖分(见《计算几何-算法与应用》，清华大学出版社，2005，第68页)、或凸剖分(见《C语言中的计算几何》“Computational geometry in C”，机械工业出版社，2005，第58页)，虽然目前已知的三角剖分的最优算法可以为线性时间的，但是却非常复杂，而且是离线的。其他剖分方法的运行时间复杂度都高于O(N)。而且，凸剖分则可能需要添加额外的steiner点及额外的边(见《计算几何-算法与应用》，清华大学出版社，2005，第232页)。

因此，寻求一个更为简便的，特别是在线的，线性时间剖分方法一直是计算几何领域的开放性难题(The Open Problems Project，http://maven.smith.edu/～orourke/TOPP/P10.html#Problem.10)。

2007年开始，本人开始着手这一问题的研究，经过两年多的探索，终于发明了一种在线的计算机图形中简单多边形的切环剖分方法，就是将简单多边形剖分为一系列凸环(每个顶点可以在环上或内部与所有其他顶点直线连接)和凹环(仅有一个顶点可以在环上或环内部与所有其他顶点直线连接)，形成多边形的一种双态剖分(dimorphic partition)，其最坏情况下的运行时间为O(N)的。而多边形的切环剖分一旦完成，可以直接将凹环和凸环在线性时间内转化为三角剖分。

发明内容：

技术问题：本发明的目的是提供一种计算机图形中简单多边形的切环剖分方法，随着多边形顶点的逐一嵌入，在线的、以线性时间完成多边形的剖分。

技术方案：本发明计算机图形中简单多边形的切环剖分方法采用的技术方案如下：

步骤1.1：建立XOY平面坐标，在待剖分的多边形的外部设置一个能够包容多边形的菱形，菱形的4个构造顶点的坐标分别是(a，0)、(0，a)、(-a，0)与(0，-a)，a为大于水平尺度与竖直尺度之和的实数，水平尺度为多边形最小外包矩形的左侧或右侧X坐标的绝对值的较大者，竖直尺度为多边形最小外包矩形的上侧或下侧Y坐标的绝对值的较大者；菱形构成一个环，环以逆时针方向为下游方向；以多边形上任一顶点作为第1顶点，逐一将第1顶点与菱形的4个构造顶点连接，将菱形分解为4个较小的环，作为起始的剖分集合；以多边形上与第1顶点相邻的两个顶点中任意一个作为第2顶点，假设以第1顶点与第2顶点顺序的走向为多边形的下游方向；

步骤1.2：沿着多边形的下游方向逐个将第n顶点嵌入剖分集合，n＝2，3，4，……，N，N+1，N为多边形的顶点个数，第N+1顶点与第1顶点重合；

步骤1.3：如果按照第1顶点、第2顶点、第3顶点、……、第N顶点至第1顶点的顺序形成的多边形的走向是顺时针方向的，则对多边形的每个顶点进行方向逆转处理，即将原设定的上游相邻顶点修正为下游相邻顶点，将原设定的下游相邻顶点修正为上游相邻顶点；

上述的将第n顶点嵌入剖分集合的方法是：

步骤1.2.1：以自第n-1顶点至第n顶点的有向边为探头，若第n顶点与第1顶点不同，则执行步骤1.2.2；否则，若以第n-1顶点为起点的所有附加边中有一条附加边的终点是第1顶点时， 则多边形闭合，将此附加边更新为多边形的边，嵌入结束，所述的附加边是由任意两个不相邻的顶点形成的有向边；否则，

步骤1.2.2：以自第n-1顶点的位于探头右侧的第一条有向边为第1右首边，以第1右首边的下游边为第1链首，以探头的上游边为第1链尾，以i作为后续的计数器，i＝1，若第一条位于第1右首边的左侧的附加边与探头重叠，则以此附加边的下游边为共线边，并删除重叠的附加边，执行步骤1.2.6；否则，

步骤1.2.3：以第i链首、第i链尾分别作为第i链段的开头与结尾，所述的链段是一系列首尾衔接的有向边；若第i链段是单边形、凸链形或凹链形链段，则对第i链段进行链段夹挤确定探头对准边，并以所获得的对准边作为第i命中边，然后执行步骤1.2.5；若第i链段是左凹形，则执行步骤1.2.4；否则第i链段是右凹形，若探头与第i链尾的上游边相交，则以所述上游边作为第i命中边，执行步骤1.2.5，否则对以第i链首为链首、第i链尾的上游边为链尾的链段进行链段夹挤确定探头对准边，若存在对准边，则以对准边作为第i命中边，否则以第i链尾的上游边为第i命中边，然后执行步骤1.2.5；上述单边形链段的链尾是链首的下游边；上述凸链形链段的所有中间顶点的角度＜π，所述链段的中间顶点是链段上介于链首的起点与链尾的起点之间的所有顶点，所述顶点的角度是链段上以此顶点为衔接的两条相邻的有向边左侧的夹角；上述凹链形链段的所有中间顶点的角度≥π；上述左凹形链段除链首的终点的角度＜π，链段上的其余中间顶点的角度≥π；上述右凹形链段除链尾的上游边的起点的角度＜π，链段上的其余中间顶点的角度≥π；

步骤1.2.4：若探头与第i链首相交，则以第i链首为第i命中边，执行步骤1.2.5；否则，对以第i链首的下游边为链首、第i链尾为链尾的链段进行链段夹挤确定探头对准边，若存在对准边，则以对准边作为第i命中边，否则以第i链首作为第i命中边，

步骤1.2.5：若第i命中边的起点与探头共线，则以第i命中边作为共线边，执行步骤1.2.6；否则，分别以第i右首边、第i链首和第i命中边作为起始边、中间边和终止边，以无界方式对探头的右侧进行三边连环，再分别以第i命中边的下游边、第i链尾和探头作为起始边、中间边和终止边，以无界方式对探头的左侧进行三边连环；以三边连环后的第i命中边的新的下游边为第i+1链尾，若探头与第i命中边相交，则以第i命中边的逆向边的下游边为第i+1链首，以探头的逆向边的下游边为第i+1右首边，删除第i命中边，以i+1作为新的i，重返步骤1.2.3；否则，对以探头的逆向边为链首、第i命中边为链尾的链段进行链段修正，将新连接的自第n顶点的附加边作为右翼边，再对以第i+1链尾为链首、右翼边为链尾的链段进行链段修正，将新连接的自第i+1链尾的起点的附加边作为左翼边；分别以右翼边的下游边、左翼边和右翼边的上游边作为起始边、中间边和终止边，以无界方式对探头的前方进行三边连环从而确保探头的前方是三角形，嵌入结束；上述的链段修正的方法是：若链段是凸链形，则以链首为起环边、链尾为止环边进行双边连环，否则若链段是左凹形，则对以链首的下游边为新链首，链尾为新链尾所构成的新链段进行自上方式的凹链顺延使之变为单边形或凹链形，否则若链段是右凹形，则对以链首为新链首，链尾的上游边为新链尾的新链段进行自下方式的凹链顺延使之变为单边形或凹链形；结束链段修正；上述的双边连环的方法是：以止环边的上游边为环内边，连接起环边的起点与止环边的起点，以所形成的附加边作为封口边；若起环边是一条附加边且起环边足够长，且起环边的两侧的两个环在起环边被删除的情况下可以形成一个较大的凸环或在起环边的终点不是第1顶点的前提下形成一个较大的凹环，则可以删除起环边；同理，若环内边也是附加边且环内边足够长，且环内边的两侧的两个环在环内边被删除的情况下可以形成一个较大的凸环或在环内边的起点不是第1顶点的前提下形成一个较大的凹环，则可以删除环内边；双边连环结束；上述的起环边足够长是指起环边的长度至少是起环边的终点至止环边的起点的距离的一半或起环边的长度至少是封口边的长度的一半；上述的环内边足够长是指环内边的长度至少是起环边的起点至环内边的起点的距离的一半或环内边的长度至少是封口边的长度的一半；上述的凸环指的是在环内的所有顶点的角度＜π；上述的凹环指 的是在环内除了仅有三个相邻的顶点的角度＜π，其余所有顶点的角度≥π；

步骤1.2.6：分别以第i右首边、第i链首和共线边作为起始边、中间边和终止边，以有界方式对探头的右侧进行三边连环，再分别以共线边、第i链尾和探头作为起始边、中间边和终止边，以有界方式对探头的左侧进行三边连环，若共线顶点有下游方向新的附加边，则以此附加边作为后续的共线边；若第n顶点与第i命中边的起点重合，则第n顶点返至第1顶点而多边形闭合，协调探头与共线边的位置关系，嵌入结束；否则，对以探头逆向边的下游边为链首、共线边为链尾的链段获取中部边并作为右中边，然后以探头的逆向边为起环边、右中边为止环边进行双边连环，并连接第n顶点与共线顶点作为接续边，上述有向边的逆向边是端点与所述有向边相同而方向与其相反的边；对以共线边为链首、探头为链尾的链段获取中部边并作为左中边，以左中边为起环边、接续边为止环边进行双边连环，嵌入结束；上述的对链段获取中部边的方法是：若链段为左凹形，则以链尾的上游边为中部边，并以链首为起环边、中部边为止环边进行双边连环，获取结束；否则若链首的下游边是链尾的上游边，则以链首的下游边为中部边，获取结束；否则以链首的下游边为起环边、链尾为止环边进行双边连环，以双边连环后链首的新的下游边为中部边，获取结束；

上述的三边连环的方法是：

步骤1.2.5.1：对以起始边为链首、中间边为链尾的链段进行链段修正，若修正后起始边的起点位置有新的附加边，则以新的附加边作为新始边，否则以起始边为新始边；再对以中间边为链首、终止边为链尾的链段进行链段修正，若修正后中间边的起点位置有新的下游方向的附加边，则以所述附加边作为新中边，否则以中间边为新中边；若起始边与中间边相同或中间边与终止边相同或新中边起点的角度≥π则结束；若两次修正结果都是凹链形，则执行步骤1.2.5.2；否则，若三边连环方式是有界方式，则结束；否则是无界方式，若两次修正结果都是单边形，则以新始边为起环边、终止边为止环边进行双边连环，结束；若前一次修正结果是单边形，后一次修正结果是凹链形，对以新中边为链首、终止边为链尾的链段进行自上方式的凹链顺延，结束；否则，前一次修正结果是凹链形，后一次修正结果是单边形，对以新始边为链首、新中边为链尾的链段进行自下方式的凹链顺延，结束；

步骤1.2.5.2：以新中边为第1奇折边，新始边的起点为上端点，终止边的起点为下端点，j为循环计数器，j＝1，进行两个凹链的交替顺延处理；

步骤1.2.5.3：若三边连环是无界方式，且第j轮奇折边的起点是下端点或第j轮奇折边起点的角度≥π，结束；若三边连环是有界方式且第j轮奇折边的上游边的起点是上端点则结束；否则对以第j轮奇折边为链首、终止边为链尾的链段，以自上方式进行凹链顺延，并以新连接的附加边作为第j轮偶折边；

步骤1.2.5.4：若三边连环是无界方式，且第j轮偶折边的起点是上端点或第j轮偶折边起点的角度≥π，结束；若三边连环是有界方式且第j轮偶折边的下游边的起点是下端点则结束；否则对以新始边为链首、第j轮偶折边为链尾的链段，以自下方式进行凹链顺延，并以新连接的附加边的下游边作为第j+1轮奇折边；以j+1作为新一轮的j，执行步骤1.2.5.3；上述的凹链顺延的方法是：若是自上方式的顺延，则以链首的上游边为观察边，否则以链尾的下游边为观察边；以观察边的起点为观察点，进行链段夹挤确定观察点的可见范围，并以可见范围的上游起始位置的有向边作为上游类切边，可见范围的下游终止位置的有向边的下游边作为下游类切边；对于自上方式的顺延，以观察边为起环边、下游类切边为止环边进行双边连环，对于自下方式的顺延，则以上游类切边为起环边、观察边为止环边进行双边连环；双边连环后，若止环边的上游边的起点与起环边的起点相同，则自起环边的起点至止环边的起点新构成的链段是单边形，否则是凹链形；

上述的链段夹挤确定探头对准边的方法是：

步骤2.1：以链首为顺序第1边、链尾的上游边为逆序第1边，k为循环计数器，k＝1，

步骤2.2：若顺序第k边的终点位于探头左侧而顺序第k边的起点位于探头右侧或与探头共线，则以顺序第k边为对准边，结束，否则若逆序第k边的终点位于探头左侧而逆序第k边的起点位于探头右侧或与探头共线，则以逆序第k边为对准边，结束，否则若逆序第k边的终点与探头共线而逆序第k边的起点位于探头右侧，则以逆序第k边的下游边为对准边；否则若顺序第k边与逆序第k边相同或顺序第k边是逆序第k边的上游边，则找遍整个序列也没有对准边，结束；否则若链段是凹链形，且顺序第k边的起点位于探头的左侧或逆序第k边的终点位于探头的右侧，则不可能有对准边，结束；否则以顺序第k边的下游边为顺序第k+1边、逆序第k边的上游边为逆序第k+1边，以k+1作为新的k，执行步骤2.2；

上述的链段夹挤确定观察点的可见范围的方法是：

步骤3.1：以链首为顺序第1边、链尾的上游边为逆序第1边；若观察点在顺序第1边左侧，可见范围的上游起始位置的有向边为顺序第1边；若观察点在逆序第1边左侧，可见范围的下游终止位置的有向边为逆序第1边；若可见范围的上、下位置都已确定，则结束；否则以k为循环计数器，k＝1，

步骤3.2：以顺序第k边的下游边为顺序第k+1边、逆序第k边的上游边为逆序第k+1边，以k+1作为后续的k；若观察点位于顺序第1边左侧但不在顺序第k边左侧，则下游终止位置的有向边为顺序第k-1边，结束；否则若观察点同时位于顺序第1边左侧与逆序第k边左侧，则下游终止位置的有向边为逆序第k边，结束；否则若观察点同时位于顺序第k边左侧与逆序第1边左侧，则上游起始位置的有向边为顺序第k边，结束；否则若观察点位于逆序第1边左侧但不在逆序第k边左侧，则上游起始位置的有向边为逆序第k-1边，结束；否则执行步骤3.2。

有益效果：

1计算机图形中简单多边形的切环剖分方法是在线的处理方法

处理的方法是逐一将多边形的第1顶点V₁、第2顶点V₂、……、第N顶点V_N嵌入剖分集合，结束条件是第n顶点V_n重返第1顶点V₁，只要得到第1个顶点就开始剖分过程，无需等到获得所有顶点之后。

2计算机图形中简单多边形的切环剖分方法的时间复杂度为O(N)

在整个剖分过程中，循环重复的处理有：

第1层次的逐个嵌入多边形顶点V_n的主循环loopMain，包含：

第2层次的探头E_p与命中边H_ui相交时的边切割循环loopCut，进一步包含：

第3层次的探头E_p在链段上寻找命中边H_ui的求交循环loopHit，

第3层次的探头E_p两侧的一致凸或一致凹处理的连接循环loopLink；

第1层次的多边形的方向校正循环loopClockwise；

以上各种循环各自需要不同的运行时间：

2.1最外层的主循环loopMain在不考虑从属层次的情况下，运行时间复杂度为O(N)；

2.2第2层次的边切割循环loopCut的时间复杂度为比较复杂，对于不同顶点，探头所穿越的附加边的数量越多，运行时间越长；总的时间复杂度等于各个顶点切割次数的总和；依照本发明的方法，在特定情况下每嵌入一个顶点都要进行附加边切割(图24a～24i)，假定上顶点V_u有m_u条附加边、下顶点V_d有m_d条附加边，则最坏情况是m_u＝m_d＝m(若m_u≠m_d，对于多出的附加边，每完成一条附加边的切割至少需要嵌入两个顶点，使得时间复杂度减小)；设下顶点V_d为第n顶点，则在第n+1顶点V_n+1嵌入剖分集合完成后，新产生的可能被下一个顶点所形成的探头所穿越的附加边的数量最多为m/2+1(见图13a、13b，14a、14b双边连环的方法)，于是：

第n+1顶点V_n+1嵌入后总的切割次数为m次；

第n+2顶点V_n+2嵌入后总的切割次数为m+m次；

第n+3顶点V_n+3嵌入后总的切割次数为2m+m/2+1次；

第n+4顶点V_n+4嵌入后总的切割次数为2m+m/2+1+m/2+1次；

第n+5顶点V_n+5嵌入后总的切割次数为2m+m+2+m/4+1次；

第n+6顶点V_n+6嵌入后总的切割次数为2m+m+2+m/4+1+m/4+1次；

……

第n+2m顶点V_n+2m嵌入后总的切割次数为$2\underset{i=0}{\overset{m}{\Sigma }}\frac{m}{2^i}+2m-2=2(2-2^{-m})m+2m-2<6m$次；

后续更多的顶点嵌入后总的切割次数则不再受入前被切割边数m的影响；

∵总的顶点数为N≥[(2m+1)+(2m+2)-1]+2m＝6m+2，m≤(N-2)/6＜N/6，6m＜N；

∴边切割循环loopCut的时间复杂度在最坏情况下是O(6m)＝O(N)；

2.3第3层次的求交循环loopHit采用链段夹挤确定探头对准边的方法(图18a～18c)，每次运算时间由链段上顶点的个数决定的，在未发生切割处理的情况下，总的时间复杂度是所有被切开的环上顶点的个数的累加，即是O(N)；但在反复切割的情况下，每当一个大环被分解为两个较小环时，若被分解出的小环的顶点数不一样，则所耗费的运算次数仅与两者中顶点数较少的一个环有关，且是其顶点个数的两倍(链段夹挤每循环一次需要分别进行顺序与逆序判断各一次)，而与顶点数较多的环无关，因此，最坏情况是两个小环各为原来大环顶点数的一半；当新嵌入的顶点进入某一侧小环时，求交循环loopHit需要对小环再度搜索，产生了附加的运算时间；设大环上的顶点个数为n，小环上的顶点个数为n/2，则大环上的求交运算次数最多为n，小环上的求交运算次数最多为n/2；同理，若小环被再度递进分解，则新增的运算次数最多为n/4，……，直到环上少于4个顶点而全部变为三角形，此后的顶点若是位于被递进分解的小环之内，则求交循环loopHit不再受之前大环顶点个数n的影响；于是，对于探头任一侧的小环，所有递进分解的小环的累加的求交循环次数总和为：

$\underset{i=1}{\overset{n}{\Sigma }}\frac{n}{2^i}=n(1-\frac{1}{2^n})<n,$

将其与大环的单独求交循环次数n相加，则求交循环次数总和＜2n；

∵将大环递进分解到不可以再分解时，至少需要另外n个顶点，则总的顶点数应该至少是大环上的n个顶点与递进分解的n个顶点之和，即2n≤N；

∴第3层次的求交循环loopHit的时间复杂度在最坏情况下也是O(2n)＝O(N)；

2.4第3层次的连接循环loopLink的时间复杂度，与环的形状以及是否被反复连接有关，对于形成凸环的连接，每次仅需常数的时间，而对于形成凹环的连接，则可能是常数的时间，也可能等价于形成凹环的顶点个数；在不发生凹环分解状况时，对于自上方式的凹链顺延，若下游类切边位于链尾(图16b)，则需要常数时间，若下游类切边位于链段中部(图17b)，则最坏情况下的定位的次数为链段的顶点个数；同样的原理也适合于自下方式的凹链顺延(图16c、17d)；因此，总的连接循环的时间复杂度为O(N)；而在发生了边被切割而造成环分解的状况下，总的运行时间可以划分为首次连接时间与重复连接时间，首次连接时间为O(N)，重复连接时间则因为大的凹环被分解为小的凹环而重复运算(这种重复运算包含了两个凹链交替顺延的情况，图15a、15b)；按照上述求交循环中的分析，当大环被分解成两个顶点个数相等的小环时需要运算的次数最多；于是，在最坏情况下，再度连接所需的总的运算次数为：$\underset{i=1}{\overset{n}{\Sigma }}\frac{N}{2^i}=N(1-\frac{1}{2^N})<N$

∴连接循环loopLink的时间复杂度为首次与重复连接时间之和：O(N)+O(N)＝O(N)；

2.5最外层的多边形方向校正循环loopClockwise，其方向逆转的运行时间复杂度为O(N)；

以上各种循环虽然处于不同的循环层次，但各种循环的次数是由多边形自身的几何关系决定的，不是由循环的层次决定的，而各种循环的时间复杂度的总和就是切环剖分法的时间复杂度；由于每种循环的时间复杂度都是线性的，因此，它们的和也是线性的，即切环剖分法的时间复杂度为O(N)。

3计算机图形中简单多边形的切环剖分方法比已知的其他线性时间剖分法更简单

1991年，由Bernard Chazelle发明的“简单多边形的线性时间剖分”Triangulating a SimplePolygon in Linear Time方法，发表在计算几何界的权威学术期刊《离散与计算几何》(Discrete&Computational Geometry，6(5)，第485～524页，1991)，该方法不仅相当复杂、难以理解，而且是离线的；

本发明的切环剖分法显然比Bernard Chazelle的方法简单易懂，容易实现；

4计算机图形中简单多边形的切环剖分方法可以实时处理顶点坐标为随机值的多边形

当简单多边形的顶点有规律的连续构成大段的凹链或凸链时，在某些部位有可能积累大量的附加边，使得后续的某一个顶点嵌入时需要花费相当长的时间进行切割处理；如果顶点坐标是没有规律的随机值，则切割处理被分散开来，这对于常规的图形处理是非常有利的，从而可以实现实时处理。

附图说明

图1是多边形的外包菱形Q₀的设定示意图。

图2是由第1顶点V₁所形成的初始剖分集合。

图3是顺时针方向的多边形的实例。

图4是探头E_p与附加边重叠的实例。

图5是单边形链段C_c1及起点为第n-1顶点V_n-1的全部有向边G_e(3或4个)的构成实例。

图6a、6b、6c与6d分别是凸链形、凹链形、左凹形与右凹形链段的示意图。

图7a、7b分别是右凹形链段获取命中边H_ui时的初始状态与右翼分解出的两边示意图。

图8a、8b分别是左凹形链段获取命中边H_ui时的初始状态与左翼分解出的两边示意图。

图9是探头E_p与命中边H_ui相交的实例。

图10是对探头E_p的前方进行三边连环构成2个附加边的实例。

图11是在探头E_p前方有共线点V_c时构成3个附加边的实例。

图12是第n顶点V_n重返至第1顶点V₁且命中边H_ui的起点是第1顶点V₁的实例。

图13a分别是在双边连环时，起环边R_u可以被删除形成一个较大的凸环实例；

图13b是在双边连环时，起环边R_u与环内边R_i皆可以被删除形成一个较大的凸环的实例；

图14a是在双边连环时，起环边R_u可以被删除形成一个较大的凹环的实例；

图14b是在双边连环时，环内边R_i可以被删除形成一个较大的凹环的实例。

图15a、15b是在三边连环时，分别以有界、无界方式进行左右交替的顺延处理的实例。

图15c是在有界方式的三边连环时，两次链段修正的结果是两个单边形的实例。

图15d是在无界方式的三边连环时，两次链段修正的结果是两个单边形的实例。

图15e是在无界方式的三边连环时，两次链段修正的结果分别是单边形、凹链形的实例。

图15f是在无界方式的三边连环时，两次链段修正的结果分别是凹链形、单边形的实例。

图16a、16b、16c分别是凸链形链段、左凹形链段、右凹形链段的链段修正的实例。

图16d、16e分别是链段修正过程中，单边链段链段、凹链形链段的不作处理的实例。

图17a、17b是自上方式的凹链顺延为新凹链形的结果。

图17c、17d是自下方式的凹链顺延为新单边形的结果。

图18a、18b分别是对凸链形链段、凹链形链段实施链段夹挤确定探头对准边的实例。

图18c是对凹链形链段实施链段夹挤确定探头对准边时，没有对准边的实例。

图19a是链段夹挤确定观察点的可见范围时，直接得到可见范围的实例；

图19b是链段夹挤确定观察点的可见范围时，一端由不可见变为可见的实例。

图19c是链段夹挤确定观察点的可见范围时，一端由可见变为不可见的实例。

图20a、20b是多边形polygon的完整切环剖分实例的初始设置；

图20c～20f是多边形polygon的第2顶点V₂～第3顶点V₃嵌入剖分集合的示意图；

图21a～21f是多边形polygon的第4顶点V₄～第10顶点V₁₀嵌入剖分集合的示意图；

图22a～22f是多边形polygon的第11顶点V₁₁～第13顶点V₁₃嵌入剖分集合的示意图；

图23a～23d是多边形polygon的第14顶点V₁₄～第15顶点V₁₅嵌入剖分集合的示意图；

图23e、23f是多边形polygon的闭合处理结果。

图24a～24i是最坏情况下被切割边数的数量变化示意图。

注：图中各有向边的标注字符顺序的走向与被标注的有向边的方向一致。

具体实施方式

实施例1

参照图1，在步骤1.1中，由a＞水平尺度X_max+竖直尺度Y_max，确定a的数值，建立多边形之外的菱形Q₀；实际编程时注意，尽管理论上说a可以为无穷大，但所使用的计算机语言对有效数值范围会有限定，另外，有向边建议使用半边数据结构，在进行方位判别时需要考虑到数值计算舍入误差的影响；

参照图2，在步骤1.1中，选定第1顶点V₁、第2顶点V₂，连接第1顶点V₁与菱形的各个顶点；

参照图3，在将第n顶点V_n嵌入剖分集合时，因第n顶点V_n与第1顶点V₁重合且以第N顶点V_N为起点的附加边E_N的终点是第1顶点V₁，则第N顶点E_N是多边形的边，嵌入结束；在执行步骤1.3时，因为多边形是顺时针的(可由过菱形Q₀的某一构造顶点的附加边获取多边形的外围顶点，再由所述的外围顶点的上下游相邻顶点来判断菱形Q₀的上述构造顶点是否在多边形的左侧，例如菱形Q₀有过第2构造顶点P₂的附加边E_2N，所述附加边E_2N的终点是第N顶点V_N，而第2构造顶点P₂位于自第N顶点V_N的上游相邻顶点V_N-1经第N顶点V_N至第N顶点V_N的下游相邻顶点V₁所形成的左侧夹角之内)，故需要进行方向逆转处理，将第N顶点V_N标定为第1顶点V₁的下游相邻顶点，将第1顶点V₁标定为第2顶点V₂的下游相邻顶点，将第2顶点V₂标定为第3顶点V₃的下游相邻顶点，将第3顶点V₃标定为第4顶点V₄的下游相邻顶点，……；并将第1顶点V₁标定为第N顶点V_N的上游相邻顶点，将第2顶点V₂标定为第1顶点V₁的上游相邻顶点，将第3顶点V₃标定为第2顶点V₂的上游相邻顶点，将第4顶点V₄标定为第3顶点V₃的上游相邻顶点，……。

参照图4，在将第n顶点V_n嵌入剖分集合时，从以第n-1顶点V_n-1为起点的有向边中选择出位于探头右侧的第一条有向边为第1右首边E_r1，以第1右首边E_r1的下游边为第1链首E_h1，以探头的上游边为第1链尾E_t1，以i作为后续的计数次数，i＝1，因为位于第1右首边E_r1左侧的第一条附加边E_c与探头E_p重叠，故以重叠边E_c的下游边为共线边H_a，然后删除重叠边E_c，再由步骤1.2.6进行共线处理。

参照图5、图6a～6d，在执行步骤1.2.1时，从所有以第n-1顶点V_n-1为起点的有向边G_e中选择出位于探头E_p右侧的第一条边为第1右首边E_r1，以第1右首边E_r1的下游边为第1链首E_h1，以探头E_p的上游边为第1链尾E_t1，创建了一个单边形(图5)的链段为第1链段C_c1；其它形状的链段有凸链形(图6a)、凹链形(图6b)、左凹形(图6c)、右凹形(图6d)。

参照图7a、图7b，在执行步骤1.2.3进行环切割处理时，第i链段C_ci是右凹形且探头E_p与第i链尾E_ti的上游边不相交，故对以第i链首E_hi为链首、第i链尾E_ti的上游边为链尾的链段进行链段夹挤确定探头对准边，并将其作为第i命中边H_ui。

参照图8a、图8b，在执行步骤1.2.4时，第i链段C_ci是左凹形且探头E_p与第i链首E_hi不相交，故对以第i链首E_hi为链首，第i链尾E_ti的上游边为链尾的链段进行链段夹挤确定探头对准边，但 对准边不存在，故以第i链首E_hi作为第i命中边H_ui。

参照图9，在执行步骤1.2.5时，以第i命中边H_ui的下游边H_di为第i+1链尾E_ti+1，因为探头E_p与第i命中边H_ui相交，故以第i命中边H_ui的逆向边E_hr的下游边E_hrd为第i+1链首E_hi+1，以探头E_p的逆向边E_pr的下游边E_prd为第i+1右首边E_ri+1，并删除第i命中边H_ui，以i+1作为新的i，重返步骤1.2.3进行下一轮环切割处理。

参照图10，在执行步骤1.2.5时，因为探头E_p与第i命中边H_ui不相交，故对以探头E_p的逆向边E_pr为链首、第i命中边H_ui为链尾的链段进行链段修正，将新连接的自第n顶点的附加边作为右翼边W_r，再对以第i+1链尾E_ti+1为链首、右翼边W_r为链尾的链段进行链段修正，将新连接的自第i+1链尾的起点的附加边作为左翼边W_l；分别以右翼边W_r的下游边W_rd、左翼边W_l和右翼边W_r的上游边W_ru作为起始边、中间边和终止边，以无界方式对探头的前方进行三边连环。

参照图11，在执行步骤1.2.6进行共线处理过程中，先对探头E_p的两侧分别进行有界方式的三边连环，然后对以第i右首边E_ri为链首、共线边H_a为链尾的链段获取中部边，因该链段是左凹形，故以链尾H_a的上游边H_au为中部边，并以链首E_ri为起环边、中部边为止环边进行双边连环；然后以中部边为右中边M_u，探头E_p的逆向边E_pr为起环边、右中边M_u为止环边进行双边连环，并连接第n顶点V_n与共线顶点V_c作为接续边E_x；对以共线边H_a为链首、探头E_p为链尾的链段获取中部边，因该链段不是左凹形且链首的下游边H_ad不是链尾的上游边，故以链首的下游边H_ad为起环边、链尾为止环边进行双边连环，然后以双边连环之后的链首的下游边为中部边；然后以中部边作为左中边M_d，以左中边M_d为起环边、接续边E_x为止环边进行双边连环。

参照图12，在执行步骤1.2.6时，第n顶点V_n是第i命中边H_ui的起点(也必定是第1顶点V₁)，多边形闭合。

参照图13a，在双边连环时，以止环边R_d的上游边为环内边R_i，以连接起环边R_u的起点与止环边R_d的起点形成的附加边作为封口边R_r，因为起环边R_u是一条附加边且起环边R_u足够长且起环边R_u的两侧的两个环在起环边R_u被删除的情况下可以形成一个较大的凸环，故可被删除起环边R_u；因环内边R_i不是附加边，故环内边R_i不可以删除。

参照图13b，在双边连环时，与图14a不同的是，环内边R_i也是附加边且环内边R_i足够长且环内边R_i的两侧的两个环在环内边R_i被删除的情况下可以形成一个较大的凸环，故环内边R_i也可被删除。

参照图14a，在双边连环时，以止环边R_d的上游边为环内边R_i，以连接起环边R_u的起点与止环边R_d的起点形成的附加边作为封口边R_r，因为起环边R_u是一条附加边且起环边R_u足够长且起环边R_u的终点不是第1顶点V₁且起环边R_u的两侧的两个环在起环边R_u被删除的情况下可以形成一个较大的凹环，故可被删除起环边R_u；因环内边R_i不是附加边，故环内边R_i不可以删除。

参照图14b，在双边连环时，起环边R_u不是附加边，故起环边R_u不可以删除；因环内边R_i是附加边且环内边R_i足够长且环内边R_i的终点不是第1顶点V₁且环内边R_i的两侧的两个环在环内边R_i被删除的情况下可以形成一个较大的凹环，故环内边R_i也可被删除。

参照图15a，在有界方式的三边连环过程中，对以起始边S_u为链首、中间边S_m为链尾所创建的链段进行链段修正，以起始边S_u为新始边S_nu；再对以中间边S_m为链首、终止边S_d为链尾所创建的链段进行链段修正，以中间边S_m的起点位置的新的下游方向的附加边作为新中边S_nm；因为起始边S_u不是中间边S_m且中间边S_m不是终止边S_d且新中边S_nm起点的角度＜π且两次修正结果都是凹链形，执行步骤1.2.5.2，以新中边S_nm为第1轮奇折边O₁，新始边S_nu的起点为上端点P_u，终止边S_d的起点为下端点P_d，执行步骤1.2.5.3，以第1轮奇折边O₁为凹链首、终止边S_d为凹链尾，以自上方式进行凹链顺延，并以新连接的附加边作为第1轮偶折边E₁；执行步骤1.2.5.4，以新始边S_nu为凹链首、第1轮偶折边E₁为凹链尾，以自下方式进行凹链顺延，并以新连接的附加边的下游边作为第2轮的奇折边O₂；以第2轮执行步骤1.2.5.3，因为三边连环是有界方式且第2轮的奇折边O₂的上游边的起点是上端点P_u，故结束。

参照图15b，在无界方式的三边连环过程中，对以起始边S_u为链首、中间边S_m为链尾所创 建的链段进行链段修正，以起始边S_u为新始边S_nu；再对以中间边S_m为链首、终止边S_d为链尾所创建的链段进行链段修正，因为中间边S_m的起点位置有新的上游方向而不是下游方向的附加边，故以中间边S_m作为新中边S_nm；因为起始边S_u不是中间边S_m且中间边S_m不是终止边S_d且新中边S_nm起点的角度＜π且两次修正结果都是凹链形，执行步骤1.2.5.2，以新中边S_nm为第1轮奇折边O₁，新始边S_nu的起点为上端点P_u，终止边S_d的起点为下端点P_d，执行步骤1.2.5.3，以第1轮奇折边O₁为凹链首、终止边S_d为凹链尾，以自上方式进行凹链顺延，并以新连接的附加边作为第1轮偶折边E₁；执行步骤1.2.5.4，以新始边S_nu为凹链首、第1轮偶折边E₁为凹链尾，以自下方式进行凹链顺延，并以新连接的附加边的下游边作为第2轮奇折边O₂；以第2轮执行步骤1.2.5.3，以第2轮奇折边O₂为凹链首、终止边S_d为凹链尾，以自上方式进行凹链顺延，并以新连接的附加边作为第2轮偶折边E₂；执行步骤1.2.5.4，因为三边连环是无界方式且第2轮偶折边E₂的起点是上端点P_u，故结束。

参照图15c，在有界方式的三边连环过程中，经过两次链段修正，得到新始边S_nu，新中边S_nm；虽然起始边S_u不是中间边S_m且中间边S_m不是终止边S_d且新中边S_nm起点的角度＜π，但两次链段修正的结果不是两个凹链形。

参照图15d，在无界方式的三边连环过程中，经过两次链段修正，得到新始边S_nu，新中边S_nm；因为起始边S_u不是中间边S_m且中间边S_m不是终止边S_d且新中边S_nm起点的角度＜π，且两次修正结果都是单边形，故以新始边S_nu为起环边、终止边S_d为止环边进行双边连环。

参照图15e，在无界方式的三边连环过程中，类似图15d的情况，但第一次修正结果是单边形，第二次修正结果是凹链形，故分别以新中边S_nm为凹链首、终止边S_d为凹链尾，以自上方式进行凹链顺延。

参照图15f，在无界方式的三边连环过程中，类似图15d的情况，但第一次修正结果是凹链形，第二次修正结果是单边形，故分别以新始边S_nu为凹链首、新中边S_nm为凹链尾，以自下方式进行凹链顺延。

参照图16a，在链段修正过程中，链段是凸链形，以链首E_h为起环边、链尾E_t为止环边进行双边连环(修正结果是单边形)。

参照图16b，在链段修正过程中，链段是左凹形，以链首E_h的下游边为凹链首，链尾E_t为凹链尾，以自上方式进行凹链顺延(修正结果是单边形)。

参照图16c，在链段修正过程中，链段是右凹形，以链首E_h为凹链首，链尾E_t的上游边为凹链尾，以自下方式进行凹链顺延(修正结果是凹链形)。

参照图16d、图16e，在链段修正过程中，链段是单边形或凹链形，不作处理。

参照图17a、图17b，在自上方式的凹链顺延过程中，以链首E_h的上游边为观察边W，并对链首E_h、链尾E_t组成的两条边，进行链段夹挤确定观察点的可见范围，以可见范围的上游起始位置的有向边为上游类切边T_u，可见范围的下游终止位置的有向边的下游边为下游类切边T_d；然后以观察边W为起环边R_u、下游类切边T_d为止环边R_d进行双边连环(顺延结果是凹链形)。

参照图17c、图17d，在自下方式的凹链顺延过程中，以链尾E_t的下游边为观察边W，并对链首E_h、链尾E_t组成的两条边，进行链段夹挤确定观察点的可见范围，以可见范围的上游起始位置的有向边为上游类切边T_u，可见范围的下游终止位置的有向边的下游边为下游类切边T_d；然后以上游类切边T_u为起环边R_u、观察边W为止环边R_d进行双边连环(顺延结果是单边形)。

参照图18a，在链段夹挤确定探头对准边的过程中，以两边的第一边E_nip1为顺序第1边E_f1、两边的第二边E_nip2的上游边为逆序第1边E_b1；经过步骤2.2的循环，可以求得探头E_p的对准边是逆序第3边E_b3。

参照图18b，在链段夹挤确定探头对准边的过程中，以两边的第一边E_nip1为顺序第1边E_f1、两边的第二边E_nip2的上游边为逆序第1边E_b1；经过步骤2.2的循环，可以求得探头E_p的对准边是顺序第5边E_f5。

参照图18c，在链段夹挤确定探头对准边的过程中，以两边的第一边E_nip1为顺序第1边E_f1、 两边的第二边E_nip2的上游边为逆序第1边E_b1；经过步骤2.2的循环，逆序第3边的起点的角度≥π且探头E_p的起点同时位于顺序第3边E_f3、逆序第3边E_b3的左侧，且E_f3的终点位于探头E_p的右侧，不可能有对准边。

参照图19a，在链段夹挤确定观察点的可见范围的过程中，以两边的第一边E_nip1为顺序第1边E_f1、两边的第二边E_nip2的上游边为逆序第1边E_b1；观察点V_eye同时位于顺序第1边E_f1左侧与逆序第1边E_b1左侧，则上游起始位置的有向边为顺序第1边E_f1，可见范围的下游终止位置的有向边为逆序第1边E_b1。

参照图19b，在链段夹挤确定观察点的可见范围的过程中，以两边的第一边E_nip1为顺序第1边E_f1、两边的第二边E_nip2的上游边为逆序第1边E_b1；观察点V_eye在逆序第1边左侧E_b1，可见范围的下游终止位置的有向边为逆序第1边E_b1；经过步骤3.2的循环，观察点V_eye同时位于顺序第4边E_f4左侧与逆序第1边E_b1左侧，则上游起始位置的有向边为顺序第4边E_f4。

参照图19c，在链段夹挤确定观察点的可见范围的过程中，以两边的第一边E_nip1为顺序第1边E_f1、两边的第二边E_nip2的上游边为逆序第1边E_b1；观察点V_eye在顺序第1边左侧E_f1，可见范围的上游终止位置的有向边为E_f1；经过步骤3.2的循环，观察点V_eye位于顺序第1边左侧但不在顺序第4边左侧E_f4，则下游终止位置的有向边为顺序第4边E_f4的上游边E_f3。

实施例2

初始化：参照图20a、20b，多边形Polygon的15个顶点坐标分别为：V₁(1.72，10.72)、V₂(-2.0，6.0)、V₃(-7.0，4.0)、V₄(-11.6，3.2)、V₅(-5.0，-2.0)、V₆(-3.88，-3.32)、V₇(-3.68，-4.48)、V₈(-3.14，-3.64)、V₉(-2.0，-3.52)、V₁₀(0.0，-4.0)、V₁₁(-4.0，-2.4)、V₁₂(-1.71，2.8)、V₁₃(-4.25，-0.81)、V₁₄(-5.92，3.05)、V₁₅(-3.61，0.56)，第16个顶点V₁₆是第1顶点的重现；由a＞水平尺度X_max+竖直尺度Y_max＝|-11.6|+10.72＝22.32，取a＝30，在多边形Polygon之外设置4个构造顶点分别是P₁(30，0)、P₂(0，30)、P₃(-30，0)、P₄(0，-30)的菱形Q₀；第1顶点V₁分别与菱形Q₀的4个构造顶点相连接；

将第2顶点V₂嵌入剖分集合：参照图20c、20d，由步骤1.2.1，自第1顶点V₁至第2顶点V₂构成探头E_p，因第2顶点V₂与第1顶点V₁未重合，故选择出自第2顶点的位于探头E_p右侧的第一条有向边为第1右首边E_r1，并以第1右首边E_r1的下游边为第1链首E_h1，以探头E_p的上游边为第1链尾E_t1，因为没有与探头E_p重叠的附加边，故执行步骤1.2.3，对以第1链首E_h1、第1链尾E_t1所构成的单边形第1链段C_c1进行链段夹挤确定探头对准边，将所获得的对准边作为第1命中边H_u1，然后执行步骤1.2.5，因为第2顶点V₂与第1顶点V₁未重合，且第1命中边H_u1的两个端点皆未与探头E_p共线，故分别以第1右首边E_r1、第1链首E_h1和第1命中边H_u1作为起始边、中间边和终止边，以无界方式对探头E_p的右侧进行三边连环，由于以起始边为链首、中间边为链尾的链段是单边形，而中间边和终止边相同，故三边连环没有产生变化；再分别以第1命中边H_u1的下游边、第1链尾E_t1和探头E_p作为起始边、中间边和终止边，以无界方式对探头的左侧进行三边连环，由于起始边与中间边相同，而以中间边为链首、终止边为链尾的链段是单边形，这一次三边连环也没有产生变化；以第1命中边H_u1的下游边为第2链尾E_t2，因探头E_p未与第1命中边H_u1相交，故对以探头E_p的逆向边E_pr为链首、第1命中边H_u1为链尾的凸链形链段进行链段修正，在以链首为起环边、链尾为止环边进行双边连环时删除了第1右首边E_r1，将新连接的自第2顶点的附加边作为右翼边W_r；再对以第2链尾E_t2为链首、右翼边W_r为链尾的凸链形链段进行链段修正，同样在双边连环时删除了第2链尾E_t2，将新连接的自第2链尾E_t2的起点的附加边作为左翼边W_l；分别以右翼边W_r的下游边、左翼边W_l和右翼边W_r的上游边作为起始边、中间边和终止边，以无界方式对探头的前方进行三边连环，此次三边连环没有产生变化；

将第3顶点V₃嵌入剖分集合：参照图20e、20f，与上述将第2顶点V₂嵌入剖分集合过程相仿，分别连接了自第3顶点V₃至第3构造顶点P₃的右翼边W_r与自第4构造顶点P₄至第3顶点V₃的左翼边W_l，不同之处是在进行双边连环时，第2链尾E_t2不能被删除；

将第4顶点V₄嵌入剖分集合：参照图21a、21b，以第1右首边E_r1的下游边为第1链首E_h1，以探头E_p的上游边为第1链尾E_t1，其特别之处在于第一条位于第1右首边E_r1的左侧的附加边E_c 与探头E_p重叠，故以此附加边E_c的下游边为共线边H_a，并删除重叠的附加边E_c，然后执行步骤1.2.6，分别以第1右首边E_r1、第1链首E_h1和共线边H_a作为起始边、中间边和终止边，以有界方式对探头的右侧进行三边连环，致使在第2顶点V₂与第3构造顶点P₃之间连接了附加边；再分别以共线边H_a、第1链尾E_t1和探头E_p作为起始边、中间边和终止边，以有界方式对探头的左侧进行三边连环，没有产生变化；对以探头E_p逆向边E_pr的下游边E_prd为链首、共线边H_a为链尾的链段获取中部边并作为右中边M_u，然后以探头E_p逆向边E_pr为起环边、右中边M_u为止环边进行双边连环，并连接第4顶点V₄与共线顶点P₃作为接续边E_x；对以共线边H_a为链首、探头E_p为链尾的链段获取中部边并作为左中边M_d，然后以左中边M_d为起环边、接续边E_x为止环边进行双边连环；

将第5顶点V₅嵌入剖分集合：参照图21c、21d，其特别之处是在执行步骤1.2.5时，探头E_p在探头与第1命中边H_u1相交，因而需要删除第1命中边H_u1，两次执行步骤1.2.3；将第6～9顶点的嵌入剖分集合过程与第2顶点V₂、第3顶点V₃类似，每次连接两条新的附加边，并可能删除一至两条附加边；

将第10顶点V₁₀嵌入剖分集合：参照图21e、21f，与第5顶点V₅嵌入剖分集合类似，在删除第1命中边H_u1之后，第二次执行步骤1.2.3，从而将第10顶点V₁₀分别与第1构造顶点P₁、第4构造顶点P₄进行了链接；

将第11顶点V₁₁嵌入剖分集合：参照图22a、22b，分别在第1轮删除了第1命中边H_u1，第2轮删除了第2命中边H_u2之后，第3轮的命中边H_u3的起点V₅与探头E_p共线，在执行步骤1.2.6时，需要以有界方式对探头E_p的两侧分别进行三边连环，其中对左侧的三边连环导致了两个凹链的交替顺延；接下去的步骤类似第4顶点V₄嵌入剖分集合的过程；

将第12～15顶点的嵌入剖分集合：参照图22c～22f、23a～23d，与第2顶点V₂、第3顶点V₃的嵌入剖分集合过程类似；

将第16顶点V₁₆嵌入剖分集合：参照图19e、19f，虽然第16顶点V₁₆与第1顶点V₁重合，但第15顶点V₁₅至第1顶点V₁没有附加边，因此需要以探头E_p作为探头E_p执行步骤1.2.3～步骤1.2.5，分别经过第1轮删除了第1命中边H_u1，第2轮删除了第2命中边H_u2之后，第3轮的命中边H_u3的起点是第1顶点V₁，多边形闭合，分别以有界方式对探头E_p的两侧分别进行三边连环，完成所有顶点的嵌入剖分集合过程；

多边形的方向校正：因为按照第1顶点、第2顶点、第3顶点、……、第15顶点至第1顶点的顺序形成的多边形的走向是逆时针方向的，无需修正上下游相邻关系；

以上步骤完成了实施例2的多边形Polygon的切环剖分。