摘要
二维点集凸壳应用广泛，算法较多，但实现较为复杂。虽然“利用正负划分性求平面点集凸包的最优算法”^[1]计算准确，计算过程中只用到加、减、乘和比较运算，时间复杂性低，但存在极值点分布情况不全面及分情况处理的局限。为弥补这些不足，首先从分析凸壳的3—8个基本极值点出发，将补全后的分布情况融入初始包容壳中；然后详细给出一种经过完善的追踪凸壳的新算法。该算法继承了文献[1]算法的优点，不仅考虑全面，而且化繁于简，并可应用于三维点集。该算法是一种自适应算法。
The convex hull of 2D point set is applied widespreadly with abundant algorithms but complex implementation. The algorithm, ＂optimum algorithm for constructing convex hull of planar point set utilizing plus or minus characteristic of demarcation＂, is accurate and low complex only with operation of addition, subtraction, multiplication and comparision. But it has limitation of uncomprehensive distribution of extreme point. To make up for the shortage, an improved algorithm was proposed based on analyzing the 3 to 8 fundamental extreme points of convex hull and merging complementary distribution into initial inclusion hull. This comprehensive and simple auto-adapted algorithm can be used for 3D point set.
出处
《测绘科学》
CSCD
北大核心
2009年第6期171-174,共4页
Science of Surveying and Mapping
关键词
二维点集
凸壳
极值点
初始包容壳
郝氏距离^[1]
2D point set
convex hull
extreme points
initial inclusion hull
Haosh distance formula
