A Fast Convex Hull Algorithm for Ring-Distributed Planar Point Sets

Abstract

Abstract:

Aimed at the problem that the gridaided algorithm does not perform well in constructing convex hull of a ring-distributed point set, a gridreprocessing algorithm was proposed. By comparing the spatial relationship between related cells, the proposed algorithm eliminated most of the points never proved to be vertices of the convex hull twice. As a result, the number of points to be Grahamscanned was greatly reduced and the computational efficiency improved. The experimental results show that the grid-reprocessing algorithm significantly improves the efficiency of handling ring-distributed point sets and is more efficient, to a certain extent, than the grid-aided algorithm when dealing with evenly distributed point sets.

Key words: marine environment, feature extraction, ringdistribution, convex hull, grid

CLC Number:

CHEN Ming,ZHANG Feng,DU Zhenhong,LIU Renyi. A Fast Convex Hull Algorithm for Ring-Distributed Planar Point Sets[J]. Journal of Shanghai Jiaotong University, 2014, 48(05): 658-662.

References

［1］O’Rourke J. Computational geometry in C ［M］. 2nd ed. UK: Cambridge University Press, 1998.

［2］Igarashi Y, Suzuki H. Cover geometry design using multiple convex hulls ［J］. ComputerAided Design, 2011, 43(9): 11541162.

［3］Kodell R L, Zhang C, Siegel E R, et al. Selective voting in convexhull ensembles improves classification accuracy ［J］. Artificial Intelligence in Medicine, 2012, 54(3): 171179.

［4］Choi H B, Ryu J. Convex hullbased velocity transmission capability of parallel manipulators ［J］. International Journal of Advanced Manufacturing Technology, 2013, 65(58): 695704.

［5］Thomas H C, Charles E L, Ronald L R, et al. Introduction to algorithms, second edition ［M］. USA: MIT Press and McGrawHill, 2001: 955956.

［6］Graham R L. An efficient algorithm for determining the convex hull of a finite point set ［J］. Information Process Letter, 1972, 1(1): 132133.

［7］Preparata P F, Hong J S. Convex hulls of finite sets of points in two and three dimensions ［J］. Communications of the ACM, 1977, 20(2): 8793.

［8］刘斌，王涛. 一种高效的平面点集凸包递归算法［J］. 自动化学报, 2012, 38(8): 13751379.

LIU Bin, WANG Tao. An efficient convex hull algorithm for planar point set based on recursive method ［J］. Acta Automatica Sinica, 2012, 38(8): 13751379.

［9］Liu G H, Chen C B. A new algorithm for computing the convex hull of a planar point set ［J］. Journal of Zhejiang University Science A, 2007, 8(8): 12101217.

［10］周培德. 计算几何——算法设计与分析［M］. 4版. 北京：清华大学出版社, 2011: 8285.

［11］Liu R, Fang B, Tang Y Y, et al. A fast convex hull algorithm with maximum inscribed circle affine transformation ［J］. Neurocomputing, 2012, 77(1): 212221.

［12］An P T. Method of orienting curves for determining the convex hull of a finite set of points in the plane ［J］. Optimization, 2010, 59(2): 175179.

［13］王结臣, 陈焱明. 一种栅格辅助的平面点集最小凸包生成算法［J］. 武汉大学学报：信息科学版, 2010, 35(4)：403406.

WANG Jiechen, CHEN Yanming. A gridaided algorithm for determining the minimum convex hull of a planar point set ［J］. Geomatics and Information Science of Wuhan University, 2010, 35(4): 403406.

