| 一种简单多边形凸包的新线性算法 |
| |
| 引用本文： | 刘润涛.一种简单多边形凸包的新线性算法[J].工程图学学报,2002,23(2):120-126. |
| |
| 作者姓名： | 刘润涛 |
| |
| 作者单位： | 哈尔滨理工大学信息与科学计算技术研究所,哈尔滨,150080 |
| |
| 基金项目： | 国家自然科学基金资助项目(10171025) |
| |
| 摘 要： | 给出了一个计算简单多边形凸包的新算法，其搜索策略为：对简单多边 形上的点进行分类，排除不可能为凸包上的点，缩小搜索范围，从而降低算法的时间复杂度，该算法具有线性时间复杂度和空间复杂度，同时，具体量化了该算法的复杂度，给出了该算法的时间复杂度和空间复杂度的确定的上界，即，时间复杂度为不超过4(n-4）次乘法，6（n-4）次减法和17n-12次比较运算，空间复杂度为不超过2n个存储单元（n是该简单多边形顶点的个数）。
|
| 关 键 词： | 线性算法 简单多边形 凸包 计算几何 时间复杂度 空间复杂度 |
| 文章编号： | 1003-0158(2002)02-0120-07 |
| 修稿时间： | 2001年7月4日 |
A New Linear Algorithm for Computing the Convex Hull of Simple Polygon |
| |
| LIU Run-tao.A New Linear Algorithm for Computing the Convex Hull of Simple Polygon[J].Journal of Engineering Graphics,2002,23(2):120-126. |
| |
| Authors: | LIU Run-tao |
| |
| Abstract: | |
| |
| Keywords: | simple polygon convex hull algorithm time complexity space complexity upper bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
