多边形裁剪中交点为多边形顶点的进出性判别方法

技术领域

本发明涉及一种计算机图形学领域，具体涉及一种多边形裁剪中交点为多边 形顶点的进出性判别方法。

背景技术

多边形的裁剪是图形学中的基本操作，一般多边形之间的裁剪过程为裁剪多 边形与实体多边形定点的顺序存储、裁剪多边形与实体多边形之间交点求解、多 边形交点的进出性判别、多边形交点分别插入裁剪多边形与实体多边形的顶点集 合，通过交点的进出性交替便利裁剪多边形和实体多边形得到裁剪结果。

现有技术中存在的问题是：当裁剪多边形与实体多边形存在顶点或边合的情 况时，在求解裁剪多边形与主多边形的交点时存在多个相同的交点，并且交点的 进出性判定不一致，从而无法准确的插入裁剪多边形和实体多边形的顶点集合 中，同时无法根据交点的进出性得到准确的裁剪结果。

发明内容

发明目的：本发明的目的在于解决现有技术中存在的不足，提供一种多边形 裁剪中交点为多边形顶点的进出性判别方法。

技术方案：本发明的一种多边形裁剪中交点为多边形顶点的进出性判别方 法，包括以下具体步骤：

(1)在裁剪多边形C与实体多边形S之间交点求解，且在交点的进出性预判 别之后，计算交点集合中具有相同坐标交点的个数；其中，用C_i代表裁剪多边形 的第i个顶点，用S_j代表实体多边形的第j个顶点，T表示裁剪多边形和实体多边形 求交后的交点集合，T_k代表添加到裁剪多边形中交点集合T中第k个交点，Q_l代表 添加到实体多边形顶点序列中交点集合Q的第l个点，其中i,j,k,l∈[1,2…,n]，NT 为新添加到裁剪多边形顶点序列新添加到T_k中的交点，NQ为新添加到Q_l中的交 点；

(2)当具有相同坐标交点的个数N等于2时，说明裁剪多边形与实体多边 形存在相同的顶点，且顶点坐标等于交点坐标，假设这两个交点分别表示为T_k与T_k+1，Q中与T_k与T_k+1坐标相同的两个交点分别为Q_l与Q_l+1，则该顶点进出 性的判别步骤如下：

(21)如果T_k与T_k+1的进出性相同：

①若交点T_k与T_k+1的坐标与顶点C_i坐标不相等，交点Q_l与Q_l+1的坐标与顶 点S_j坐标相同，则交点T_k与T_k+1是裁剪过程中的需要添加的交点，添加一个交 点NT，该交点坐标及进出性均与T_k相同，且交点Q_l与Q_l+1是裁剪过程中的顶 点坐标，设置S_j的进出性与顶点C_i的进出性相异；

②若交点T_k与T_k+1的坐标与顶点C_i坐标相等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相同，则交点T_k与T_k+1是裁剪过程中顶点，设置顶点C_i的进出性等于交 点T_k与T_k+1的进出性，交点Q_l与Q_l+1是裁剪过程中需要添加的交点，添加一个 新点NQ，该交点坐标及其进出性与Q_l相同；

③从交点集合T中删除交点T_k与T_k+1，交点集合Q中删除交点Q_l与Q_l+1。

(22)如果T_k与T_k+1的进出性不相同：

①若交点T_k与T_k+1的坐标与顶点C_i坐标不等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相等，判别交点T_k与T_k+1的先后顺序以及后一个交点的进出性，进而判 别顶点S_j的进出性，并向T中添加新交点NT，其中NT的坐标及进出性与S_j相同；

②若交点T_k与T_k+1的坐标与顶点C_i坐标相等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相等，判别交点T_k与T_k+1的先后顺序，依据得到交点T_k与T_k+1裁剪多边 形线段的先后顺序，进而得到顶点C_i的进出性，向Q中添加新较低那NQ，其 中NQ的坐标与顶点C_i的坐标相同，进出性相异。

③从交点集合T中删除交点T_k与T_k+1，交点集合Q中删除交点Q_l与Q_l+1。

(23)完成对交点集合T和Q中所有存在两个相同坐标的交点的处理，设 置相应多边形顶点的进出性，更新交点集合T中的交点；

(3)当具有相同坐标交点的个数N大于2时，则顶点进出性的判别步骤如 下：

(31)该交点坐标与裁剪多边形的顶点C_i坐标相同，同时该交点坐标与实 体多边形的顶点S_j坐标相同；

(32)判断以顶点C_i为起点的边C_iC_i+1与实体多边形的边S_j-1S_j与边S_jS_j+1是否共线；

(33)如果不存在共线，边C_iC_i+1与顶点S_j-1、S_j和S_j+1构成的内角∠S_j-1S_jS_j+1的关系，如果边C_iC_i+1在内角∠S_j-1S_jS_j+1内部，则顶点C_i为进点，在内角∠S_j-1S_jS_j+1的外部，则顶点C_i为出点，顶点S_j为进点；

