任意多边形区域交的有效算法  

Effective algorithm on intersection of arbitrary polygonal regions

作　　者：侯宝明[1] 刘雪娜[1] 

机构地区：[1]渤海大学信息科学与工程学院,辽宁锦州121000

出　　处：《计算机辅助工程》2009年第2期73-76,共4页Computer Aided Engineering

摘　　要：为有效进行任意多边形区域的交运算,采用接缝技术消除多边形区域内部的孔洞,化复连通域为单连通域,通过单连通域的交集得到复连通域的交.改写Weiler-Atherton裁减算法的交点遍历方法,以便在跟踪时跳过接缝,同时借助队列保存这些接缝的节点,确保能正确得到交集区域的每条边界.算法无须包容性测试就能自然得到交集的外边界与孔洞的包容关系.与已有算法相比,该算法具有更高的稳定性和健壮性,特别适合计算带有孔洞区域的交、并、差运算.To compute the intersection of arbitrary polygonal regions effectively, the seam technique is used to remove all the holes in a polygonal region and the multiple connected region is transformed into a single one. The intersection of multiple connected regions is obtained by the intersection set of single connected regions. The traversing method about intersection point in Weiler-Atherton clipping algorithm is overwritten to jump over the seals while tracing and a queue is set up to save the jumped-over nodes of the seals. Therefore every border of the intersection regions can be correctly obtained. Without the containing test, the containing relations between the outside borders and their holes are naturally obtained. Compared with the existing algorithms, the algorithm has higher stability and robustness and is very suitable for the computation of the intersection, union and difference among the regions with holes.

关 键 词：复连通域 单连通域 多边形 交 裁剪 接缝 孔洞 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]