A new method of minimum convex hull in computer applications
A new method of minimum convex hull in computer applications
复制标题
一种新的最小凸包计算方法在计算机中的应用
DOI：
10.1504/ijcat.2014.066728
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
阮见
中科院分区：
文献类型：
--
作者：
刘波;阮见
最小凸船体问题是计算几何中研究最多的问题之一，在地理信息系统等领域有着广泛的应用。通过分析传统最小凸船体串行算法的不足，提出了一种新的最小凸船体算法。在最小凸船体中引入了“绝对顶点”、“绝对错误顶点”和“可能顶点”3个新的概念，提高了算法的计算效率，增加了最小凸船体在大量空间数据中的适用性。最后，通过对比分析，与传统的串行算法相比，本文算法在大数据量空间数据中寻找最小凸船体顶点方面具有明显的优势，该算法的执行效率高于传统的最小凸船体串行算法，并且提高了最小凸船体的适用性。
The minimum convex hull is one of the widely studied problems in computational geometry, as well as widely applied in many fields such as in GIS. This paper, through analysis of the disadvantage of the traditional minimum convex hull serial algorithm, puts forward a new method of the minimum convex hull. It introduces three new concepts such as 'absolute vertex', 'absolutely wrong vertex' and 'possible vertex' in minimum convex hull, which can improve the algorithm computing efficiency, and increase the applicability of minimum convex hull in large number of spatial data. In the end, through comparative analysis, compared to the traditional serial algorithm, this paper's algorithm has obvious advantages on seeking minimum convex hull vertex in large number of spatial data, this algorithm execution efficiency is higher than the traditional serial algorithm for minimum convex hull, and it also can improved the applicability of minimum convex hull.