摘要
本文提出一种矢量运算方法确定平面离散点集凸包 ,其原理是在构建凸包前 ,通过矢量计算判别出位于凸包多边形内部的点 ,预先将其删去 ,保留凸包多边形外部边缘的点 ,从而减少了构建凸包的离散点数目 ,提高运算速度。新算法达到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.
出处
《上海应用技术学院学报(自然科学版)》
2003年第2期118-120,共3页
Journal of Shanghai Institute of Technology: Natural Science