初始凸包对改进快速凸包算法效率的影响  

Influence of initial convex hull on the efficiency of Quickhull algorithm

作　　者：陈明晶[1] 方源敏[1] 陈杰[1] 

机构地区：[1]昆明理工大学国土资源工程学院,昆明650093

出　　处：《测绘科学》2016年第7期23-27,共5页Science of Surveying and Mapping

基　　金：国家自然科学基金项目(41161071)

摘　　要：针对目前众多采用了改进的快速凸包算法对给定的平面海量离散点集生成凸包的文献中,没有明确指出其初始凸包的形式(四边形或八边形)对算法效率的影响的问题,该文对凸包的生成过程进行了深入分析,并进行了大量的实验。通过比较这些实验的结果,发现以四边形或八边形作为初始凸包均能有效地提高算法效率,但在相同的条件下,以八边形作为初始凸包时,并不能将算法效率进一步提高,与以四边形作为初始凸包相比,其实际的执行效率不升反降。实验结果表明以四边形作为初始凸包时算法效率最佳。In terms of the issues that some papers use the improved Quickhull algorithm to generate the convex hull for a given mass plane discrete point set without pointing out the influence of initial convex hull form （quadrilateral or octagon） on the algorithm efficiency, the generation process of convex hull was analyzed in this paper. Experimental results showed that using quadrilateral or octagon as the initial convex hull could both effectively improve the efficiency of the algorithm; however, under the same condition, the efficiency of algorithm using octagon as the initial convex hull was lower than that using quadrilateral; the algorithm had the best efficiency when using quadrilateral as the initial convex hull.

关 键 词：快速凸包算法 初始凸包 离散点 地理信息系统 

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