摘要
最小凸包问题是计算几何中得到广泛研究的问题之一,在建筑体建模和地理信息系统(GIS)构建中有着广泛的应用.在探讨现有普通算法的基础上,提出了全新的环扩张算法来求点集凸包,然后对此算法与普通算法进行算法复杂度分析和实验比较,并进行曲线拟合分析,验证了理论与实践的统一,从而证明环扩张算法的有效性和高效性.
The minimum convex hull is one of the widely studied problems in science of computing geometry, as well as extensively applied in many field of architectural modeling and GIS(Geographic Information System). One of the common algorithm for computing spatial convex hull has been discussed. In order to increase operation speed, a new method is put forward based on loop, then the algorithm complexity analysis and experimental comparison will be done, on which do the curve fitting to proof the unity of theory and practice and the high efficiency of the algorithm.
出处
《东华大学学报(自然科学版)》
CAS
CSCD
北大核心
2008年第3期311-314,共4页
Journal of Donghua University(Natural Science)
关键词
点集
凸包
环
算法
point set
convex hull
loop
algorithm