摘要
从集合和几何的基本原理出发,提出了复合多边形求差的一种矢量算法。算法首先区分多边形的拓扑相离、包含或相交关系。对于拓扑相离或包含的两个多边形,其差容易计算;对于相交的两个多边形,应用平行线扫描算法来求解,得到两个复合多边形的差。该算法的特点是可以解决嵌套了任意层次孔洞的两个多边形之间的求差运算,这在计算机辅助设计、地理信息系统、地图数据处理等领域具有较广泛的应用前景。
Rooting in the basic principles of set theory and geometry, this paper proposed a vector-based algorithm. The algo- rithm firstly discerned three types of topological relations between polygons, i.e. interseetional, contained, separated. If the two polygons were separated or contained, then it could easily get the difference of them ; otherwise, it obtained the difference using the parallel line scanning method. The proposed algorithm can be used for computing the differences of two arbitrary po- lygons, including two polygons with multiply embedded holes （ polygons）, which is of great useful in computer-aided design, geographic information systems and cartography.
出处
《计算机应用研究》
CSCD
北大核心
2013年第10期3192-3194,共3页
Application Research of Computers
基金
国家科技支撑计划资助项目(2013BAB05B01)
国家教育部创新团队支持计划资助项目(IRT0966)
关键词
复合多边形
矢量
算法
计算几何
complex polygons
vector
algorithms
computational geometry
