复合多边形求差的高效矢量算法

摘要：

从集合和几何的基本原理出发, 提出了复合多边形求差的一种矢量算法。算法首先区分多边形的拓扑相离、包含或相交关系。对于拓扑相离或包含的两个多边形, 其差容易计算; 对于相交的两个多边形, 应用平行线扫描算法来求解, 得到两个复合多边形的差。该算法的特点是可以解决嵌套了任意层次孔洞的两个多边形之间的求差运算, 这在计算机辅助设计、地理信息系统、地图数据处理等领域具有较广泛的应用前景。

关键词：复合多边形、矢量、算法、计算几何

所属期刊栏目：30

分类号：TP391.41;P208(计算技术、计算机技术)

资助基金：国家科技支撑计划资助项目2013BAB05B01;国家教育部创新团队支持计划资助项目IRT0966

在线出版日期：2013-11-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：3192-3194