摘要
针对目前众多采用了改进的快速凸包算法对给定的平面海量离散点集生成凸包的文献中,没有明确指出其初始凸包的形式(四边形或八边形)对算法效率的影响的问题,该文对凸包的生成过程进行了深入分析,并进行了大量的实验。通过比较这些实验的结果,发现以四边形或八边形作为初始凸包均能有效地提高算法效率,但在相同的条件下,以八边形作为初始凸包时,并不能将算法效率进一步提高,与以四边形作为初始凸包相比,其实际的执行效率不升反降。实验结果表明以四边形作为初始凸包时算法效率最佳。
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.
出处
《测绘科学》
CSCD
北大核心
2016年第7期23-27,共5页
Science of Surveying and Mapping
基金
国家自然科学基金项目(41161071)
