一种构建平面离散点集凸包的算法研究

A Vector Algorithm Research on the Construction of the Convex Hull of a Set of Planar Point

本文提出一种矢量运算方法确定平面离散点集凸包 ,其原理是在构建凸包前 ,通过矢量计算判别出位于凸包多边形内部的点 ,预先将其删去 ,保留凸包多边形外部边缘的点 ,从而减少了构建凸包的离散点数目 ,提高运算速度。新算法达到O(nlogn)时间复杂度下限 ,简单且易于实现 .

This paper presents a vector algorithm for constructing the convex hull of a set of planar discrete points.The computing method is to remove all or most points lying in the interior of the hull and reserve the possible vertices of the exterior boundary of the hull before the convex hull is constructed.Therefore,the number of the points for constructing the convex hull is greatly reduced.The computing rate is improved and the constructed efficiency is enhanced.