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

A WEIGHTING ALGORITHM FOR DECOMPOSING A SIMPLE POLYGON INTO CONVEX POLYGONS

本文提出可以为简单多边形中的可视点对建立一种权函数．这种权函数容易计算，可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质，因此可以用来引导剖分．描述了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤，讨论了所建立算法的性质．结果表明算法既能够使剖分得到凸多边形的数目较少，又能够使得到的剖分有较好的形态质量，因此有很好的实用性．

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.