一种改进的实时凸壳算法

• 作者: 张显全 王继军 蒋联源 陈发住
• 来源期刊: 科技与创新
• 关键词: 凸壳 单调段 极值点 切点
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 软件时空
• 页码范围: 252-254
• 页数: 3页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1008-0570.2007.03.102

摘要

凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题.正切线算法需对新加入的实时点进行实时编号,本文实现了对新加入点的自动编号,且增加一个实时点最多只需对2个单调段进行计算,提高了运算效率,在最坏情况下时间复杂度为O(nlogm).