基于矢量游走的任意非自交图形合并算法  

Non-self-intersection graphics combination algorithm based on vector wander method

作　　者：刘术华[1] 周云燕[1] 曹立强[1] 万里兮[1] 

机构地区：[1]中国科学院微电子研究所,北京100029

出　　处：《计算机工程与设计》2012年第1期186-191,共6页Computer Engineering and Design

基　　金：国家科技重大专项基金项目(2009ZX02038)

摘　　要：图形处理软件中,常常需要将许多非自交图形合并成一个图形,提出一种基于矢量游走的任意非自交多边形合并算法,提出了适合于多边形合并运算的改进矢量游走规则及交点转移条件。通过将交点和两相交矢量边联合处理,对交点分类,有效地去除了"伪交点",进而简化了重合交点处理。提出用带凸度线段的方式来表示圆和含圆弧边的多边形,成功地将矢量游走规则运用到这些复杂多边形的快速合并当中。Non-self-intersection graphics are needed to merge into one graphic, which is commonly used in graphics processing software. An inner hole polygon combination algorithm based on vector wander method is introduced, and the related rules and converge shift conditions are proposed. The simplification of coincidence intersection processing is proposed by combinational handling the intersection and the intersected vectors, then the intersection is assorted and the fake intersection is eliminated efficiently. The principle of vector wandering is applied to the mergence of the polygons by using convex section of line to indicate circle and polygon with circular arc.

关 键 词：多边形 带孔多边形 矢量游走 合并运算 重合顶点 凸度 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]