导航数据中多元交通规制三元化的方法

摘要

本发明提供在导航电子地图数据编译过程中，将多元交通规制转化为三元交通规制的方法。其包括以下步骤：1)调整源数据中规制信息的组织形式；2)根据规制信息探索可通行的路径；3)调整规制信息和可通行路径的表示方式；4)按照加权的方式找出可以代替原有规制信息的三元规制；5)找出与三元规制冲突的可通行路径，并通过增加虚LINK的方式保证新的三元规制不会影响原有的可通行路径。

主权项

一种导航数据中多元交通规制三元化的方法，其特征在于包括以下步骤：步骤一、获取导航电子地图中用于表示道路连通网络而虚拟出来的结点NODE和用于表示NODE与NODE之间通路的曲线型对象路段LINK；其中将结点数大于1的路口定义为复合路口，复合路口内的LINK为交叉点内LINK，与复合路口相连的LINK为外LINK，导航路线中走向结点NODE方向的LINK为进入LINK，从结点NODE方向走出的LINK为退出LINK；步骤二、根据步骤一得到的结点NODE、路段LINK和复合路口建立起导航线路的规制，由多条进入LINK、一个退出NODE和一条退出LINK组成的规制为多元规制，由一条进入LINK、一个退出NODE和一条退出LINK组成的规制为三元规制；步骤三、根据步骤二建立的导航路线规制建立通行序列表，调整源数据中规制信息的组织形式；所述步骤三包括以下步骤：S301）从源数据中取出进入LINK或者退出LINK不为外LINK的规制信息；S302）根据LINK的通行方向，探索以外LINK进入和外LINK退出，并且途径步骤S301中规制信息的所有规制序列;步骤四、根据规制信息探索可通行的路径；所述步骤四包括以下步骤：S401）分别找出所有可以进入复合路口和退出复合路口的外LINK；S402）在满足LINK的通行方向的前提下，找出所有从进入复合路口的LINK到退出复合路口的LINK中可以通行的路径序列；S403）将从步骤S402中找出的序列中与禁止规制冲突的序列删除;步骤五、调整规制信息和可通行路径的表示方式；步骤六、按照加权的方式找出可以代替原有规制信息的三元规制；所述步骤六包括以下步骤：S601）计算每个三元组分别在禁止通行序列和可通行序列中出现的次数，将某个三元组在禁止通行序列中出现的次数减去在可通行序列中出现的次数称为该三元组的度数；S602）取出度数最大的三元组，如果度数最大的三元组有多个，优先选择进入LINK和退出LINK都是交叉点内LINK的三元组，其次取进入LINK的ID最大的，最后取退出LINK的ID最大的；并将该三元组作为三元禁止规制放在目标规制集合M中；S603）判断集合M中的三元禁止规制是否与原有规制等价，如果等价，则步骤六处理完毕；否则，更新步骤S602中三元组的度数；S604）重复以上步骤直至规制集合M中的三元禁止规制与原有规制等价;步骤七、找出与三元规制冲突的可通行路径，并通过增加虚LINK的方式保证新的三元规制不会影响原有的可通行路径;所述步骤七包括以下步骤：S701）在可通行序列中找出与已经生成的三元禁止规制冲突的可通行序列N；S702）找出序列N中沿着通行序列方向的第一个复合路口结点N1和最后一个复合路口结点N2；S703）在该复合路口处增加虚LINK，N1和N2分别为该虚LINK的两个结点；S704）将序列N中除了第一条进入LINK和退出LINK之外的所有LINK的形点作为该虚LINK的形点；S705）将该虚LINK的属性定义为交叉点内LINK；S706）如果序列N中的所有LINK都是双向通行，则将该虚LINK的通行方向设置为双向通行；否则将该虚LINK的通行方向设置为沿着序列N的方向。