改进的加权剖分简单多边形为凸多边形的算法  

A Improved Weighting Algorithm for Decomposing a Simple Polygon into Convex Polygons

作　　者：张玉连[1] 

机构地区：[1]燕山大学信息科学与工程学院,秦皇岛066004

出　　处：《燕山大学学报》2001年第1期76-79,共4页Journal of Yanshan University

摘　　要：对加权剖分简单多边形为凸多边形算法的权函数做了改进，新的权函数容易计算，可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质，因此可以用来引导剖分。给出了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤，讨论了所建立算法的性质。结果表明算法既能够使剖分得到的凸多边形数目较少，又能够使得到的剖分具有较好的形态质量，因此有很好的实用性。In this paper, a improved weight function for the algorithm in decomposing simple polggon into convex polggons is presented.The ne wweight function can be evaluated easily,and express the shape quality of obtained decomposition in adding the decomposing line between a pa ir of vertexes,so it can be used to conduct the decomposing procedure. A weighting algorithm for decomposing a simple polygon into convex pol ygons using the weight function is described,some properties are discu ssed. It is possible to reduce the polygons and improve the aspect ra tio of the resulting convex polygons. The algorithm runs very efficien tly and fits to use in practice.

关 键 词：权函数 剖分 简单多边形 凸多边形 计算几何学 算法 

分 类 号：O18[理学—数学]