一种解决交点退化问题的复杂多边形裁剪方法

摘要

本发明公开了一种解决交点退化问题的复杂多边形裁剪方法，首先，对实体多边形的外环边界构成的多边形与裁剪多边形进行求交；然后，若实体多边形含有孔洞，则对结果多边形与孔洞构成的多边形进行求差；得到的裁剪结果再与下一个孔洞多边形进行求差，直至所有孔洞多边形处理完毕，整个裁剪过程结束，最终得到一般多边形的裁剪结果。本发明适用于任意凸的、凹的或带孔洞的多边形裁剪，可实现实体多边形与裁剪多边形的求交、求差以及求并，在交点退化情况下也能够得到正确的裁剪结果；减少了多边形的求交次数和生成裁剪结果时顶点遍历次数，加快了裁剪算法运行速度；在空间消耗和时间消耗上的性能要优于Greiner‑Hormann算法。

说明书

技术领域

本发明涉及计算机图形学以及地理信息系统(GIS)技术，特别是涉及一种解决交点退化问题的复杂多边形裁剪方法。

背景技术

多边形裁剪算法被广泛应用于地理信息系统（GIS）、计算机图形学、机器人运动学等领域，是计算机图形学许多重要问题的基础，其主要目的是裁剪掉被裁减多边形（又称实体多边形）位于裁剪多边形之外的部分。

目前，对于多边形裁剪国外已有很多经典算法，例如Sutherland-Hodgeman算法、Liang-Barsky算法、Maillot算法等算法，可是以上算法要求裁剪多边形是矩形，被裁剪多边形（也称实体多边形）是凸多边形。而在实际应用中，实体多边形为一般多边形时裁剪算法才具有普遍意义和实际应用价值。在这类算法中Weiler-Atherton算法（简称W-A算法）和Greiner-Hormann算法（简称G-H算法）是公认的比较具有代表性、成熟的任意多边形裁剪算法。其中，W-A算法使用的是树形结构，而G-H算法使用的是双向线性链表结构，所以后者在复杂性和运行速度方面都优于前者。国内学者大多数从优化数据结构、减少交点判断和交点求取的计算量等方面展开研究，进一步提高了裁剪算法效率。但是上述算法都没有具体描述在重合边和两多边形在顶点处相切（又称交点退化）这两种特殊情况下多边形裁剪的解决方案。王慧青等采用交点关联线段间的交点进出性判别方法，用于处理重点和重边问题，但是该算法将交点插入到实体多边形和裁剪多边形的顶点链表，在生成裁剪结果多边形时，需要在实体多边形和裁剪多边形的两个顶点链表之间来回切换遍历，其工作量很大。因此，需要研究一种新的解决交点退化问题的复杂多边形裁剪方法。

发明内容

为了解决上述存在的问题，本发明提供一种解决交点退化问题的复杂多边形裁剪方法，在顶点处相切这两种交点退化情况下也能够得到正确裁剪结果的复杂多边形裁剪方法，为达此目的，本发明提供一种解决交点退化问题的复杂多边形裁剪方法，所述步骤包括：

（1）假设被裁剪多边形即实体多边形为S，裁剪多边形为C，将含孔洞的复杂实体多边形分解成多个由外环和N个内环构成的不含孔洞的简单多边形，其中N≧0；

（2）对实体多边形的外环边界构成的多边形与裁剪多边形进行求交即S∩C操作，得到裁剪结果；

（3）若S不含孔洞，则直接输出这个裁剪结果；否则，继续步骤4；

（4）将结果多边形视为裁剪多边形，某一孔洞构成的多边形视为实体多边形，对结果多边形与孔洞构成的多边形进行求差即C－S操作，得到裁剪结果；

（5）取下一个孔洞构成的多边形，继续步骤4，直至所有孔洞构成的多边形处理完毕，输出最终的裁剪结果。

进一步的，所述步骤（2）中对实体多边形的外环边界构成的多边形与裁剪多边形进行求交操作步骤为：

（21）设计了一个合理的数据结构，用于存储入点、出点以及裁剪多边形顶点；

（22）将实体多边形S和裁剪多边形C的顶点按顺时针方向分别以单向线性链表形式存储；

（23）判断实体多边形和裁剪多边形的最小外包矩形框MBR是否相交：若不相交，则输出裁剪结果多边形为空；若相交，继续步骤（24）；

