摘要
二维凸包问题是计算几何领域的经典问题之一,在地理信息系统中有广泛的应用.在凸包中,位于两凸点之间直线上点也在凸包上,但不是凸点,如何寻找凸点是凸包算法的关键.提出了基于夹角的平面点集凸包改进算法,以最大夹角,按顺时针的方向可得到所有的凸点,当满足最大夹角的点不唯一时,以离当前凸点最远的点为凸点.
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.
出处
《信阳师范学院学报（自然科学版）》
CAS
北大核心
2007年第4期508-510,共3页
Journal of Xinyang Normal University(Natural Science Edition)
基金
国家自然科学基金项目(10671166)
河南省教育厅自然科学基金项目(2006520012)
关键词
夹角
凸包
凸点
Included angle
convex hull
convex points
