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]	ZHANG Yu, ZHANG Chen, LIU Hui, YU Siqi, WU Linlin, CAI Xu. Mechanism of Power Transfer Limit Under Multiple Electrical Constraints for Grid-Connected New Energy Units and Full-Power Operation Conditions in Weak Grids [J]. Journal of Shanghai Jiao Tong University, 2026, 60(1): 19-31.
[2]	ZHU Feng, SHAN Chao, WU Ning, CAI Qixin, ZHU Yunan, LIU Yunpeng, ZUO Qiang. Feature Extraction and Anomaly Identification Method for Power Customer Price in Power Market Enviroment [J]. Journal of Shanghai Jiao Tong University, 2025, 59(7): 995-1006.
[3]	LI Xiang, CHEN Siyuan, ZHANG Jun, KE Deping, GAO Jiemai, YANG Huanhuan. Physics-Informed Fast Transient Stability Assessment of Non-Fixed Length in Power Systems [J]. Journal of Shanghai Jiao Tong University, 2025, 59(7): 962-970.
[4]	ZHOU Xia, CHEN Wenjian, DAI Jianfeng, XIE Xiangpeng. Black-Start Coordinated Control Strategy of Optical Storage Microgrid Considering State of Charge Balance of Distributed Energy Storage [J]. Journal of Shanghai Jiao Tong University, 2025, 59(7): 938-951.
[5]	REN Xiancheng, LI Shangzhi, LI Yingbiao, HU Jiabing, XU Taishan, BAO Yanhong, WU Feng. Transient Modeling and Characteristic Comparative Analysis of Grid-Forming VSC with and Without Current Control [J]. Journal of Shanghai Jiao Tong University, 2025, 59(7): 971-982.
[6]	WANG Yuyang, ZHANG Chen, ZHANG Yu, WANG Yiming, XU Po, CAI Xu. Reactive Power-Voltage Droop Gain Online Tuning Method of Photovoltaic Inverters for Improvement of Stable Output Power Capability in Weak Grids [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 845-856.
[7]	CHEN Shi, YANG Linsen, LIU Yihong, LUO Huan, ZANG Tianlei, ZHOU Buxiang. Optimal Scheduling Strategy of Newly-Built Microgrid in Small Sample Data-Driven Mode [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 732-745.
[8]	ZHANG Li, WANG Bao, JIA Jianxiong, SONG Zhumeng, YE Yutong, YU Yue, LIN Jiaqing, XU Xiaoyuan. End-to-End Collaborative Optimization Method for Microgrid Power Prediction and Optimal Scheduling [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 720-731.
[9]	SHAO Yanli, YING Yong, CHEN Xi, DONG Siyu, WEI Dan. Multi-Scene Smoke Detection Based on Multi-Feature Extraction Method [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 866-879.
[10]	QUAN Shaoli, YU Haozheng, MA Jie, WANG Weiyu, GUO Yong, CHEN Chun. Distributed Cooperative Disturbance-Rejection Control of Hybrid Alternating Current/Direct Current Distribution Grids with Multiple Inverters [J]. Journal of Shanghai Jiao Tong University, 2025, 59(5): 605-616.
[11]	ZHAO Yingying, QIU Yue, ZHU Tianchen, LI Fan, SU Yun, TAI Zhenying, SUN Qingyun, FAN Hang. Online Steady-State Scheduling of New Power Systems Based on Hierarchical Reinforcement Learning [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 400-412.
[12]	WEI Maohua, YANG Ling, WENG Liangtao, YANG Jipei, CHEN Yongqiao. SOC Balancing Strategy for Distributed Energy Storage Units in Isolated DC Microgrids Considering Capacity Differences [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 376-387.
[13]	YANG Jipei, YANG Ling, WEI Maohua. DC-Bus Voltage Oscillation Suppressor Based on Active Capacitor and Its Control Method [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 303-312.
[14]	SI Wenjia, CHEN Junru, ZHANG Chenglin, LIU Muyang. Influence of DC-Bus Voltage on Synchronization Stability of Grid-Following Converters [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 313-322.
[15]	ZHAO Yongxi, GAO Pengchao, FAN Hong. Power Coordination Strategy for Hybrid Energy Storage in AC/DC Microgrids Based on Virtual Impedance-Fuzzy Algorithm [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 388-399.