（24）从实体多边形边界上的首顶点开始，寻找实体多边形边界上位于裁剪多边形外的第一个点，记为P_k点，该点在实体多边形边界上的坐标点号记为k；

（25）从P_k点开始，求取实体多边形与裁剪多边形的交点及可见折线段；基于制定的交点出入特性判定规则判断交点是否有效；若该点为有效的交点，即为入点或出点，则计算交点到裁剪多边形的首顶点的距离dfDis值，以及记录交点的nId值；

（26）若存在交点，则继续步骤（27）；若实体多边形和裁剪多边形之间没有交点，存在以下三种情形：

①实体多边形边界上只要有顶点落在裁剪多边形的内部，则表示裁剪多边形包含实体多边形，此时输出裁剪结果为实体多边形；

②裁剪多边形边界上只要有顶点落在实体多边形的内部，则表示实体多边形包含裁剪多边形，此时输出裁剪结果为裁剪多边形；

③否则表示裁剪多边形与实体多边形相离，此时输出裁剪结果为空；

（27）计算裁剪多边形每个顶点的dfDis值，并将tag值设为0；

（28）将步骤（25）中计算得到的入点、出点以及步骤（27）中的裁剪多边形顶点按dfDis值采用快速排序算法进行升序排序，若某交点和裁剪多边形的某顶点的dfDis值相同，则排序时按照“入点、顶点”或“顶点、出点”的顺序排列；

（29）基于单向线性链表构建中间链表，存储上述排序后的点；

（30）遍历生成的中间链表，输出一个或多个裁剪结果多边形。

进一步的，所述步骤（21）中设计的数据结构有7个成员变量，分别如下：

①pt是入点、出点或裁剪多边形顶点坐标；

②tag表示该点所属类型：tag=0，该点是裁剪多边形的顶点；tag=1，该点为入点； tag=2，该点为出点；

③dfDis表示从裁剪多边形首顶点出发，沿着裁剪多边形边界方向到该点的距离，用作单向链表中结点排序参数；

④nId表示实体多边形边界上与该点相邻的点的索引号：若该点是入点，nId是从入点出发，沿可见折线段方向遇到的实体多边形边界上第一个顶点的索引号；若该点是出点，nId是从出点出发，沿可见折线段反方向遇到的实体多边形边界上第一个顶点的索引号；

⑤bIsUsed表示该点是否被使用过：TRUE表示被使用过，FALSE表示未被使用过；

⑥next1用于指向该点关联的结点：若该点是入点，next1指向入点关联的出点；若该点是出点，根据实际应用需求，如果仅需对实体多边形与裁剪多边形进行求交操作，则next1为空指针；如果还需对两个多边形进行求差或求并操作，则next1指向沿着实体多边形边界方向的下一个入点；

⑦next2用于指向下一个结点。

进一步的，所述步骤（25）中制定的交点出入特性判定规则如下：

（41）入点的判定：

①交点的前一个结点在C的外部，且交点的后一个结点在C的内部；

②交点的前一个结点在C的外部，且以该点为起始点的可见折线段上有点在C的内部；

③交点与前一个结点的中间点在C的外部，且交点与后一个结点的中间点在C的内部；

④交点与前一个结点的中间点在C的边界，且交点与后一个结点的中间点在C的内部；

满足以上任一条件的交点定义为入点；

（42）出点的判定：

①交点的前一个结点在C的内部，且交点的后一个结点在C的外部；

②以交点为末尾点的可见折线段上有点在C的内部，且交点的后一个结点在C的外部；

③交点与前一个结点的中间点在C的内部，且交点与后一个结点的中间点在C的外部；

④交点与前一个结点的中间点在C的内部，且交点与后一个结点的中间点在C的边界。

满足以上任一条件的交点定义为出点，

在交点退化情况下，利用上述规则也能够准确判断出交点是入点还是出点，若交点不满足上述任一条件，则该交点被视为无效。

进一步的，所述步骤（30）中实现两个多边形的求交即S∩C操作的遍历方式具体实现过程如下：

（51）在单向链表中寻找一个未被用过的入点；

（52）将该入点记为可见折线段的入点，并通过入点找到可见折线段的出点；

