一种处理交点退化现象的高效多边形裁剪算法-东南大学学报.PDFVIP

第４６卷第４期 东南大学学报（自然科 学版 ） Ｖｏｌ．４６ Ｎｏ．４ 　 ２０１６年７月 ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） 　 Ｊｕｌｙ２０１６ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－０５０５．２０１６．０４．００５ 一种处理交点退化现象的高效多边形裁剪算法 １ ２ 王慧青　　崇素文 １ （东南大学仪器科学与工程学院，南京２１００９６） ２ （展讯通信（上海）有限公司，上海２０１２０３） 摘要：针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象，提出了一种能够处理交点 退化现象的高效多边形裁剪算法．该算法利用单向链表实现多边形的存储，同时基于单调链的平 面扫描法求解多边形间的交点，减少了多边形顶点的遍历次数和求交次数；对于重点和重边现 象，通过交点关联的线段间的方向关系判别交点的进出性；最后更新多边形顶点序列，获取裁剪 结果．实验结果表明，该算法能够完成对含内环多边形的裁剪，在交点退化情况下也能获得准确 的裁剪结果．且该算法裁剪效率较ＧｒｅｉｎｅｒＨｏｒｍａｎｎ算法大幅提高，具有很高的执行效率和实 用性． 关键词：多边形裁剪；交点退化；单向链表；方向关系 中图分类号：ＴＰ３９１　　文献标志码：Ａ　　文章编号：１００１－０５０５（２０１６）０４０７０２０６ Ａｈｉｇｈｅｆｆｉｃｉｅｎｔｐｏｌｙｇｏｎｃｌｉｐｐｉｎｇａｌｇｏｒｉｔｈｍ ｆｏｒｄｅａｌｉｎｇｗｉｔｈｉｎｔｅｒｓｅｃｔｉｏｎｄｅｇｒａｄａｔｉｏｎ １ ２ ＷａｎｇＨｕｉｑｉｎｇ　　ＣｈｏｎｇＳｕｗｅｎ １ （ＳｃｈｏｏｌｏｆＩｎｓｔｒｕｍｅｎｔＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６，Ｃｈｉｎａ） ２ （ＳｐｒｅａｄｔｒｕｍＣｏｍｍｕｎｉｃａｔｉｏｎｓ（Ｓｈａｎｇｈａｉ）Ｃｏ．，Ｌｔｄ．，Ｓｈａｎｇｈａｉ２０１２０３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇａｔｃｏｍｐｌｅｘｐｏｌｙｇｏｎｃｌｉｐｐｉｎｇｗｉｔｈｃｏｉｎｃｉｄｅｎｃｅｐｏｉｎｔｓａｎｄｃｏｉｎｃｉｄｅｎｃｅｅｄｇｅｓ，ａ ｈｉｇｈｅｆｆｉｃｉｅｎｔａｌｇｏｒｉｔｈｍｆｏｒｐｏｌｙｇｏｎｃｌｉｐｐｉｎｇｉｓｐｒｏｐｏｓｅｄｆｏｒｄｅａｌｉｎｇｗｉｔｈｉｎｔｅｒｓｅｃｔｉｏｎｄｅｇｒａｄａｔｉｏｎ． Ｔｈｅａｌｇｏｒｉｔｈｍｕｓｅｓｓｉｎｇｌｙｌｉｎｋｅｄｌｉｓｔｓｔｏｓｔｏｒｅｐｏｌｙｇｏｎｓ，ａｎｄａｃｑｕｉｒｅｓｉｎｔｅｒｓｅｃｔｉｏｎｐｏｉｎｔｓｂｅｔｗｅｅｎｐｏｌ ｙｇｏｎｓｂａｓｅｄｏｎｔｈｅｐｌａｎａｒｓｃａｎｎｉｎｇｍｅｔｈｏｄｗｉｔｈａｍｏｎｏｔｏｎｅｃｈａｉｎ，ｔｈｕｓｒｅｄｕｃｉｎｇｔｈｅｔｉｍｅｓｏｆｔｒａｖｅｒ ｓｉｎｇｐｏｌｙｇｏｎｖｅｒｔｉｃｅｓａｎｄｃａｌｃｕｌａｔｉｎｇｉｎｔｅｒｓｅｃｔｉｏｎｓ．Ｔｈｅｎ，ｉｔｍａｒｋｓｔｈｅｅｎｔｒｙａｎｄｅｘｉｔｐｏｉｎｔｓｔｏｔｈｅ ｃｌｉｐｐｉｎｇｐｏｌｙｇｏｎｓｉｎｔｅｒｉｏｒｂａｓｅｄｏｎｔｈｅｄｉｒｅｃｔｉｏｎｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｌｉｎｅｓｅｇｍｅｎｔｓｗｉｔｈｉｎｔｅｒｓｅｃ ｔｉｏｎｓ．Ｆｉｎａｌｌｙ，ｉｔｕｐｄａｔｅｓｔｈｅｐｏｌｙｇｏｎｖｅｒｔｅｘｓｅｑｕｅｎｃｅａｎｄｏｂｔａｉｎｓ