文献类型：期刊文章

作　　者：金文华[1] 何涛[2] 刘晓平[3] 唐卫清[3] 唐荣锡[3]

机构地区：[1]中国科学院计算技术研究所 [2]北京航空航天大学制造工程系,北京100083 [3]合肥工业大学计算机学院,合肥230009

出　　处：《计算机学报》

年　　份：1998

卷　　号：21

期　　号：6

起止页码：533-539

语　　种：中文

收录情况：BDHX、BDHX1996、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：凸包问题是计算几何的基本问题之一，在许多领域均有应用．传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干．本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法．该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包．本文算法不仅达到了O（nlogn）的理论时间复杂度下限，而且算法极其简单，易于实现．本文方法已应用于工厂设计软件PDSOFT中，实践证明效果很好．

关 键 词：凸包 平面点集 简单多边形 算法  计算几何  

分 类 号：O24]