Abstract:
Convex hull problem is one of the fundamental problems in computational geometry, and is used in many fields. Reference[4] 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.
Key words:
Convex hull,
Computational geometry,
Polygons
摘要: 凸包问题是计算几何的基本问题之一,在许多领域均有应用。该文通过给出反例,证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包,并分析了其缺点,提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题,且实现简单。
关键词:
凸包,
计算几何,
多边形
WANG Liqing; CHEN Zhengyang; CHEN Shuqiang; CHEN Xuegong. An Improved Algorithm of Simple Polygon Convex Hull[J]. Computer Engineering, 2007, 33(03): 200-201.
王丽青;陈正阳;陈树强;陈学工. 一个改进的简单多边形凸包算法[J]. 计算机工程, 2007, 33(03): 200-201.