| 基于二叉树的散乱点集快速凸包算法 |
| |
| 引用本文： | 刘广忠,黄琳娜.基于二叉树的散乱点集快速凸包算法[J].测绘科学,2008,33(4). |
| |
| 作者姓名： | 刘广忠 黄琳娜 |
| |
| 作者单位： | 河北工程技术高等专科学校计算机系,河北,沧州,061001;沧州师范专科学校计算中心,河北,沧州,061001 |
| |
| 摘 要： | 在右壳树和左壳树概念的基础上,提出了基于二叉树的散乱点集快速凸包算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速、动态地减小散点集的规模,通常情况下能达到线性时间复杂度。算法省却了凸包顶点间连接关系的判断过程,适用于任何复杂的散点分布情况,并且简单,易于实现。
|
| 关 键 词： | 计算机应用 散点集 凸包 二叉树 算法 |
Quick convex hull algorithm for scattered points based on binary tree |
| |
| LIU Guang-zhong,HUANG Lin-na.Quick convex hull algorithm for scattered points based on binary tree[J].Science of Surveying and Mapping,2008,33(4). |
| |
| Authors: | LIU Guang-zhong HUANG Lin-na |
| |
| Abstract: | On the basis of the concept of righttree and lefttree,a quick convex hull algorithm for scattered points based on a binary tree is put forward.It can dynamically reduce the scale of scattered point rapidly by removing a number of non-convex hull vertexes while finding each convex hull vertex.Normally,it can achieve linear time complexity.The algorithm obviates the judging process of the convex hull vertices' connected relation.It is applicable to any complex scattered points,and simple and easy to use. |
| |
| Keywords: | computer application discrete point set convex hull binary tree algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
