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

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

作　　者：陈明[1] 张丰[1] 杜震洪[1] 刘仁义[1] 

机构地区：[1]浙江大学浙江省资源与环境信息系统重点实验室,地理信息科学研究所,杭州310007

出　　处：《上海交通大学学报》2014年第5期658-662,共5页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金(41101356;41171321);中央高校基本科研业务费专项基金(2011QNA3008);国家海洋公益专项基金(20090512-8)资助项目

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O18[自动化与计算机技术—计算机科学与技术]