简单多边形分解成凸多边形差组合的算法

Algorithm for Finding Convex Decomposition of Simple Polygons

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N^2),其中N为原多边形的边数。

An Algorithm for finding convex decomposition of simple polygons is described. This algorithm finds the convex hull of a simple polygon and then recurses to find the convex hull of the original region and itsconvex hull until such regions are convex. The time complexity of the algorithm is proved to be O(n2) , where N is the number of edges of the original polygon.