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

方兴  吴诗帆 《海洋测绘》2019,39(2):67-70

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