平面点集凸壳的快速算法

doi:10.3778/j.issn.1002-8331.2009.01.016

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (1): 56-58.DOI: 10.3778/j.issn.1002-8331.2009.01.016

平面点集凸壳的快速算法

赵军¹,曲仕茹²

1.兰州交通大学数理与软件工程学院，兰州 730070
2.西北工业大学自动化学院，西安 710072

收稿日期:2008-04-29 修回日期:2008-07-29 出版日期:2009-01-01 发布日期:2009-01-01
通讯作者: 赵军

Efficient convex hull algorithm for plane point set

ZHAO Jun¹,QU Shi-ru²

1.Lanzhou Jiaotong University，Lanzhou 730070，China
2.Northwestern Polytechnical University，Xi’an 710072，China

Received:2008-04-29 Revised:2008-07-29 Online:2009-01-01 Published:2009-01-01
Contact: ZHAO Jun

摘要/Abstract

摘要： 提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形，它们包含了所有凸壳顶点，通过对矩形中的点进行扫描，排除明显不是凸壳顶点的点，剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点，最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了，避免了乘法运算（除最坏情况外），从而节省计算时间。

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

Abstract: 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 convexity-concavity 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.

Key words: plane point set, convex hull, simple polygon, concave vertex

赵军¹,曲仕茹². 平面点集凸壳的快速算法[J]. 计算机工程与应用, 2009, 45(1): 56-58.

ZHAO Jun¹,QU Shi-ru². Efficient convex hull algorithm for plane point set[J]. Computer Engineering and Applications, 2009, 45(1): 56-58.

[1]	刘鹏程1，2，揭毅1，2，杨文博1，2. 临近特征点类型匹配的多边形渐变表达模型[J]. 计算机工程与应用, 2015, 51(22): 42-47.
[2]	赵建芳1，钱雪忠1，贾志伟2. 基于凸壳的约束信息扩展方法[J]. 计算机工程与应用, 2014, 50(4): 173-176.
[3]	周雪梅1，黎应飞2. 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200.
[4]	赵军¹，高满屯²，王三民². 求平面多边形集凸壳的方法[J]. 计算机工程与应用, 2011, 47(1): 205-207.
[5]	王三¹，刘润涛²，王洪艳¹. 求两个相交凸多边形并的凸包及交的算法[J]. 计算机工程与应用, 2010, 46(5): 154-156.
[6]	安维华，付永刚，张习文. 基于图像的点云建模及其真实感绘制[J]. 计算机工程与应用, 2010, 46(20): 4-8.
[7]	王洪艳¹，刘润涛²，王三¹. 简单多边形核求解新算法[J]. 计算机工程与应用, 2010, 46(17): 166-168.
[8]	刘润涛¹,王三²,安晓华². 求平面点集凸壳的一种新算法[J]. 计算机工程与应用, 2009, 45(3): 58-59.
[9]	董秀山,刘润涛. 判断点与简单多边形位置关系的新算法[J]. 计算机工程与应用, 2009, 45(2): 185-186.
[10]	唐培和¹,蒋联源¹,宋佩华²,苏勤³. 基于凸壳的高密度点集物碰撞检测算法[J]. 计算机工程与应用, 2008, 44(16): 51-53.
[11]	樊广佺王小牛杨炳儒. 平面点集凸壳的一种近似算法[J]. 计算机工程与应用, 2007, 43(12): 40-41.

平面点集凸壳的快速算法

Efficient convex hull algorithm for plane point set

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics