基于夹角的二维凸包改进算法

二维凸包问题是计算几何领域的经典问题之一,在地理信息系统中有广泛的应用.在凸包中,位于两凸点之间直线上点也在凸包上,但不是凸点,如何寻找凸点是凸包算法的关键.提出了基于夹角的平面点集凸包改进算法,以最大夹角,按顺时针的方向可得到所有的凸点,当满足最大夹角的点不唯一时,以离当前凸点最远的点为凸点.

An Improved Algorithm of Two Dimensional Convex Hull Based on Included Angle

Two dimensional convex hull is one of the typical problems in computational geometry and widely applied in GIS.In convex hull,some points in the convex hull,such as the points lie in the line between the two convex points but not convex points.How to seek the convex points is the key issue of the convex hull algorithm.An improved algorithm of two dimensional convex hull based on included angle is proposed,and all the convex points are achieved through the maximal included angle by the increasing counter-clockwise direction.When more than one point satisfies the maximal included angle,the most distant point to the previous point is regarded as the next convex point.