一种凹多边形凸分解的全局剖分算法  

Global Subdivision Algorithm on Convex Decomposition of Concave Polygon

作　　者：贺怀清[1] 杨鹏[1] 

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300

出　　处：《中国民航大学学报》2011年第3期52-55,共4页Journal of Civil Aviation University of China

摘　　要：提出了一种凹多边形凸分解的全局剖分算法。首先对局部剖分算法的原理及存在的问题进行了阐述,并对基于正负法搜索可视点串的算法进行了更正和改进,然后利用改进的权函数从全局剖分的角度选择最优的剖分点进行剖分。同局部剖分算法相比,提高了剖分后所得的多边形形态质量。该算法主要作为轮廓偏置算法的前期处理算法,对原轮廓进行分解,提高了原轮廓多边形进行轮廓偏置算法的运行效率。Proposed a global subdivision algorithm on the convex decomposition of concave polygon. First, the principle of local subdivision algorithm and the existed problems were described; Then it corrected and improved the search visual point string algorithm based on positive and negative method; last, chose the optimal split points to subdivide concave polygon by using the improved weight function from an overall perspective. Compared with the local subdivision algorithm, it improved polygon shape quality after subdivision. As a main preprocessing algorithm of contour offset, it decomposed the original contour and improved the efficiency of contour offset algorithm to the original contour polygon.

关 键 词：凹多边形 凸分解 全局剖分 局部剖分 正负法 轮廓偏置 

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