安全管道判断算法及其优化

• 作者: 吴诗帆 方兴
• 来源期刊: 海洋测绘
• 学科: 地球科学
• 关键词: 计算机图形学 有向穿越计数 射线法 环绕计数法 安全管道
• 年，卷（期）: 2019,（2）
• 所属期刊栏目: 工程实践
• 页码范围: 67-70
• 页数: 4页
• 分类号: P229
• 字数: 2994字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-3044.2019.02.015

摘要

结合射线法和环绕计数法的优点,提出了有向穿越计数算法,该算法更加高效且容易实现,可作为安全管道判断的首选方法.对3种特定类型的安全管道进行了有针对性的优化,其中单调多边形管道的时间复杂度提升到了O(log n)级别;通过建立基于概率分布的简单外部或内部边界,在绝大多数情况下只需一次判断,优化了平均时间复杂度;通过改变顶点排列顺序,将有向穿越计数算法扩展到环形管道.