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

摘要

本发明公开一种多边形裁剪中交点为多边形顶点的进出性判别方法，在裁剪多边形C与实体多边形S之间交点求解，且在交点的进出性预判别之后，计算交点集合中具有相同坐标交点的个数，并针对交点中存在重点现象，分为存在两个相同坐标的交点情况和存在两个以上相同坐标的交点情况的不同情况分别进行阐述，进而确定交点的进出性，最终可得到精准的裁剪结果。本发明步骤简单易实现，准确度高。

主权项

一种多边形裁剪中交点为多边形顶点的进出性判别方法，其特征在于包括以下具体步骤：(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中存在两个以上相同坐标的交点。