利用初始包容壳求二维点集凸壳的自适应算法
二维点集凸壳应用广泛,算法较多,但实现较为复杂.虽然"利用正负划分性求平面点集凸包的最优算法"[1] 计算准确,计算过程中只用到加、减、乘和比较运算,时间复杂性低,但存在极值点分布情况不全面及分情况处理的局限.为弥补这些不足,首先从分析凸壳的3～8个基本极值点出发,将补全后的分布情况融入初始包容壳中;然后详细给出一种经过完善的追踪凸壳的新算法.该算法继承了文献[1]算法的优点,不仅考虑全面,而且化繁于简,并可应用于三维点集.该算法是一种自适应算法.
作 者： 张咏 刘长星 董汉军 ZHANG Yong LIU Chang-xing DONG Han-jun 作者单位： 西安科技大学测绘科学与技术学院,西安,710054 刊 名： 测绘科学 ISTIC PKU 英文刊名： SCIENCE OF SURVEYING AND MAPPING 年，卷(期)： 2009 34(6) 分类号： P208 TP391 关键词： 二维点集 凸壳 极值点 初始包容壳 郝氏距离[1] 2D point set convex hull extreme points initial inclusion hull Haosh distance formula