(34)如果存在共线，判断边C_i+1C_i与顶点S_j-1、S_j和S_j+1构成的内角∠ S_j-1S_jS_j+1的关系，如果边C_i-1C_i在内角∠S_j-1S_jS_j+1的内部，则顶点C_i为出点；如 果边C_i-1C_i在内角∠S_j-1S_jS_j+1的外部，则顶点C_i为进点，顶点S_j为出点；

(35)删除交点集合T和Q中存在两个以上相同坐标的交点。

进一步的，所述步骤(1)的具体步骤如下：

(11)分别将裁剪多边形C和实体多边形S的顶点坐标按顺时针存储成序列， 其中用C_i代表裁剪多边形的第i个顶点，用S_j代表实体多边形中第j个顶点；

(12)按顺序对裁剪多边形C的边和实体多边形S的边进行求交运算，求出 可能存在交点的边；

(13)对多边形求交的交点集合进行统计，获得存在相同坐标的交点的数量， 判断交点坐标与多边形顶点是否相同，进而判断交点是否为添加到多边形顶点序 列中的交点；

(14)以实体多边形S为参考对象，判断出将添加到裁剪多边形C顶点序列 中的交点的进出性以及添加到实体多边形S顶点序列中的交点的进出性。

进一步的，若所述步骤(14)中的交点坐标唯一，则该交点为多边形线段间 的交点。

进一步的，当判断存在交点的多边形顶点的进出性后，保留坐标唯一的交点； 然后按顺序将交点添加到多边形顶点序列中，并更新顶点序列表；接着交替遍历 更新后裁剪多边形和实体多边形顶点序列，通过顶点的进出性和添加的交点的进 出性得到裁剪结果多边形。

有益效果：本发明能够去除线段求交过程中所有冗余的交点，提高裁剪过程 的效率；同时扩展多边形裁剪方法的适用范围，可以提高实现裁剪多边形与实体 多变形之间的求交运算的准确性，通过本发明中快速准确的判别交点的进出性， 最终能够得到准确的裁剪图形。

附图说明

图1为本发明中存在顶点为交点时的多边形裁剪流程示意图；

图2为本发明中存在两个相同交点的示意图；

图3为本发明中存在两个相同交点时的流程示意图；

图4为本发明中存在两个以上相同交点的示意图；

图5为本发明中存在两个以上相同交点时的流程示意图。

具体实施方式

下面对本发明技术方案结合附图进行详细说明。

如图1所示，当裁剪多边形C与实体多边形S的交点为多边形顶点时的多 边形裁剪步骤如下：

(1)将裁剪多边形C和实体多边形S的顶点坐标按顺时针存储成点序列；

(2)按顺序对裁剪多边形C的边与实体多边形S的边进行求交运算，求出 可能存在交点的边；

(3)以实体多边形S为参考对象，判断出将要插入到裁剪多边形C中的交 点的进出性，插入实体多边形S的交点的进出性相异；

(4)对两个多边形求出的交点进行统计，获得存在相同坐标的交点的数量；

(4.1)如果交点存在重点现象，则需要进行两种情况：一种交点坐标与 多边形顶点坐标相同；另一种情况交点坐标与一个多边形顶点坐标相同，同时是 另一多边形的交点；

(4.2)如果交点坐标唯一，则为多边形线段间的交点；

(5)判断存在交点的多边形顶点的进出性，保留坐标唯一的交点；

(6)按顺序将交点添加到多边形顶点序列中，更新顶点序列表；

(7)交替遍历更新后裁剪多边形和实体多边形顶点序列，通过顶点的进出 性和添加的交点的进出性得到裁剪结果多边形。

下面针对交点中存在重点现象，分为存在两个相同坐标的交点情况和存在两 个以上相同坐标的交点情况的不同情况进行阐述。

如图2所示，当存在两个相同坐标的交点情况时的实施例为：由顶点C₁、 C₂、C₃、C₄、C₅、C₆、C₇构成裁剪多边形，由顶点S₁、S₂、S₃、S₄、S₅、S₆、S₇、 S₈、S₉、S₁₀、S₁₁构成实体多边形。图中的裁剪多边形C与实体多边形S完成线 段求交后，由于顶点S₂、S₈以及S₁₁的坐标在线段C₃C₄、C₅C₆和C₁C₂上，同时 顶点C₄与S₅坐标相同且线段C₃C₄与S₄S₅、C₄C₅与S₅S₆共线，则交点集合T中 存在两个与顶点C₄、S₂、S₈及S₁₁坐标相同的交点，由于待插入多边形顶点中的 交点集合需要其坐标唯一，因此需要对存在两个相同坐标的交点情况进行相应处 理。

