Efficient convex hull algorithm for plane point set

doi:10.3778/j.issn.1002-8331.2009.01.016

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (1): 56-58.DOI: 10.3778/j.issn.1002-8331.2009.01.016

• 理论研究 • Previous Articles Next Articles

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

平面点集凸壳的快速算法

赵军¹,曲仕茹²

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

通讯作者: 赵军

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

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

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

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

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

[1]	WANG Jiarun, SUN Yunan, YIN Hui, YANG Zhilong. Terrain Fitting and Double Convex Preserving for Visual Modeling of Military Target Relations [J]. Computer Engineering and Applications, 2020, 56(5): 270-278.
[2]	DONG Benzhi, YU Shangshu, JING Weipeng. Salient Object Detection Algorithm via Multiple Prior Fusion [J]. Computer Engineering and Applications, 2019, 55(2): 179-186.
[3]	LI Gefei1, MA Weiyin2, LI Li3. Convex hull problem based on Spark platform [J]. Computer Engineering and Applications, 2018, 54(22): 67-73.
[4]	YANG Xiujuan1, DONG Jun1, LI Huihui2. Research of reverse furthest neighbors query in euclidean space [J]. Computer Engineering and Applications, 2015, 51(4): 142-147.
[5]	ZHAO Jianfang1, QIAN Xuezhong1, JIA Zhiwei2. Constraints extending method based on convex hull [J]. Computer Engineering and Applications, 2014, 50(4): 173-176.
[6]	HUANG Ke, XUE Yueju, CHEN Yao, CHEN Hanming, LI Hongsheng. Research on QR code images geometric rectification algorithm [J]. Computer Engineering and Applications, 2014, 50(20): 192-196.
[7]	WANG Zhihua, DAI Linsong, CHEN Sugen, SU Benyue. Timmer-like curve [J]. Computer Engineering and Applications, 2014, 50(10): 161-164.
[8]	ZHOU Xuemei1, LI Yingfei2. Algorithm research to generate triangulation network based on Bowyer-Watson [J]. Computer Engineering and Applications, 2013, 49(6): 198-200.
[9]	Cairangzhuoma1, ZHANG Mingcheng2. Aircraft recognition via structural features [J]. Computer Engineering and Applications, 2013, 49(4): 174-177.
[10]	CHANG Zhenhua1，CHEN Bocheng1，LI Yingjie2，LIU Wenhuang1，YAN Xuewei3. Study on geometric approach of SVM algorithm——SK algorithm analysis and study [J]. Computer Engineering and Applications, 2011, 47(8): 149-153.
[11]	LI Xuehui，WEI Lili. Multi-classification algorithm based on contraction of closed convex hull [J]. Computer Engineering and Applications, 2011, 47(31): 135-137.
[12]	LIU Wenjing1，TIAN Zheng1，2，ZHANG Zhaoyang1. Convex hull sequence method using graph spectra in image point pattern matching [J]. Computer Engineering and Applications, 2011, 47(23): 197-200.
[13]	ZHAO Jun¹，GAO Mantun²，WANG Sanmin². Efficient convex hull method for simple polygon set in plane [J]. Computer Engineering and Applications, 2011, 47(1): 205-207.
[14]	WANG San¹，LIU Run-tao²，WANG Hong-yan¹. Algorithms for convex hull of union and intersection of two intersecting convex polygons [J]. Computer Engineering and Applications, 2010, 46(5): 154-156.
[15]	WU Chong-ming，WANG Xiao-dan，BAI Dong-ying，ZHANG Hong-da. Fast SVM incremental learning algorithm based on between-class convex hull vectors [J]. Computer Engineering and Applications, 2010, 46(23): 185-187.

Efficient convex hull algorithm for plane point set

平面点集凸壳的快速算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics