简单多边形凸单元剖分算法的设计及实现

Algorithm design and realization for decomposing simple polygon into convex parts

简单多边形凸单元剖分是计算几何的基本问题之一,剖分算法在许多领域均有较广泛的应用。本文给出了一个利用剖分线的特征性质,剖分简单多边形为凸多边形的剖分算法。算法消除了剖分后存在部分凸多边形可以合并的现象,既能使剖分得到的凸多边形数目较少,能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率,因此有很好的实用性。

Decomposing a simple polygon into convex cell is one of elementary problems of computational geometry. Decomposing algorithm apply widely in many fields. In this paper, 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, so it fits to use in practice.