[1]	CHEN Xiaowen, HAN Yudong, DING Xiaoping, HOU Dongwei. Multiscale Calculation of Elastic Modulus of Cement Paste Based on Grid Nanoindentation Technology [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1199-1207.
[2]	ZHU Chenghao, WANG Han, SUN Guoqi, WEI Xiaobin, WANG Fuwen, CAI Xu. An Identification Method for DC-Link Capacitor Capacitance of Grid Connected Inverter [J]. Journal of Shanghai Jiao Tong University, 2022, 56(6): 693-700.
[3]	YU Hao, ZHANG Zhemeng, PENG Sui, ZHANG Zhiqiang, REN Wanxin, LI Canbing. Comparative Analysis of Technical Standards for Offshore Wind Power via VSC-HVDC [J]. Journal of Shanghai Jiao Tong University, 2022, 56(4): 403-412.
[4]	GAO Changhao, SONG Wenping, HAN Shaoqiang, LU Kuan, WANG Yue, YE Kun. Research on Poststall Re-orientation Technology of Air-to-Air Missile [J]. Air & Space Defense, 2022, 5(3): 17-26.
[5]	HUANG Jiayang (黄嘉阳), YANG Pengfei* (杨鹏飞), WAN Bo (万波), ZHANG Zhiqiang (张志强). KDLPCCA-Based Projection for Feature Extraction in SSVEP-Based Brain-Computer Interfaces [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(2): 168-175.
[6]	ZHANG Yanhe, ZANG Yuejin, CHEN Bo, XU Mingsheng. Radar HRRP Target Recognition Algorithm Based on Variational Auto-encoder with Disentangled Representation [J]. Air & Space Defense, 2022, 5(2): 87-93.
[7]	LU Qiuyu, YU Zhen, YANG Yinguo, LI Li. Two-Stage Optimal Schedule of Offshore Wind-Power-Integrated Multi-Microgrid Considering Uncertain Power of Sources and Loads [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1308-1316.
[8]	WANG Zheng (王正), XU Hui (许辉), L v Na (吕娜), TAO Wei∗ (陶卫), CHEN Guodong (陈国栋), CHI Wenzheng (迟文正), SUN Lining (孙立宁). Dynamic Obstacle Avoidance for Application of Human-Robot Cooperative Dispensing Medicines [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(1): 24-35.
[9]	XU Ling, WANG Xingzhi, XIAO Linpeng. Power Grid Dispatching Event Detection Technology Based on Semantic Feature Capture [J]. Journal of Shanghai Jiao Tong University, 2021, 55(S2): 86-91.
[10]	QU Gang, XIAO Linpeng, ZHANG Liang. Construction of a Regulation Ontology Label System for Intelligent Search of Power Grid Regulation Micro Scene [J]. Journal of Shanghai Jiao Tong University, 2021, 55(S2): 92-97.
[11]	XIAO Ran, WEI Ziqing, ZHAI Xiaoqiang. Hourly Energy Consumption Forecasting for Office Buildings Based on Support Vector Machine [J]. Journal of Shanghai Jiao Tong University, 2021, 55(3): 331-336.
[12]	XIN Jianjian, FANG Tian, SHI Fulong. Numerical Studies on Violent Sloshing and Resonance Frequencies in a Three-Dimensional Prismatic Tank [J]. Journal of Shanghai Jiao Tong University, 2021, 55(2): 161-169.
[13]	ZHU Song, QIAN Xiaochao, LU Yingbo, LIU Fei. An XGBoost-Based Effectiveness Prediction Method of Equipment System-of-Systems [J]. Air & Space Defense, 2021, 4(2): 1-.
[14]	HU Hong, CHEN Xinyi, WANG Lifeng, TENG Xiaobi, YAN Zheng, XU Xiaoyuan, WANG Han. Construction Method of an Operating Reserve System for East China Power Grid Oriented to New Power Systems [J]. Journal of Shanghai Jiao Tong University, 2021, 55(12): 1640-1649.
[15]	WANG Wei, WANG Bing, HU Xiong, SUN Dejian. Online Degradation Assessment of Shore Bridge Hoisting Gearbox Based on Improved Symbolic Sequence Entropy and Logistic Regression Model [J]. Journal of Shanghai Jiao Tong University, 2021, 55(10): 1272-1280.