| 一个改进的简单多边形凸包算法 |
| |
| 引用本文： | 王丽青,陈正阳,陈树强,陈学工.一个改进的简单多边形凸包算法[J].计算机工程,2007,33(3):200-201. |
| |
| 作者姓名： | 王丽青 陈正阳 陈树强 陈学工 |
| |
| 作者单位： | 1. 中南大学信息物理工程学院,长沙,410083
2. 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划) |
| |
| 摘 要： | 凸包问题是计算几何的基本问题之一，在许多领域均有应用。该文通过给出反例，证明文献4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包，并分析了其缺点，提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题，且实现简单。
|
| 关 键 词： | 凸包 计算几何 多边形 |
| 文章编号： | 1000-3428（2007）03-0200-02 |
| 修稿时间： | 2006-02-21 |
An Improved Algorithm of Simple Polygon Convex Hull |
| |
| WANG Liqing,CHEN Zhengyang,CHEN Shuqiang,CHEN Xuegong.An Improved Algorithm of Simple Polygon Convex Hull[J].Computer Engineering,2007,33(3):200-201. |
| |
| Authors: | WANG Liqing CHEN Zhengyang CHEN Shuqiang CHEN Xuegong |
| |
| Affiliation: | ??1. School of Info-physics and Geomatics Engineering, Central South University, Changsha 410083; 2. School of Information Science & Engineering, Central South University, Changsha 410083) |
| |
| Abstract: | Convex hull problem is one of the fundamental problems in computational geometry,and is used in many fields.Reference4] presents an algorithm for finding the convex hull of a simple polygon using active double line test.By presenting counter-examples,it proves that the algorithm could not adapt to all cases,and analyzes its shortcoming,proposes an improved algorithm.The improved algorithm completely solves self-intersection which linear algorithms do not solve,and the realization is simple. |
| |
| Keywords: | Convex hull Computational geometry Polygons |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
|
