基于改进三角剖分算法的导航网格构建  

Construction of Navigation Mesh Based on Improved Triangulation Algorithm

作　　者：赫鑫 任鸿翔[1] HE Xin;RENG Hong-xiang(Navigation College,Dalian Maritime University,Dalian Liaoning 116026,China)

机构地区：[1]大连海事大学航海学院

出　　处：《计算机仿真》2019年第10期373-377,共5页Computer Simulation

基　　金：国家高技术研究发展计划(863)资助项目(2015AA010504);交通运输部应用基础研究资助项目(2015329225204);省自然科学基金指导计划(20170540092)

摘　　要：针对航海仿真系统中栅格地图适应性较差、效率较低的问题,引入基于德洛内三角网的导航网格作为寻路网格,提出了一种改进三角剖分算法.算法将各层甲板、舱室内的关键点连成多边形;采用逐点插入法构建三角网;改进了回溯循环算法,构建基于多边形边约束的三角网;基于边指向的域外三角形判定法则对三角网进行修正,最终构建出基于德洛内三角网的导航网格.实验结果表明,经改进的算法,构建的导航网格数量较少,计算机运行效率较高.This paper proposes an improved triangulation algorithm and introduced the navigation mesh based on Delaunay triangulation into the Navigation Simulation System to solve the problems, such as the poor adaptability in navigation simulation system and the large influence of granularity and low efficiency of the grid map. This algorithm collected key points of decks and cabins and built polygons, and used point by point insertion method to build Delaunay TIN and improved backtracking loop algorithm to build Delaunay TIN constrained by edges of polygons, and modified the Delaunay TIN based on the judgment rule of external domain triangles. The experimental results show that the navigation mesh built in this paper has less quantity and higher efficiency of computer operation.

关 键 词：航海仿真系统 寻路网格 德洛内三角网 导航网格 三角剖分 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]