平面点集凸壳的快速算法  

Efficient convex hull algorithm for plane point set

作　　者：赵军[1] 曲仕茹[2] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070 [2]西北工业大学自动化学院,西安710072

出　　处：《计算机工程与应用》2009年第1期56-58,共3页Computer Engineering and Applications

基　　金：国家自然科学基金;兰州交通大学"青蓝"人才工程资助计划(No.QL-06-11A)~~

摘　　要：提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间。An efficient algorithm for computing the convex hull of plane point set is proposed.Firstly,according to the extremity point of the point set,the point on the convex hull is restricted in four rectangles.By scanning the point in rectangles the point which is in evidence not on the convex hull is eliminated,and remain points can constitute a simple polygon.Then,the convexityconcavity of polygon＇s vertex is recognized by the vertices sequence and all concavity vertexes are deleted.Lastly,a convex polygon is obtained and it is just the convex hull of the point set.Test results show the high efficiency and stability of this terse algorithm.

关 键 词：平面点集 凸壳 简单多边形 凹顶点 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]