一个加权剖分简单多边形为凸多边形的算法  

A WEIGHTING ALGORITHM FOR DECOMPOSING A SIMPLE POLYGON INTO CONVEX POLYGONS

作　　者：王钲旋[1] 李文辉[1] 庞云阶[1] 

机构地区：[1]吉林大学计算机科学系,长春130023

出　　处：《计算机学报》1998年第3期229-233,共5页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文提出可以为简单多边形中的可视点对建立一种权函数．这种权函数容易计算，可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质，因此可以用来引导剖分．描述了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤，讨论了所建立算法的性质．结果表明算法既能够使剖分得到凸多边形的数目较少，又能够使得到的剖分有较好的形态质量，因此有很好的实用性．A weighting function for a pair of visible vertexes in simple polygon is presented. The weight function can be evaluated easily, and expresses the shape quality of obtained decomposition in adding the decomposing line between a pair of vertexes. So it can be used to conduct the decomposing procedure. A weighting al-gorithm for decomposing a simple polygon into convex polygons, using the weight function, is described. Some properties are discussed. It is possible to make fewer numbers and better aspect ratio of the resulting convex polygons. The algorithm runs very efficiently and fits to use in practice.

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

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