-
题名改进的二维点集凸包快速求取方法
被引量:22
- 1
-
-
作者
余翔宇
孙洪
余志雄
-
机构
武汉大学电子信息学院
-
出处
《武汉理工大学学报》
CAS
CSCD
北大核心
2005年第10期81-83,92,共4页
-
基金
国家自然科学基金(40376051
60372057)
-
文摘
凸包问题是计算几何的基本问题,分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进,通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点,得到凸包的粗略逼近,接着在逼近结果上进行遍历,使用链表或栈这样的数据结构,找到逼近结果中连续2个顶点之间的漏检点,从而得到完整的凸包。整个过程达到复杂度下限,且在通常情况下接近线性时间。该方法已经有效地应用于基于控制点的图像配准中。
-
关键词
凸包
平面点集
计算几何
链表
栈
-
Keywords
convcx hull
planar poim set
computational geometry
linklist
stack
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-