| Citation: | CUI Y P，LI Z H，ZHENG G L. Computing convex hull of a generic polygon with simulation of progressive support for an elastic line[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（1）：216-223 （in Chinese） doi: 10.13700/j.bh.1001-5965.2022.0246
|
The computation of the convex hull of the Jordan curve has found widespread application in recent years. A simulation of progressive support for an elastic line approach was suggested in this paper to determine the elastic envelope of a straightforward closed generic polygon. Based on the physical model, this algorithm could determine whether a point was a balanced fulcrum on the elastic envelope line by judging whether it was balanced by force. According to these findings, the algorithm performed different operations such as forward, spring-back, and jump respectively, until all the balanced support points were selected and the elastic envelope was eventually generated. The contrastive analysis of three typical generic polygons demonstrates that the proposed algorithm can solve the elastic envelope of arbitrary simple closed generic polygons synchronously, and it is robust, efficient, and universally applicable.
| [1] |
GRAHAM R L. An efficient algorithm for determining the convex hull of a finite planar set[J]. Information Processing Letters, 1972, 1(4): 132-133. doi: 10.1016/0020-0190(72)90045-2
|
| [2] |
JARVIS R A. On the identification of the convex hull of a finite set of points in the plane[J]. Information Processing Letters, 1973, 2(1): 18-21. doi: 10.1016/0020-0190(73)90020-3
|
| [3] |
PREPARATA F P, HONG S J. Convex hulls of finite sets of points in two and three dimensions[J]. Association for Computing Machinery, 1977, 20(2): 87-93. doi: 10.1145/359423.359430
|
| [4] |
LINH N K, AN P T, HOAI T V. A fast and efficient algorithm for determining the connected orthogonal convex hulls[J]. Applied Mathematics and Computation, 2022, 429: 127183. doi: 10.1016/j.amc.2022.127183
|
| [5] |
SKLANSKY J. Measuring concavity on a rectangular mosaic[J]. IEEE Transactions on Computers, 1972, 100(12): 1355-1364.
|
| [6] |
MCCALLUM D, AVIS D. A linear algorithm for finding the convex hull of a simple polygon[J]. Information Processing Letters, 1979, 9(5): 201-206. doi: 10.1016/0020-0190(79)90069-3
|
| [7] |
LEE D T. On finding the convex hull of a simple polygon[J]. International Journal of Computer & Information Sciences, 1983, 12(2): 87-98.
|
| [8] |
MELKMAN A A. On-line construction of the convex hull of a simple polyline[J]. Information Processing Letters, 1987, 25(1): 11-12. doi: 10.1016/0020-0190(87)90086-X
|
| [9] |
CHEN C L. Computing the convex hull of a simple polygon[J]. Pattern Recognition, 1989, 22(5): 561-565. doi: 10.1016/0031-3203(89)90023-X
|
| [10] |
吴中海, 叶澄清, 潘云鹤. 一个改进的简单多边形凸包算法[J]. 计算机辅助设计与图形学学报, 1997, 9(1): 9-13.
WU Z H, YE C Q, PAN Y H. An improved algorithm of convex hull computing[J]. Journal of Computer-Aided Design & Computer Graphics, 1997, 9(1): 9-13(in Chinese).
|
| [11] |
孔宪庶, 蔡洪学. 简单多边形凸包的双动线检测算法[J]. 计算机学报, 1994, 17(8): 596-600.
KONG X S, CAI H X. An algorithm for finding the convex hull of a simple polygon using active double line testing[J]. Chinese Journal of Computers, 1994, 17(8): 596-600(in Chinese).
|
| [12] |
王丽青, 陈正阳, 陈树强, 等. 一个改进的简单多边形凸包算法[J]. 计算机工程, 2007, 33(3): 200-201. doi: 10.3969/j.issn.1000-3428.2007.03.072
WANG L Q, CHEN Z Y, CHEN S Q, et al. An improved algorithm of simple polygon convex hull[J]. Computer Engineering, 2007, 33(3): 200-201(in Chinese). doi: 10.3969/j.issn.1000-3428.2007.03.072
|
| [13] |
张林. 改进的多边形凸包算法[J]. 长春工业大学学报(自然科学版), 2013, 34(5): 560-563.
ZHANG L. An improved algorithm of polygon convex hull[J]. Journal of Changchun University of Technology(Natural Science Edition), 2013, 34(5): 560-563(in Chinese).
|
| [14] |
刘子尧. 基于夹角的凸包算法改进[J]. 软件导刊, 2018, 17(4): 94-96.
LIU Z Y. Improvement of convex hull algorithm based on included angle[J]. Software Guide, 2018, 17(4): 94-96(in Chinese).
|
| [15] |
WANG C, ZHOU R G. A quantum search algorithm of two-dimensional convex hull[J]. Communications in Theoretical Physics, 2021, 73(11): 115102. doi: 10.1088/1572-9494/ac1da0
|
| [16] |
杨宏伟. 平面散乱点云凸包快速求解算法[J]. 机械研究与应用, 2021, 34(2): 55-56.
YANG H W. Accelerating algorithm for convex hull construction of 2d scattered point cloud[J]. Mechanical Research & Application, 2021, 34(2): 55-56 (in Chinese).
|
| [17] |
林晓, 刘祖祥, 郑晓妹, 等. 基于凸包改进的流行排序显著性检测[J]. 计算机辅助设计与图形学学报, 2019, 31(5): 761-770.
LIN X, LIU Z X, ZHENG X M, et al. Saliency detection based on improved manifold ranking via convex hull[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(5): 761-770(in Chinese).
|
| [18] |
CHEN M M, ZHENG D, RENG X Q. Research on gesture recognition technology based on convex hull algorithm[J]. Scientific Journal of Intelligent Systems Research, 2021, 3(7): 192-199.
|
| [19] |
武伟璐. 基于快速凸包算法的4D航迹规划研究[D]. 天津: 中国民航大学, 2020.
WU W L. Research on 4D trajectory planning based on quickhull algorithm[D]. Tianjin: Civil Aviation University of China, 2020(in Chinese).
|
| [20] |
WU Y, GUPTA A, KURZEJA K, et al. Chocc: Convex hull of cospherical circles and applications to lattices[J]. Computer-Aided Design, 2020, 129: 102903. doi: 10.1016/j.cad.2020.102903
|
| [21] |
NGUYEN L K, SONG C, RYU J, et al. QuickhullDisk: A faster convex hull algorithm for disks[J]. Applied Mathematics and Computation, 2019, 363: 124626. doi: 10.1016/j.amc.2019.124626
|
| [22] |
ELBER G, KIM M S, HEO H S. The convex hull of rational plane curves[J]. Graphical Models, 2001, 63(3): 151-162. doi: 10.1006/gmod.2001.0546
|
| [23] |
KIM Y J, LEE J, KIM M S, et al. Efficient convex hull computation for planar freeform curves[J]. Computers & Graphics, 2011, 35(3): 698-705.
|
Figures(10) / Tables(1)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
