Computing convex hull of a generic polygon with simulation of progressive support for an elastic line
-
摘要:
针对诸多领域涉及的平面弯曲图形的凸包计算，提出弹性线递支模拟算法用于计算简单闭广义多边形的弹性包络线。所提算法基于物理模型，通过判断各支点是否受力平衡来判别其是否为弹性包络线上的平衡支点，并据此分别进行前进、回弹和跳跃等操作，直至计算出所有平衡支点进而求出其弹性包络线。3种典型的简单闭广义多边形的对比测算表明：所提算法可实时稳健地求解平面任意简单闭广义多边形的弹性包络线，具有高效性和普遍适用性。
Abstract: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.
-
Key words:
- generic polygon /
- curved shape /
- convex hull /
- elastic envelop /
- supporting line
-
图 4 受力平衡与非平衡向量示意图
Figure 4. Vector diagram of force equilibrium and forcenon-equilibrium
表 1 广义多边形弹性包络线计算时间
Table 1. Calculation time of elastic envelope of generic polygon
点 数 量 全凸多边形
计算时间/ms内折多边形
计算时间/ms外凹多边形
计算时间/ms30 0.0785 0.1268 0.1690 60 0.1254 0.2592 0.3606 90 0.1765 0.4135 0.7560 120 0.2280 0.6298 1.2120 150 0.2834 0.9260 1.8050 180 0.3382 1.1942 2.6040 240 0.4540 1.8388 4.0760 
下载: 导出CSV
-
[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.072WANG 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. -
下载:
点击查看大图
计量
- 文章访问数: 284
- HTML全文浏览量: 30
- PDF下载量: 8
- 被引次数: 0
