改进的二维点集凸包快速求取方法

被引：54

作者：

余翔宇

孙洪

余志雄

机构：

[1] 武汉大学电子信息学院,武汉大学电子信息学院,武汉大学电子信息学院武汉,武汉,武汉

来源：

武汉理工大学学报 | 2005年 / 10期

关键词：

凸包; 平面点集; 计算几何; 链表; 栈;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

凸包问题是计算几何的基本问题,分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进,通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点,得到凸包的粗略逼近,接着在逼近结果上进行遍历,使用链表或栈这样的数据结构,找到逼近结果中连续2个顶点之间的漏检点,从而得到完整的凸包。整个过程达到复杂度下限,且在通常情况下接近线性时间。该方法已经有效地应用于基于控制点的图像配准中。

引用

页数：4