简单多边形可见点问题的快速求解算法

• 作者: 何涛 刘慎权 唐卫清 唐荣锡 金文华
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 简单多边形 顶点可见性 可见多边形 计算几何
• 年，卷（期）: 1999,（3）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 275-282
• 页数: 8页
• 分类号: TP391
• 字数: 4394字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.1999.03.008

摘要

简单多边形可见点问题是计算几何的基本问题之一,在许多领域均有应用.本文在参考现有算法(尤其是Lee算法)的基础上,提出了改进的方法.文中方法先用射线法求取第一个可见点,然后利用文中设定的规则搜索后续可见点.本文算法继承和发展了Lee算法的几何直观性,且也只采用一个堆栈,但无须耗时的坐标变换和三角函数运算,而且彻底修改了Lee算法的错误,避免了Lee算法中的不足之处,并且算法的时间和空间复杂度仍为O(n).本文算法已应用于工厂设计配管软件PDSOFT for Piping中,实践证明效果很好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐荣锡	北京航空航天大学制造工程系	36	760	15.0	27.0