坐标排序的离散点凸包生成算法  

Algorithm of convex hull generation for point sets based on sorted coordinates

作　　者：李必栋 闫浩文[1] 王中辉[1] 刘虎林[1] 

机构地区：[1]兰州交通大学测绘与地理信息学院/甘肃省地理国情监测工程实验室,兰州730070

出　　处：《测绘科学》2017年第2期14-17,共4页Science of Surveying and Mapping

基　　金：国家科技支撑计划项目(2013BAB05B01);国家自然科学基金项目(41371435;41561090)

摘　　要：针对传统的凸包生成方法在数据量较大情况下效率下降明显的问题,该文提出了一种基于平面离散点快速生成凸包算法。基于凸包边界单调性对平面点集分区域按X轴方向排序的方法,较好地减少了传统凸包生成算法的计算量,实现了凸包求取的高效性。实验结果表明:该算法不仅可以快速有效地生成凸包,还能够保证结果的准确性,且效率较高。Aiming at the problem that the efficiency of traditional methods reduces significantly in the condition of large amount of data, a new quick hull-building algorithm based on the planar scattered point set was proposed in this paper. This method used the monotonicity of convex hull＇s border to sort plane point set by X-axis, reduced the computation load of traditional convex hull generation algorithm, and ac celerated the efficiency of convex hull. The experiment results showed that the referred algorithm could generate convex hull quickly, accurately and efficiently.

关 键 词：凸包 排序 单调 Graham算法 

分 类 号：P282[天文地球—地图制图学与地理信息工程]