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

摘要

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