[发明专利]一种解决交点退化问题的复杂多边形裁剪方法

摘要

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

主权项

一种解决交点退化问题的复杂多边形裁剪方法，其特征在于：所述步骤包括：（1）假设被裁剪多边形即实体多边形为S，裁剪多边形为C，将含孔洞的复杂实体多边形分解成多个由外环和N个内环构成的不含孔洞的简单多边形，其中N≧0；（2）对实体多边形的外环边界构成的多边形与裁剪多边形进行求交即S∩C操作，得到裁剪结果；（3）若S不含孔洞，则直接输出这个裁剪结果；否则，继续步骤4；（4）将结果多边形视为裁剪多边形，某一孔洞构成的多边形视为实体多边形，对结果多边形与孔洞构成的多边形进行求差即C－S操作，得到裁剪结果；（5）取下一个孔洞构成的多边形，继续步骤4，直至所有孔洞构成的多边形处理完毕，输出最终的裁剪结果。