一个简单多边形凸单元剖分的算法

通过分析剖分得到的凸多边形的结构特点，发现了剖分线的特征性质，并引入可视链及可视度的概念加以描述。在此基础上，给出了一个利用剖分线的特征性质剖分简单多边形为凸多边形的剖分算法，算法消除了剖分后存在部分凸多边形可以合并的现象，既能使剖分得到的凸多边形数目较少，又能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率，因此有很好的实用性。

Algorithm for decomposing simple polygon into convex parts

In this paper , through analyzing the structure characteristic of the convex polygon which produced by decomposing, we review the properties of the decomposing line, find that there is a internal relation between the two endpoints of the decomposing line, one of the two endpoints is a concave point of the simple polygon, and another endpoint is in the continue sequences of the point which is visual to the concave point, so we defined the concepts Visual Link (VL) and Visual Degree (VD) in order to describe the internal relation. Based on this, a simple and effective decomposing algorithm using the structure characteristic of decomposing line is presented, and the algorithm avoid combined phenomenon which has been produced by other algorithms. Many instance indicate that, the algorithm runs very efficiently and makes fewer numbers and better aspect ratio of the resulting convex polygon, so it fits to use in practice.