求平面点集凸壳的一种新算法

doi:10.3778/j.issn.1002-8331.2009.03.016

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

求平面点集凸壳的一种新算法

刘润涛¹,王三²,安晓华²

1.哈尔滨理工大学信息与计算科学研究所，哈尔滨 150080
2.哈尔滨理工大学应用科学学院，哈尔滨 150080

收稿日期:2008-01-07 修回日期:2008-03-31 出版日期:2009-01-21 发布日期:2009-01-21
通讯作者: 刘润涛

New method for computing convex hulls of point sets on plane

LIU Run-tao¹,WANG San²,AN Xiao-hua²

1.Institute of Information and Scientific Computing Technology，Harbin University of Science and Technology，Harbin 150080，China
2.College of Applied Science，Harbin University of Science and Technology，Harbin 150080，China

Received:2008-01-07 Revised:2008-03-31 Online:2009-01-21 Published:2009-01-21
Contact: LIU Run-tao

摘要/Abstract

摘要： 在研究了大量的求平面点集凸包的算法基础上，提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点，构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域；对于一个线段区域上的点只需要找出右侧的点，分别和线段的两个端点连接得到新的多边形链，依次这样处理每个点，直到结束。这样就得到四个简单多边形单调链，然后对单调链求凸点，时间复杂度为O（n），最后求得的每个凸点就是平面点集的凸壳，此算法总的时间复杂度不超过O（n log n）。

关键词: 点集, 单调链, 凸壳

Abstract: A new algorithm of computing convex hulls of plane point sets is presented，based on the research on a large amount of algorithms of computing the convex hulls of plane point sets.In the algorithm，the four extreme points are first computed，which compose a quadrangle，then for the points out of the quadrangle we figure out which line sections they belong to in order with the method of bisection.For the points in the same line section，we just find out the points on the right side，then connect them with the two endpoints of the line section separately to compose a new polygon chain，then process each point in the same way until the last one.In this way，four monotonic chains of simple polygons are obtained，then the vertices of the convex hulls of the four monotonic chains are computed.Its time complexity is O（n）.All the vertices are the ones of the convex hull of the plane point set.The total time complexity of this algorithm is not more than O（n log n）.

Key words: point set, monotonic chains, convex hull

刘润涛¹,王三²,安晓华². 求平面点集凸壳的一种新算法[J]. 计算机工程与应用, 2009, 45(3): 58-59.

LIU Run-tao¹,WANG San²,AN Xiao-hua². New method for computing convex hulls of point sets on plane[J]. Computer Engineering and Applications, 2009, 45(3): 58-59.

[1]	孙俊，张曦煌. 基于节点集Top-k频繁模式挖掘算法[J]. 计算机工程与应用, 2017, 53(6): 101-105.
[2]	花秀娟. R0-代数的导子[J]. 计算机工程与应用, 2017, 53(21): 54-57.
[3]	雒培磊1，李国庆2，曾怡1. 一种改进的基于深度学习的遥感影像拼接方法[J]. 计算机工程与应用, 2017, 53(20): 180-186.
[4]	刘万军，杨笑，曲海成. 基于SQP局部搜索的蝙蝠优化算法[J]. 计算机工程与应用, 2016, 52(15): 183-189.
[5]	刘鹏程1，2，揭毅1，2，杨文博1，2. 临近特征点类型匹配的多边形渐变表达模型[J]. 计算机工程与应用, 2015, 51(22): 42-47.
[6]	赵建芳1，钱雪忠1，贾志伟2. 基于凸壳的约束信息扩展方法[J]. 计算机工程与应用, 2014, 50(4): 173-176.
[7]	周雪梅1，黎应飞2. 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200.
[8]	龙文1，徐松金2，焦建军1. 一种改进的约束优化差分进化算法[J]. 计算机工程与应用, 2012, 48(25): 34-38.
[9]	龙文. 一种改进的多目标约束优化差分进化算法[J]. 计算机工程与应用, 2012, 48(21): 5-8.
[10]	赵军¹，高满屯²，王三民². 求平面多边形集凸壳的方法[J]. 计算机工程与应用, 2011, 47(1): 205-207.
[11]	王三¹，刘润涛²，王洪艳¹. 求两个相交凸多边形并的凸包及交的算法[J]. 计算机工程与应用, 2010, 46(5): 154-156.
[12]	安维华，付永刚，张习文. 基于图像的点云建模及其真实感绘制[J]. 计算机工程与应用, 2010, 46(20): 4-8.
[13]	赵军¹,曲仕茹². 平面点集凸壳的快速算法[J]. 计算机工程与应用, 2009, 45(1): 56-58.
[14]	唐培和¹,蒋联源¹,宋佩华²,苏勤³. 基于凸壳的高密度点集物碰撞检测算法[J]. 计算机工程与应用, 2008, 44(16): 51-53.
[15]	杜国红徐克虎杜涛. 平面非规则曲线的一种快速识别与匹配算法[J]. 计算机工程与应用, 2007, 43(7期): 81-83.

求平面点集凸壳的一种新算法

New method for computing convex hulls of point sets on plane

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics