一个改进的简单多边形凸包算法  

An Improved Algorithm of Simple Polygon Convex Hull

作　　者：王丽青[1] 陈正阳[1] 陈树强[2] 陈学工[2] 

机构地区：[1]中南大学信息物理工程学院,长沙410083 [2]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2007年第3期200-201,共2页Computer Engineering

基　　金：国家"863"计划基金资助项目"地学空间信息三维智能分析与可视化技术"(2002AA135160)

摘　　要：凸包问题是计算几何的基本问题之一,在许多领域均有应用。该文通过给出反例,证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包,并分析了其缺点,提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题,且实现简单。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.

关 键 词：凸包 计算几何 多边形 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]