基于有序简单多边形的平面点集凸包快速求取算法

摘要：

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

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

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

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

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

页数：共7页

页码：533-539