摘要
结合射线法和环绕计数法的优点,提出了有向穿越计数算法,该算法更加高效且容易实现,可作为安全管道判断的首选方法。对3种特定类型的安全管道进行了有针对性的优化,其中单调多边形管道的时间复杂度提升到了O(log n)级别;通过建立基于概率分布的简单外部或内部边界,在绝大多数情况下只需一次判断,优化了平均时间复杂度;通过改变顶点排列顺序,将有向穿越计数算法扩展到环形管道。
Taking the advantages of the ray method and winding number method, a new algorithm called directional crossing number is proposed. It is a preferred method for security channel judgment for its high efficiency and easy implementation. Optimizations can be made for three specific types of channel. When a polygon is known to be monotone, the computation can be improved in O( log n) time.By presetting a bounding box,only 1 test is needed for a large polygon in most cases,thus greatly improves the average time complexity. As for an annular channel, this algorithm works well simply by reverse the order of inner vertices.
作者
方兴
吴诗帆
FANG Xing;WU Shifan(91550 Troops,Dalian 116023,China)
出处
《海洋测绘》
CSCD
2019年第2期67-70,共4页
Hydrographic Surveying and Charting
关键词
计算机图形学
有向穿越计数
射线法
环绕计数法
安全管道
computer graphics
directional crossing number
ray method
winding number method
security channel