（53）由入点和出点关联的nId从实体多边形中获得可见折线段的中间结点，将上述可见折线段输出到裁剪结果多边形中，同时标记这个入点已被使用过；

（54） 从当前可见折线段的出点开始，正向继续追踪单向链表，寻找下一个入点，如果在搜索下一个入点过程中遇到裁剪多边形的顶点，则输出到裁剪结果多边形中；

（55） 继续步骤（52），直至遇到此裁剪结果多边形的第一个顶点为止，这个裁剪结果多边形构建完成；重复步骤（51）～（55），构建下一个裁剪结果多边形，直至单向链表中所有入点都被标记为使用过为止，裁剪过程结束。

进一步的，所述步骤（30）中实现两个多边形的求差，求并操作的遍历方式实现过程描述如下：

（56）从单向链表的入点出发，并通过入点找到以该点为起始点的可见折线段的出点，将可见折线段输出到裁剪结果多边形中，继续反向追踪链表，可以得到两个多边形的差集即C－S；

（57）从单向链表的出点出发，通过出点找到沿着实体多边形边界方向上相邻的下一个入点，将这条以出点为起始点、入点为末尾点的实体多边形的折线段输出到裁剪结果多边形中，继续反向追踪链表，可以得到两个多边形的差集即S－C；

（58）从单向链表的出点出发，通过出点找到沿着实体多边形边界方向上相邻的下一个入点，将这条以出点为起始点、入点为末尾点的实体多边形的折线段输出到裁剪结果多边形中，继续正向追踪链表，可以得到两个多边形的并集即S∪C。

进一步的，所述步骤（4）中对结果多边形与孔洞构成的多边形进行求差操作实现方法为：将结果多边形视为裁剪多边形，某一孔洞构成的多边形视为实体多边形，采用求差即C－S方式遍历中间链表，得到裁剪结果。

本发明相对于现有技术而言具有以下优点：

（1）本发明适用于任意凸的、凹的或带孔洞的多边形裁剪，可实现实体多边形与裁剪多边形的求交、求差以及求并运算。

（2）本发明在交点退化情况下能够得到正确的裁剪结果。

（3）本发明设计了合理的数据结构，数据结构简单，易于实现，减少了多边形的求交次数和生成裁剪结果时顶点遍历次数，加快了裁剪算法运行速度。

（4）本发明在空间消耗和时间消耗上的性能要优于G-H算法。

附图说明

图1是本发明中将复杂多边形转化为一系列简单多边形的多边形裁剪的流程示意图。

图2 是本发明中的两个简单多边形的多边形裁剪方法的流程示意图。

图3 是本发明中的交点退化情况的几个典型案例的示意图。

图4 是本发明中的遍历中间链表得到两个多边形相交区域的流程示意图。

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细描述：

如图1所示，将任意多边形的裁剪问题转化为一系列不含孔洞的简单多边形的裁剪的步骤如下：

（1）假设被裁剪多边形（又称实体多边形）为S，裁剪多边形为C，将含孔洞的复杂实体多边形分解成多个由外环和N（N≧0）个内环构成的不含孔洞的简单多边形；

（2）对实体多边形的外环边界构成的多边形与裁剪多边形进行求交（S∩C）操作，得到裁剪结果；

（3）若S不含孔洞，则直接输出这个裁剪结果；否则，继续步骤4；

（4）将结果多边形视为裁剪多边形，某一孔洞构成的多边形视为实体多边形，对结果多边形与孔洞构成的多边形进行求差（C－S）操作，得到裁剪结果；

（5）取下一个孔洞构成的多边形，继续步骤4，直至所有孔洞构成的多边形处理完毕，输出最终的裁剪结果。

如图2所示，假设实体多边形和裁剪多边形是简单多边形，即都只有一条封闭边界，边界方向为顺时针方向，多边形裁剪方法的步骤如下：

（1）设计了一个合理的数据结构，用于存储入点、出点以及裁剪多边形顶点；

（2）将实体多边形S和裁剪多边形C的顶点按顺时针方向分别以单向线性链表形式存储；

（3）判断实体多边形和裁剪多边形的最小外包矩形框MBR（Minimum BoundingRectangle）是否相交：若不相交，则输出裁剪结果多边形为空；若相交，继续步骤（4）；

（4）从实体多边形边界上的首顶点开始，寻找实体多边形边界上位于裁剪多边形外的第一个点，记为Pk点，该点在实体多边形边界上的坐标点号记为k；

