简单快速的平面散乱点集凸包算法

摘要：

凸包问题是计算几何的基本问题之一,在许多领域均有应用.传统点集凸包算法和简单多边形凸包算法平行发展,互不相干.文中将简单多边形凸包算法应用于散乱点集凸包问题中,提出了新的点集凸包算法.新算法不仅达到了O(nlogn) 的理论时间复杂度下限,而且极其简单,易于实现.该算法已应用于工厂设计软件PDSOFT中,实践证明效果很好.

关键词：凸包、多边形、算法、管道、平面点集、平剖图

分类号：TP301.6;TP391.72(计算技术、计算机技术)

资助基金：国家自然科学基金69673001

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页码：72-75