如图3所示，当存在两个相同坐标的交点情况时的处理步骤如下：

(1)在交点集合T中存在出相同坐标的交点的数量为N＝2，分别为交点T_k和T_k+1；

(2)通过交点T_k与T_k+1和交点Q_l与Q_l+1的进出性以及交点T_k与T_k+1和交点 Q_l与Q_l+1坐标是否是裁剪多边形和实体多边形的顶点坐标，从而判别裁剪多边形 与实体多边形的裁剪转折点是多边形的顶点还是交点；

(2.1)如果T_k与T_k+1的进出性相同

①若交点T_k与T_k+1的坐标与顶点C_i坐标不等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相同，则交点T_k与T_k+1是裁剪过程中的一个需要添加的交点，添加一个 交点NT，该交点坐标及进出性与T_k相同；交点Q_l与Q_l+1是裁剪过程中的顶点 坐标，设置S_j的进出性与交点C_i的进出性相异；

②若交点T_k与T_k+1的坐标与顶点C_i坐标相等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相同，则交点T_k与T_k+1是裁剪过程中顶点坐标，设置顶点C_i的进出性等 于交点T₁与T₂的进出性，交点Q_l与Q_l+1是裁剪过程中需要添加的交点，添加一 个新交点NQ，该交点坐标及其进出性与Q_l相同；

③从交点集合T中删除交点T_k与T_k+1，交点集合Q中删除交点Q_l与Q_l+1。

(2.2)如果T_k与T_k+1的进出性不相同

①若交点T_k与T_k+1的坐标与顶点C_i坐标不等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相等，判别交点T_k与T_k+1的先后顺序，依据得到交点T_k与T_k+1实体多边 形线段的先后顺序，依据后一个交点的进出性可以判别顶点S_j的进出性，并向T 中添加新交点NT，其中NT的坐标及进出性与S_j相同；

②若交点T_k与T_k+1的坐标与顶点C_i坐标相等，交点Q_l与Q_l+1的坐标与顶点 S_j坐标相等，判别交点T_k与T_k+1的先后顺序，依据得到交点T_k与T_k+1裁剪多边 形线段的先后顺序，得到顶点C_i的进出性向Q中添加新交点NQ，其中NQ的 坐标与顶点C_i的坐标相同，进出性相异；

③从交点集合T中删除交点T_k与T_k+1，交点集合Q中删除交点Q_l与Q_l+1；

(3)完成对交点集合T和Q中所有存在两个相同坐标的交点的处理，设置相 应多边形顶点的进出性，更新交点集合T中的交点。

如图4所示，当存在两个以上相同坐标的交点情况时的实施例为：由顶点 C₁、C₂、C₃、C₄、C₅、C₆构成裁剪多边形，由顶点S₁、S₂、S₃、S₄、S₅、S₆、S₇、 S₈构成实体多边形。在完成裁剪多边形与实体多边形线段求交后，由于顶点C₁与S₁、C₂与S₃、C₄与S₇坐标相同，所以在交点集合T中存在两个以上与顶点 C₁(顶点S₁)、顶点C₂(顶点S₃)以及顶点C₄(顶点S₇)坐标相同的交点，由 于待插入多边形顶点中的交点集合需要其坐标唯一，因此需要对存在两个以上相 同坐标的交点情况进行相应处理。

如图5所示，当存在两个以上相同坐标的交点情况时的处理步骤如下：

(1)在交点集合T中存在相同坐标交点数量N>2；

(2)该交点坐标与裁剪多边形的顶点C_i坐标相同，同时该交点坐标与实体 多边形的顶点S_j坐标相同；

(3)判断以以顶点C_i为起点的边C_iC_i+1与实体多边形的边S_j-1S_j与边S_jS_j+1是否共线；.

(4)不存在共线，边C_iC_i+1与顶点S_j-1、S_j和S_j+1构成的内角∠S_j-1S_jS_j+1的 关系，如果边C_iC_i+1在内角∠S_j-1S_jS_j+1内部，则顶点C_i为进点，在内角∠S_j-1S_jS_j+1的外部，则顶点C_i为出点，顶点S_j为进点；

(5)如果存在共线，判断边C_i+1C_i与顶点S_j-1、S_j和S_j+1构成的内角∠S_j-1S_jS_j+1的关系，如果边C_i-1C_i在内角∠S_j-1S_jS_j+1的内部，则顶点C_i为出点；如果边C_i-1C_i在内角∠S_j-1S_jS_j+1的外部，则顶点C_i为进点，顶点S_j为出点；

(6)删除交点集合T和Q中存在两个以上相同坐标的交点。

通过上述两个实施例可以看出，本发明的多边形裁剪中交点为多边形顶点 的进出性判别方法，步骤简单易实现并且准确度高，可以精准的根据交点的进出 性得到准确的裁剪结果。