（5）从Pk点开始，求取实体多边形与裁剪多边形的交点及可见折线段；基于制定的交点出入特性判定规则判断交点是否有效；若该点为有效的交点（即为入点或出点），则计算交点到裁剪多边形的首顶点的距离dfDis值，以及记录交点的nId值；

（6）若存在交点，则继续步骤（7）；若实体多边形和裁剪多边形之间没有交点，存在以下三种情形：

①实体多边形边界上只要有顶点落在裁剪多边形的内部，则表示裁剪多边形包含实体多边形，此时输出裁剪结果为实体多边形；

②裁剪多边形边界上只要有顶点落在实体多边形的内部，则表示实体多边形包含裁剪多边形，此时输出裁剪结果为裁剪多边形；

③否则表示裁剪多边形与实体多边形相离，此时输出裁剪结果为空；

（7）计算裁剪多边形每个顶点的dfDis值，并将tag值设为0；

（8）将步骤（5）中计算得到的入点、出点以及步骤（7）中的裁剪多边形顶点按dfDis值采用快速排序算法进行升序排序，若某交点和裁剪多边形的某顶点的dfDis值相同，则排序时按照“入点、顶点”或“顶点、出点”的顺序排列；

（9）基于单向线性链表构建中间链表，存储上述排序后的点；

（10）遍历生成的中间链表，输出一个或多个裁剪结果多边形。

对于步骤10，采用不同的遍历方式，可以得到实体多边形与裁剪多边形的求交、求差、求并结果。

基于本发明中制定的交点出入特性判定规则，对于交点退化现象也能准确的判断出交点是入点还是出点。

如图3所示，例如图3a中S与C存在同向重合边。对于I1点，I1点的前一个结点在C的外部，且I1点与后一个结点I2的中间点在C的边界上，依据上述交点出入特性判定规则确定I1点既不是入点也不是出点；对于I2点，I2点与前一个结点I1的中间点在C的边界上，I2点与后一个结点I3的中间点在C的内部，因此I2点为入点；对于I3点，I3点与前一个结点的中间点在C的内部，I3点的后一个结点在C的外部，所以I3点为出点。图3f中交点I5既不是入点也不是出点。其他特殊情况依据上述规则都可以正确判断出交点的出入类型。

如图4所示，两个多边形的求交（S∩C）操作具体实现过程如下：

（1）在单向链表中寻找一个未被用过的入点；

（2）将该入点记为可见折线段的入点，并通过入点找到可见折线段的出点；

（3）由入点和出点关联的nId从实体多边形中获得可见折线段的中间结点，将上述可见折线段输出到裁剪结果多边形中，同时标记这个入点已被使用过；

（4） 从当前可见折线段的出点开始，正向继续追踪单向链表，寻找下一个入点。如果在搜索下一个入点过程中遇到裁剪多边形的顶点，则输出到裁剪结果多边形中；

（5） 继续步骤（2），直至遇到此裁剪结果多边形的第一个顶点为止，这个裁剪结果多边形构建完成。重复步骤（1）～（5），构建下一个裁剪结果多边形，直至单向链表中所有入点都被标记为使用过为止，裁剪过程结束。

对上述过程稍做修改，就可以得到两个多边形的差集、并集，实现过程简单描述如下：

（1）从单向链表的入点出发，并通过入点找到以该点为起始点的可见折线段的出点，将可见折线段输出到裁剪结果多边形中，继续反向追踪链表，可以得到两个多边形的差集（C－S）。

（2）从单向链表的出点出发，通过出点找到沿着实体多边形边界方向上相邻的下一个入点，将这条以出点为起始点、入点为末尾点的实体多边形的折线段输出到裁剪结果多边形中，继续反向追踪链表，可以得到两个多边形的差集（S－C）。

（3）从单向链表的出点出发，通过出点找到沿着实体多边形边界方向上相邻的下一个入点，将这条以出点为起始点、入点为末尾点的实体多边形的折线段输出到裁剪结果多边形中，继续正向追踪链表，可以得到两个多边形的并集（S∪C）。

以上所述，仅是本发明的较佳实施例而已，并非是对本发明作任何其他形式的限制，而依据本发明的技术实质所作的任何修改或等同变化，仍属于本发明所要求保护的范围。