[发明专利]多边形裁剪中交点为多边形顶点的进出性判别方法

摘要

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

主权项

一种多边形裁剪中交点为多边形顶点的进出性判别方法，其特征在于包括以下具体步骤：(1)在裁剪多边形C与实体多边形S之间交点求解，且在交点的进出性预判别之后，计算交点集合中具有相同坐标交点的个数；其中，用Ci代表裁剪多边形的第i个顶点，用Sj代表实体多边形的第j个顶点，T表示裁剪多边形和实体多边形求交后的交点集合，Tk代表添加到裁剪多边形中交点集合T中第k个交点，Ql代表添加到实体多边形顶点序列中的交点集合Q的第l个点，其中i,j,k,l∈[1,2…,n]，NT为新添加到裁剪多边形顶点序列新添加到Tk中的交点，NQ为新添加到Ql中的交点；(2)当具有相同坐标交点的个数N等于2时，说明裁剪多边形与实体多边形存在相同的顶点，且顶点坐标等于交点坐标，假设这两个交点分别表示为Tk与Tk+1，Q中与Tk与Tk+1坐标相同的两个交点分别为Ql与Ql+1，则该顶点进出性的判别步骤如下：(21)如果Tk与Tk+1的进出性相同：①若交点Tk与Tk+1的坐标与顶点Ci坐标不相等，交点Ql与Ql+1的坐标与顶点Sj坐标相同，则交点Tk与Tk+1是裁剪过程中的需要添加的交点，添加一个交点NT，其中该交点坐标及进出性均与Tk相同，且交点Ql与Ql+1是裁剪过程中的顶点坐标，设置Sj的进出性与顶点Ci的进出性相异；②若交点Tk与Tk+1的坐标与顶点Ci坐标相等，交点Ql与Ql+1的坐标与顶点Sj坐标相同，则交点Tk与Tk+1是裁剪过程中顶点，设置顶点Ci的进出性等于交点Tk与Tk+1的进出性；交点Ql与Ql+1是裁剪过程中需要添加的交点，添加一个新点NQ，该交点坐标及其进出性与Ql相同；③从交点集合T中删除交点Tk与Tk+1，交点集合Q中删除交点Ql与Ql+1；(22)如果Tk与Tk+1的进出性不相同：①若交点Tk与Tk+1的坐标与顶点Ci坐标不等，交点Ql与Ql+1的坐标与顶点Sj坐标相等，判别交点Tk与Tk+1的先后顺序以及后一个交点的进出性，进而判别顶点Sj的进出性，并向T中添加新交点NT，其中NT的坐标及进出性与Sj相同；②若交点Tk与Tk+1的坐标与顶点Ci坐标相等，交点Ql与Ql+1的坐标与顶点Sj坐标相等，判别交点Tk与Tk+1的先后顺序，依据得到交点Tk与Tk+1裁剪多边形线段的先后顺序，进而得到顶点Ci的进出性，向Q中添加新交点NQ，其中NQ的坐标与顶点Ci的坐标相同，进出性相异；③从交点集合T中删除交点Tk与Tk+1，交点集合Q中删除交点Ql与Ql+1；(23)完成对交点集合T和Q中所有存在两个相同坐标的交点的处理，设置相应多边形顶点的进出性，更新交点集合T中的交点；(3)当具有相同坐标交点的个数N大于2时，则顶点进出性的判别步骤如下：(31)该交点坐标与裁剪多边形的顶点Ci坐标相同，同时该交点坐标与实体多边形的顶点Sj坐标相同；(32)判断以顶点Ci为起点的边CiCi+1与实体多边形的边Sj‑1Sj与边SjSj+1是否共线；(33)如果不存在共线，边CiCi+1与顶点Sj‑1、Sj和Sj+1构成的内角∠Sj‑1SjSj+1的关系，如果边CiCi+1在内角∠Sj‑1SjSj+1内部，则顶点Ci为进点，在内角∠Sj‑1SjSj+1的外部，则顶点Ci为出点，顶点Sj为进点；(34)如果存在共线，判断边Ci+1Ci与顶点Sj‑1、Sj和Sj+1构成的内角∠Sj‑1SjSj+1的关系，如果边Ci‑1Ci在内角∠Sj‑1SjSj+1的内部，则顶点Ci为出点；如果边Ci‑1Ci在内角∠Sj‑1SjSj+1的外部，则顶点Ci为进点，顶点Sj为出点；(35)删除交点集合T和Q中存在两个以上相同坐标的交点。