嵌入式GIS导航路径二维流型分层寻优方法

摘要

一种嵌入式GIS导航路径二维流型分层寻优方法，包括以下步骤：1)、建立三级收敛域网格模型：设定网格中的某个结点，同该结点具备拓扑连接关系的当前网格以及包围当前网格一圈的外围网格中的所有结点区域定义为路段一级收敛区域；同该结点具备拓扑连接关系的包围当前网格外围第二圈网格中的所有结点区域定义为路段二级收敛区域；其余网格中具备通当前结点连接关系的结点区域定义为路段三级收敛区域；2)使用所述三级收敛域网格模型，采用基于二维流型的空间拓扑数据检索算法进行最优路径搜索，得到分层寻优的最优路径。本发明能有效解决导航路径数据海量时的分批读入寻优问题、有利于海量路网的最优路径查找、快速性和准确性良好。

主权项

一种嵌入式GIS导航路径二维流型分层寻优方法，其特征在于：所述方法包括以下步骤：1)、建立三级收敛域网格模型：设定网格中的某个结点，同该结点具备拓扑连接关系的当前网格以及包围当前网格一圈的外围网格中的所有结点区域定义为路段一级收敛区域；同该结点具备拓扑连接关系的包围当前网格外围第二圈网格中的所有结点区域定义为路段二级收敛区域；其余网格中具备同该结点连接关系的结点区域定义为路段三级收敛区域；在针对该结点的各个收敛域中连接的路段信息中增加了组成路段的另外一个结点所在网格同该结点所在网格的方向参数；对于每一级收敛域的路段数据进行存储如下表1：序号字段名称字段类型字段描述1Pidint记录号2Idint可达结点id3Idaddint可达结点信息基表地址4Daddint路段属性记录地址5angint可达结点方向参数表1收敛域路段表；2)使用所述三级收敛域网格模型对最优路径的空间拓扑数据进行检索，具体过程如下：(2.1)假设需要搜索从S到D的最优路径，单层上使用区域限制的流型算法：首先根据起始点的输入坐标值计算当前坐标点所属的网格编号，通过二级索引检索到当前网格中的所有结点，把当前坐标值与网格中的所有坐标值比较，求取离当前坐标结点最近的坐标点，作为起始搜索结点n1；同理找到终点坐标点所在网格中与之最近的坐标结点，作为终点的搜索结点n3；(2.2)做n1和n3的连线，确定最优路径的方向系数，连线交收敛域边界为p点，使用步骤(2.1)中的方法，求取p点所在网格中与p点最近的路网结点，定义为中间过渡结点n2；(2.3)搜索n1点所在网格的一级收敛域网格，使用索引存储表读取收敛域中的所有结点，再根据收敛域路段表，读取收敛域中的所有结点的拓扑信息，使用邻接多重表数据结构算法，把所有结点连接起来，在内存中组成一张路网拓扑链表，该链表的拓扑数据只限于当前网格所在的收敛域；(2.4)依照上述确定的收敛域中的起点、终点以及收敛域中的路网拓扑链表，使用最优路径搜索算法求出从起点n1到中间过渡点n2的最优路径；(2.5)把n2作为搜索的起点重复步骤(2.2)、(2.3)、(2.4)，直到中间过渡点所在的网格与终点共属于同一级收敛域内，进行最后一次搜索，得到分层寻优的最优路径。