基于有序简单多边形的平面点集凸包快速求取算法

A FAST CONVEX HULL ALGORITHM OF PLANAR POINT SET BASED ON SORTED SIMPLE POLYGON

凸包问题是计算几何的基本问题之一，在许多领域均有应用．传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干．本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法．该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包．本文算法不仅达到了O（nlogn）的理论时间复杂度下限，而且算法极其简单，易于实现．本文方法已应用于工厂设计软件PDSOFT中，实践证明效果很好．

Convex hull problem is one of the fundamental problems in computational geometry, and used in many fields. The traditional convex hull algorithms of planar point set and those of simple polygon were developed in parallel, without any combination-In this paper, a new algorithm is proposed by combining improved convex hull algorithm of simple polygon to solve the problem of planar pointset. The algorithm firstly eliminates those points which are obviously not on the hull, then sorts the points that remain, and then links the points into a sorted simple polygon according to the definite order. Finally it searches the convex hull of the polygon using forward-backward method, and thereby obtains the convex hullof the point set. The algorithm not only reaches the theoretical lower bound ofO(nlogn),but also is very simple and easy to be realized. The presented algorithm has been applied in plant design system PDSOFT. The results obtained by the method are remarkable.