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

• 作者: 何涛 刘晓平 唐卫清 唐荣锡 金文华
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 凸包 平面点集 简单多边形 有序简单多边形 计算几何
• 年，卷（期）: 1998,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 533-539
• 页数: 7页
• 分类号: TP301
• 字数: 4207字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.1998.06.008

摘要

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