【摘要】 提出了一个简单多边形集凸包的快速算法。先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线。应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包。算法的时间复杂度为线性O(n),并且给出一个例子进行了验证。更多还原

【Abstract】 A fast algorithm for computing convex hull of a set of simple polygons is presented.According to the tangent property of convex hull,a strict monotone polygonal line is extracted from the related sub-convex-hulls of simple polygons,which are constructed based on the algorithm of convex hull of simple polygon,and then some strict monotone polygonal lines are merged to a strict monotone polygonal line,so that these strict monotone polygonal lines and some edges that are on the box of the set of sub-convex-hulls form a closed polygonal line,namely a simple polygon.The time complexity of the algorithm is linear.An example is taken to verify the algorithm.更多还原