环状分布平面点集的凸包快速生成算法

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (05): 658-662.

• 自动化技术、计算机技术 • 上一篇下一篇

环状分布平面点集的凸包快速生成算法

陈明，张丰，杜震洪，刘仁义

（浙江大学浙江省资源与环境信息系统重点实验室，地理信息科学研究所，杭州 310007）

收稿日期:2013-05-31
基金资助:
国家自然科学基金（41101356, 41171321）,中央高校基本科研业务费专项基金（2011QNA3008）,国家海洋公益专项基金（200905128）资助项目

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

CHEN Ming,ZHANG Feng,DU Zhenhong,LIU Renyi

（Zhejiang Provincial Key Laboratory of GIS, Institute of Geographic Information Science,Zhejiang University, Hangzhou 310007, China）

Received:2013-05-31

摘要/Abstract

摘要：

针对栅格辅助法在处理环状分布平面点集时计算效率较低的问题，提出了一种格网2次处理算法.通过比较离散点所在网格的空间位置关系，经2次剔除点集中绝大部分不可能成为凸包顶点的内点，减少了参与Graham扫描的点数，提高了计算效率.实验结果表明，与栅格辅助法相比，格网2次处理算法能够明显提高处理环状分布平面点集的效率，而且对于其他空间分布较为均匀的平面点集的处理效率也有一定程度的提高.

关键词: 海洋环境, 地物提取, 环状分布, 凸包, 格网

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

中图分类号:

陈明，张丰，杜震洪，刘仁义. 环状分布平面点集的凸包快速生成算法[J]. 上海交通大学学报（自然版）, 2014, 48(05): 658-662.

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.

参考文献

［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.