学术探索
学术期刊
新闻热点
数据分析
智能评审

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

被引：43
作者：
金文华
何涛
刘晓平
唐卫清
唐荣锡
机构：
[1] 中国科学院计算技术研究所
[2] 北京航空航天大学制造工程系!北京
[3] 不详
[4] 合肥工业大学计算机学院!合肥
来源：
计算机学报 | 1998年 / 06期
关键词：
凸包; 平面点集; 简单多边形; 有序简单多边形; 计算几何;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
凸包问题是计算几何的基本问题之一，在许多领域均有应用．传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干．本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法．该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包．本文算法不仅达到了O（nlogn）的理论时间复杂度下限，而且算法极其简单，易于实现．本文方法已应用于工厂设计软件PDSOFT中，实践证明效果很好．
引用
收藏
页码：533 / 539
页数：7
相关论文
共 7 条
1