有孔多边形凸到分的ー种算法

该算法利用单调链对有内孔的多边形进行凸划分，包括3个步骤：首先将有孔多边形分解为有序单调链；其次通过组合和分裂单调链，逐次拆分出单调多边形；最后将单调多边形划分为凸多边形。每个步骤都给出了证明和复杂性分析。实验和分析说明算法平均复杂性接近O（nlg(n)）．

A Convex Partition Algorithm for a Polygon with Holes

The algorithm makes convex partition of a polygon with holes using monotone chains, it in?cludes three stages： the first one decomposes a polygon with holes into ordered monotone chains; the second one divides the original polygon with holes into monotone polygons through combinations and splits of ordered monotone chains; the third one partitions every monotone polygon into convex poly?gons. Proofs and complexity analysis of all stages in the algorithm were given. The experiment and analysis show that the average complexity of the algorithm approximates O(nlgn).