专利名称：地图及更新指示信息数据结构、地图信息处理及提供装置的制作方法
技术领域：
本发明涉及车用导航装置、便携电话、便携信息终端等移动体或固定的计算机终端中使用的地图信息的数据结构、更新指示信息的数据结构、地图信息处理装置及地图信息提供装置。
现有技术在车用导航装置中，进行从出发地至目的地的路径计算(路径探索)，并使作为其结果获得的最佳路径候选与道路地图一同在显示装置的画面上显示出来。这种类似的功能也可在便携电话、便携信息终端等其它移动体或固定的计算机终端中被实行。
作为用于进行这种路径探索的装置的地图信息的数据结构，有的数据结构为提高处理速度而具有道路地图显示用的数据集合及路径计算用的数据集合。比如，专利文献1中展示了这种数据结构的示例。在专利文献1中，道路地图显示用的数据是表示一条道路的链路信息的集合，各链路信息包含表示道路的节点(端点或交叉点)的节点信息，路径计算用的数据是节点数据的集合，各节点数据包含表示一个节点的节点信息及表示与该节点邻接的一个以上节点的邻接节点信息。由于如果追踪邻接节点信息便可识别道路的连接关系，因而基于路径计算用的数据中节点数据的邻接节点信息，来进行从出发地至目的地的路径计算，基于与作为其结果所获得的路径相关的节点信息，从道路地图显示用的数据来获取相关联的链路信息(道路形状)，基于所获得的链路信息显示出最佳路径。
专利文献1特开平8-292716号公报对于上述以往的地图信息的数据结构，在伴随着道路的新增、废弃、地图信息补充等而进行数据更新的场合下，为使道路地图显示用的数据与路径计算用的数据互相匹配，认为有必要将更新了的道路地图显示用的数据及路径计算用的数据双方存储到各使用者的装置。由各使用者的装置来更新数据的方法据认为包括分布寄存有更新了的数据的记录媒体的方法，以及通过通信来分布更新了的数据本身的方法。在任意一种场合下，在使用者的装置中只有单方面的数据被更新，有时其数据不能互相匹配。即，即使在分布记录媒体的场合下，也会因装置的误动作而使单方面的数据更新失败，在通过通信来分布数据的场合下，虽然路径计算用的数据被更新到最新状态，但也会因通信障碍而不能获得道路地图显示用数据的更新指示信息。这样可能产生以下不良结果即如果使用者的装置中存储了不同版本的数据，即使进行了路径计算，也不能使正确的显示装置画面上显示出所希望的路径。
发明内容
本发明旨在解决上述问题，其目的在于提供即使更新了的数据与更新失败的数据并存，也能实现适当处理的地图信息的数据结构，以及适于具有该数据结构的地图信息更新的更新指示信息的数据结构、地图信息处理装置及地图信息提供装置。
本发明涉及的地图信息的数据结构具备有链路识别信息，其表示与现实的道路部分分别对应的各元链路；副链路识别信息，其用于表示为置换任意元链路而设置的二个以上的代替链路，关于各链路，链路识别信息与副链路识别信息相对应，可以由地图信息处理装置使元链路与代替链路相关联。
本发明涉及的地图信息的数据结构具备有多个节点链路信息，其分别表示与现实的道路网的道路部分对应的各链路，各节点链路信息具有链路识别信息，其表示与现实的道路部分对应的链路；无效链路信息，其表示在设置置换元链路的二个以上的代替链路的场合下其元链路无效；连接信息，其使由上述代替链路组成的链路串与上述元链路相对应，这样，可以由地图信息处理装置使元链路与代替链路相关联。
图1是表示本发明实施方式1～4涉及的地图信息更新系统的框图。
图2是表示本发明实施方式1～4涉及的地图信息处理装置的框图。
图3是表示本发明实施方式1～4涉及的地图信息提供装置的框图。
图4是表示本发明实施方式1～4涉及的地图信息的概略数据结构的附图。
图5是表示变更前的实际道路网的地6是表示为作成本发明涉及的地图信息的道路数据帧而虚拟分配了节点及链路的道路网的附图。
图7是表示为作成本发明涉及的地图信息的路径计算系数据帧而将节点及链路虚拟分配到了用于路径计算的重要道路的道路网的附图。
图8是表示将构成图6的道路网的道路分解为链路串，为进行识别而将链路识别号附加到了各链路的道路网的附图。
图9是表示图7的路径计算中使用的链路与图8所示的链路识别号的关系的附图。
图10(a)是表示图4的地图信息的显示系数据帧中更新前的道路数据帧结构的附图。(b)是表示(a)的道路数据帧中的链路串记录的数据结构的附图。
图11是表示图10(a)中道路数据帧中的链路串记录的节点链路记录详情的附图。
图12是表示图10(a)中道路数据帧中的其它链路串记录的节点链路记录详情的附图。
图13是表示图4中地图信息的路径计算系数据帧中更新前的路径计算数据帧结构的附图。
图14是表示图13中路径计算数据帧中的节点记录详情的附图。
图15是表示变更后的实际道路网的地图。
图16是表示为更新本发明实施方式1涉及的地图信息的道路数据�。钩赏�15的道路网的道路分解为链路串，对各链路附加了链路识别号的道路网的附图。
图17是表示为更新本发明实施方式1～4涉及的地图信息的路径计算系数据帧而将节点及链路虚拟分配到了用于路径计算的重要道路的道路网的附图。
图18是表示实施方式1涉及的更新后的道路数据帧结构的附图。
图19是表示图18中道路数据帧中的链路串记录的节点链路记录详情的附图。
图20是表示图18中道路数据帧中的其它链路串记录的节点链路记录详情的附图。
图21是表示实施方式1～4涉及的更新后的路径计算数据帧结构的附图。
图22是表示图21的路径计算数据帧中节点记录详情的附图。
图23是表示图21的路径计算数据帧中其它节点记录详情的附图。
图24是表示本发明涉及的地图信息提供装置中寄存的更新指示信息数据库的结构的附图。
图25是表示本发明实施方式1、2涉及的更新指示信息的数据结构示例的附图。
图26(a)是表示包含用于道路数据帧更新的更新操作记录的更新指示信息的附图。(b)是表示用于道路数据帧更新的更新操作记录详情的附图。
图27(a)是表示包含用于路径计算数据帧更新的更新操作记录的更新指示信息的附图。(b)是表示用于路径计算数据帧更新的更新操作记录详情的附图。
图28是表示基于本发明实施方式1～4的地图信息提供装置动作的流程图。
图29是表示基于本发明实施方式1、2的地图信息处理装置动作的流程图。
图30是表示基于本发明实施方式1～4的地图信息处理装置的更新指示信息存储装置的更新指示信息寄存部的结构的附图。
图31是表示基于本发明实施方式1～4的地图信息处理装置的更新指示信息存储装置的地图信息寄存部的结构的附图。
图32是表示基于本发明实施方式1的地图信息处理装置的导航处理动作的流程图。
图33(a)是表示基于旧版显示系数据帧的地图显示画面的附图。(b)是表示基于新版显示系数据帧的地图显示画面的附图。
图34是表示导航处理中由地图信息处理装置作成的路径信息的结构的附图。
图35是表示基于更新了的路径计算数据帧所作成的路径信息内容的具体示例的附图。
图36是表示基于未更新的路径计算数据帧所作成的路径信息内容的具体示例的附图。
图37(a)是表示在基于未更新的道路数据帧的道路显示上重合显示最佳路径的地图显示画面的附图。(b)是表示在基于更新了的道路数据帧的道路显示上重合显示最佳路径的地图显示画面的附图。
图38是表示本发明实施方式2涉及的更新前的道路数据帧中链路串记录的节点链路记录详情的附图。
图39是表示为更新本发明实施方式2涉及的地图信息的道路数据�。钩杀涓蟮牡缆吠牡缆贩纸馕绰反愿髁绰犯郊恿肆绰肥侗鸷诺牡缆吠母酵肌�
图40是表示表示图39的道路网的实施方式2涉及的更新后的道路数据帧结构的附图。
图41是表示图40的道路数据帧中链路串记录的节点链路记录详情的附图。
图42是表示图40的道路数据帧中其它链路串记录的节点链路记录详情的附图。
图43是表示图40的道路数据帧中其它链路串记录的节点链路记录详情的附图。
图44是表示本发明实施方式2涉及的更新指示信息数据结构示例的附图。
图45是表示基于本发明实施方式2的地图信息提供装置动作的流程图。
图46是表示本发明实施方式3涉及的更新指示信息的数据结构的附图。
图47是表示基于本发明实施方式3的地图信息处理装置动作的流程图。
图48是表示基于本发明实施方式4的地图信息处理装置的导航处理动作的流程图。
图49是表示基于本发明实施方式4的地图信息处理装置的内部更新指示信息获取处理动作的流程图。
符号说明1输入装置，2位置检测装置，3收发装置(接收部)，4地图信息存储装置，5更新指示信息存储装置(寄存部)，6处理器(更新处理部)，7输出装置，10收发装置(发送部)，11更新指示信息存储装置(更新指示信息存储部)，12更新指示信息分布装置。
实施方式以下参照附图，对本发明涉及的各种实施方式作以说明。
实施方式1图1是表示基于本发明实施方式1的地图信息更新系统的结构的框图。如图1所示，该地图信息更新系统具备地图信息提供装置a2、多个地图信息处理装置a1。各地图信息处理装置a1是比如汽车中搭载的车用导航装置。地图信息提供装置a2通过通信网与各地图信息处理装置a1链接，可将各地图信息处理装置a1所具有的用于地图信息更新的更新指示信息在链接时提供到各地图信息处理装置a1。
图2是表示图1所示的地图信息处理装置a1的详情的框图。如图2所示，地图信息处理装置a1具备输入装置1、位置检测装置2、收发装置(接收部)3、地图信息存储装置4、更新指示信息存储装置(寄存部)5、处理器(更新处理部)6、输出装置7。
输入装置1根据使用者的操作或指示，向处理器6提供指示信号。具体地说，虽未图示，但输入装置1可以具有识别使用者的语音，输出基于语音的指示信号的语音识别装置、由使用者的手动操作来输出指示信号的操作钮以及其它适当的输入装置的至少任意一种。位置检测装置2是GPS(Global Positioning System)接收机等，检测当前位置，将检测出的位置信息提供到处理器6。
地图信息存储装置4中寄存有地图信息。收发装置3具有为更新地图信息而将更新指示信息请求发送到地图信息提供装置a2的功能及从地图信息提供装置a2接收更新指示信息的功能。
处理器6将收发装置3所接收的更新指示信息寄存到更新指示信息存储装置5。此外处理器6根据更新指示信息来变更即更新地图信息，并将被如此更新了的地图信息寄存到更新指示信息存储装置5。但本发明并非限定于该实施方式，也可将更新了的地图信息寄存(即改写保存)到地图信息存储装置4。
此外处理器6利用从位置检测装置2获得的当前位置及从地图信息存储装置4或更新指示信息存储装置5读出的地图信息，来进行各种导航处理。导航处理包含鉴别车辆所行驶的道路及道路上的位置的地图匹配、计算从出发值至目的地的路径的路径计算(路径探索)、使作为其结果获得的最佳路径候选与道路地图一同在显示装置的画面上显示的路径显示、根据最佳路径来进行从出发值至目的地的导向的路径导向以及当前位置周边的地图显示处理等。
输出装置7根据处理器6的导航处理输出，向使用者提示信息。具体地说，虽然未图示，但输出装置7可具有显示地图、当前位置、路径、导向信息等的显示装置以及以语音形式对使用者进行指示或导向的语音发生装置。
图3是表示图1所示的地图信息提供装置a2的结构的框图。地图信息提供装置a2具备收发装置(发送部)10、更新指示信息存储装置(更新指示信息存储部)11及更新指示信息分布装置12。更新指示信息存储装置11中寄存有具有用于使相应的地图信息处理装置a1更新地图信息的更新指示信息的更新指示信息数据库。收发装置10具有从通过通信网链接的各地图信息处理装置a1的收发装置3接收信号，向各地图信息处理装置a1的收发装置3个别发送信号的功能。收发装置10从地图信息处理装置a1接收到更新指示信息请求后，更新指示信息分布装置12从更新指示信息存储装置11获取(读出)所需的更新指示信息，使收发装置3向成为对象的地图信息处理装置a1发送该更新指示信息。
图4表示地图信息处理装置a1的地图信息存储装置4中寄存的地图信息的概略数据结构。地图信息具有管理信息帧、多个显示系数据帧、多个路径计算系数据帧、导向检索数据帧及其它种类的数据。
各显示系数据帧与一个地域(区域)对应，具有用于使输出装置7的显示装置显示出表示该区域的地图及与该区域相关联的关联信息的各种数据。各路径计算系数据帧也与一个地域(区域)对应，具有表示该区域内的道路节点(交叉点或端点)的数据。
导向检索数据帧具有比如目的地数据(住址、建筑物的电话号等)、表示目的地与区域的关联性的信息，用于按照使用者指定的目的地来选定必要区域的显示系数据帧及路径计算系数据帧。
管理信息帧具有用于显示系数据帧、路径计算系数据帧、导向检索数据帧等的管理及读出的数据及表示比如地图信息中各数据帧的所在位置和各数据帧的版本的数据。
如图4所示，各显示系数据帧具有用于地图匹配(基于当前位置的道路特定及道路上的位置鉴别)及道路显示的道路数据帧、用于显示河流及海洋等地图背景的背景数据帧、用于以文字来表示地名等名称的名称数据帧、用于路径引导的路径引导数据帧、用于检索周边设施的周边设施数据帧等。此外，各显示系数据帧具有显示系数据标头，显示系数据标头具有与包含表示该显示系数据帧所对应区域的信息等的显示系数据帧相关的各种属性、管理该显示系数据帧中包含的各数据帧的所在位置的信息等。
路径计算系数据帧具有用于路径计算的路径计算数据帧、路径计算系数据标头。路径计算系数据标头具有与包含表示该路径计算系数据帧所对应区域的信息等的路径计算系数据帧相关的各种属性、管理该路径计算系数据帧中包含的各路径计算数据帧的所在位置的信息等。
在说明基于本实施方式的地图信息的更新之前，先对地图信息的数据结构、数据要素的详情及地图信息的作成的基本原理作以说明。图5是表示设置于某区域的实际道路网的地图。在图5的示例中，多条道路2～5与大致横亘于横向上的二条道路0、1交叉。
图6表示在显示系数据帧的作成中，为表示图5的道路0～5的连接关系，即为将道路0～5作为道路网以数据来表示而虚拟分配的节点及链路。节点Nd0～Nd11被分配到道路0～5的交叉点及端点。链路Ld0～Ld13被分配到连接邻接的二个节点的道路部分。以下，将构成用于图示的地图显示及地图匹配的道路网的链路Ld0～Ld13称为显示系链路。此外为将各道路的形状作为线段的集合来表示，内插点P0～P24被分配到各道路的弯曲点。
如图6所示，在显示系数据帧的作成中，将1个道路作为链路串来处理。即，道路0(图5)称为链路串0，同样道路1～5称为链路串1至5。表示道路0的链路串0具有节点Nd0、Nd1、Nd2、Nd3、Nd4、Nd5、链路Ld0、Ld1、Ld2、Ld3、Ld4。此外在显示系数据帧的作成中，对各道路即链路串提供方向性，比如，对链路串0，将从节点Nd0至Nd5的方向作为顺向，将从节点Nd5至Nd0的方向作为逆向。
图7表示在路径计算系数据帧的作成中，被虚拟地分配到由路径计算中使用的重要道路0、1、3组成的道路网的节点及链路。这里，假设其它道路2、4、5不用于路径计算。节点Nr 0～Nr 5被分配到道路0、1、3的交叉点及端点。链路Lr0～Lr4被分配到连接邻接的二个节点的道路部分。以下，将构成图示的用于路径计算的道路网的链路Lr0～Lr4称为路径计算系链路。
图8表示表示构成图6的道路网的道路0～5的链路串0～5、以及为进行识别而附加到各显示系链路Ld0～Ld13的链路识别号。比如，链路Ld0的链路识别号是100，链路Ld10的链路识别号是110。链路识别号按照在同一链路串内，按链路串的顺向递增并成为连号的形式被提供到各链路。
如图8所示，道路的交叉可以作为链路串的交叉即连接来表示。比如，道路0与道路2的交叉点与链路串0的节点Nd1、链路串2的节点Nd1’对应。即，链路串0、2可看作是由节点Nd1及节点Nd1’来连接。利用这一点，对各节点，可表示表示与其它链路串的连接的交叉信息。比如，链路串0的节点Nd1的交叉信息作为连接目的地来表示链路串2的节点Nd1’，链路串2的节点Nd1’的交叉信息作为连接目的地来表示链路串0的节点Nd1。这样通过将交叉信息提供到各节点，可以把握交叉的链路串及全体链路串的连接关系。
图9表示图7的路径计算系链路Lr0～Lr4与图8所示的链路识别号的关系。前端链路识别号及终端链路识别号分别被附加到图7的路径计算系链路Lr0～Lr4。即在图7的1个链路(比如链路Lr1)中，附加到与此对应的图8的链路(比如从链路Ld2至Ld4)的最小链路识别号(比如102)被作为前端链路识别号来附加，最大链路识别号(比如104)被作为终端链路识别号来附加。由于各链路识别号按链路串的顺向递增来连号附加，因而与图7的路径计算系链路对应的图8的显示系链路可由该前端链路识别号及终端链路识别号来特定。比如，对图7的链路Lr1，特定作为链路识别号102～104的链路Ld2、Ld3、Ld4。
图10(a)表示图4的显示系数据帧中的道路数据帧示例。道路数据帧具有道路数据标头及多个链路串记录。图10(a)的道路数据帧表示图8的道路网。图中的链路串记录MR0～MR5被设置为分别与图8的链路串0～5对应，有关对应的链路串(道路)的信息被寄存。将链路串记录的排列顺序称为链路串号，利用链路串号0～5，可特定链路串记录MR0～MR5。在道路数据标头中寄存用于管理链路串记录数等链路串记录的信息。
对图10(a)的链路串记录MR0～MR5，以链路串记录MR0(与链路串0对应)为例进行说明。图10(b)表示图10(a)的链路串记录MR0的数据结构。链路串记录具有链路串标头及多个节点链路记录。图10(b)的节点链路记录NLR00、NLR01、NLR02、NLR03、NLR04、NLR05与顺向追溯链路串0时出现的节点与链路对(Nd0，Ld0)、(Nd1，Ld1)、(Nd2，Ld2)、(Nd3，Ld3)、(Nd4，Ld4)、(Nd5，无)分别对应。在链路串记录MR0中，节点链路记录NLR00～NLR05按照对应的节点与链路对的出现顺序来配置，将节点链路记录NLR00～NLR05的排列顺序称为节点链路号。利用节点链路号0～5，可特定节点链路记录NLR00～NLR05。
在节点链路记录中寄存有关对应的节点及链路的信息。比如，在节点链路记录NLR00中，寄存有关节点Nd0及链路Ld0(链路识别号100)的信息。在链路串标头中，寄存该链路串记录的数据长、该道路(比如在链路串记录MR0中为道路0)的道路类别、该道路中存在的节点数等。
图11表示图10(a)中链路串记录MR0(与链路串0对应)的节点链路记录NLR00～NLR05及链路串记录MR5(与链路串5对应)的节点链路记录NLR50、NLR51。各节点链路记录具有节点链路标头、交叉信息、节点坐标、链路识别信息、副链路识别信息、内插点信息。
节点链路标头中，寄存对应链路的内插点数以及表示副链路识别号是否被附加到对应的链路的副链路识别有无信息。此外虽然未图示，但还寄存该节点链路记录的数据长及对应链路的道路宽度等链路属性等。副链路识别号用于由于新设道路等的道路网变更或根据现实道路来补充地图信息的更新后的道路数据�。源嗽诤笪闹薪岷鲜莸母伦鞲晗傅乃得鳌Ｔ谕�11的示例中，副链路识别号未被附加到变更前的图8的道路网，因而副链路识别有无信息中寄存表示「无」的值。
在交叉信息中，寄存表示连接目的地链路串的链路串号及对应于连接目的地链路串的节点的节点链路记录的节点链路号。比如链路串记录MR0的节点链路记录NLR04(与图8的节点Nd4及链路Ld4对应)的交叉信息由链路串号5及节点链路号0来表示连接了节点Nd4的链路串5的节点Nd4’。此外链路串记录MR5的节点链路记录NLR50(与图8的节点Nd4’及链路Ld13对应)的交叉信息由链路串号0及节点链路号4来表示连接了节点Nd4’的链路串0的节点Nd4。这样节点链路记录NLR04、NLR50的交叉信息表示链路串0的节点Nd1与链路串5的节点Nd4’相连接。由于与道路端点涉及的节点Nd0，Nd5对应的节点链路记录NLR00、NLR05中，没有连接目的地链路，因而在链路串号及节点链路号中寄存-1。
节点坐标中寄存表示对应节点的地理位置的坐标值。链路识别信息中寄存附加到对应链路的链路识别号。比如，在节点链路记录NLR00中，对应节点Nd00的坐标及对应链路Ld0的链路识别号100分别被寄存到节点坐标及链路识别信息。此外末尾的节点链路记录(比如NLR05，NLR51)的链路识别信息中由于不存在对应的链路，因而寄存-1。
副链路识别信息用于由于新设道路等的道路网变更或根据现实道路来补充地图信息的更新后的道路数据�。淮嬖谟诟绷绰肥侗鸷疟桓郊拥蕉杂Φ牧绰分保绷绰肥侗鹦畔⒅屑拇娑杂α绰返母绷绰肥侗鸷�。在图11的示例中，由于副链路识别号未被附加到图8的变更前的道路网，因而不设置副链路识别有无信息。
内插点信息只存在于对应链路有一个以上的内插点之时，内插点信息中寄存表示链路的各内插点的地理位置的坐标值。比如，链路串记录MR0的节点链路记录NLR04(对应于图8的节点Nd4及链路Ld4)中，链路Ld4上的内插点P4的坐标被寄存到内插点信息。
图12同样表示图10(a)中链路串记录MR1(与链路串1对应)的节点链路记录NLR10～NLR15及链路串记录MR3(与链路串3对应)的节点链路记录NLR30、NLR31的数据结构及寄存内容。地图匹配及道路显示等中使用的显示系数据帧具有以上结构。
图13表示图4的路径计算系数据帧中的路径计算数据帧示例。路径计算数据帧具有路径计算数据标头及节点记录。假设图13的路径计算数据帧表示图7的道路网。图中的节点记录NrR0～NrR5被设置为与图7的节点Nr0～Nr5分别对应。路径计算数据标头中寄存用于管理节点记录数等节点记录的信息。节点记录中，寄存有关对应节点的信息。将节点记录的排列顺序称为节点号。
对图13的节点记录，以节点记录NrR1(与节点Nr1对应)为例进行说明。图14表示图13的节点记录NrR1的数据结构。节点记录具有节点记录标头、一个以上的连接记录。图14的连接记录CR10、CR11、CR12与被连接到与该节点记录NrR1对应的节点Nr1的链路Lr1，Lr4，Lr0分别对应。
节点记录标头中寄存该节点记录的数据长、表示与该节点记录对应的节点Nr1的地理位置的坐标值、该节点记录的连接记录数等。
各连接记录具有连接记录标头、邻接节点号、链路成本、对应链路识别信息、对应副链路识别信息、通行规则信息。
连接记录标头中寄存该连接记录的数据长、表示有无对应副链路识别信息的对应副链路识别有无信息。对应副链路识别信息用于由于新设道路等的道路网变更或根据现实道路来补充地图信息的更新后的路径计算数据�。源嗽诤笪慕岷鲜莸母伦鞲晗杆得�。在图14的示例中，副链路识别号未被附加到图8的变更前的道路网，因而副链路识别有无信息中寄存表示「无」的值。
在邻接节点号中寄存与该节点(节点Nr1)连接的链路(链路Lr1，Lr4，Lr0的任意一个)上与该节点邻接的节点(节点Nr2，Nr4，Nr0的任意一个)的节点号。比如，在连接记录CR10中，由链路Lr1与节点Nr1邻接的节点Nr2的节点号2被作为邻接节点号来寄存。
在链路成本中，作为用于路径计算中的成本评估的指标，与该连接记录对应的链路(比如在连接记录CR10中为链路Lr1)的行走所要求的所需时间等被寄存。
对应链路识别信息中寄存与该连接记录对应的链路的前端链路识别号及终端链路识别号(参照图8)。
对应链路副识别信息用于由于新设道路等的道路网变更或根据现实道路来补充地图信息的更新后的路径计算数据�。拇嬗敫昧蛹锹级杂Φ牧绰返那岸烁绷绰肥侗鸷偶爸斩烁绷绰肥侗鸷拧５谕�14的示例中，由于副链路识别号未被附加到图8的变更前的链路，因而不设置对应链路副识别信息。由对应链路识别信息(在有对应副链路识别信息的场合下为对应链路识别信息及对应副链路识别信息)，显示出与该连接记录对应的显示系链路Ld0，…(图8)的范围。
通行规则信息中寄存表示有关与该连接记录对应的链路的通行规则的信息。
路径计算中使用的路径计算系数据帧具有以上结构。具有上述说明的数据结构的地图信息被寄存到各地图信息处理装置a1的地图信息存储装置4。
接下来，对由于道路变更或根据现实道路的地图信息补充的地图信息更新作以说明。图15是表示在图5所示的道路网中新设了一个道路6的道路网的地图。对图15可以认为此前在地图信息中被忽视了的道路6也在地图信息中得到了记述。新设的道路6与道路0及道路1交叉。具体地说，图5的道路0的道路部分r0由道路6分割为二个道路部分r00、r01，道路1的道路部分r1由道路6分割为二个道路部分r10，r11。
图16是与图8同样的附图，表示在显示系数据帧的更新中，为表示图15的变更了的道路0～6的连接关系而被虚拟分配的节点、链路、链路串、链路识别号。如图16所示，设有对应于新设道路6的链路串6，链路串6具有单一的链路Ld14。图8的链路Ld3被分割为与图15的道路部分r00、r01对应的链路Ld3’、Ld3”，链路Ld8被分割为与图15的道路部分r10、r11对应的链路Ld8’、Ld8”。换言之，链路Ld3被置换为链路Ld3’、Ld3”，链路Ld8被置换为链路Ld8’、Ld8”。道路6(链路串6)由作为交叉点的节点Nd12、Nd12’被连接到道路0(链路串0)，由作为交叉点的节点Nd13、Nd13’被连接到道路1(链路串1)。节点Nd12’、Nd13’、链路Ld14组成链路串6。
当用替换链路来置换上述某个链路时，将链路Ld3、Ld8之类成为元的链路称为元链路，将链路Ld3’、Ld3”、Ld8’、Ld8”之类的替换链路称为代替链路。此外将元链路的链路识别号(比如，图8的链路识别号103、108)称为元链路识别号。
此外对代替链路，附加作为不同于元链路识别号的链路识别号的副链路识别号，利用元链路识别号和副链路识别号来识别代替链路。作为副链路识别号，假设取规定范围内的编号0～SIDMAX。比如，当取代某元链路L而设置的M条代替链路L0，L1，…，LM-1在元链路L的链路串的顺向上按L0，L1，…，LM-1的顺序来配置时，在链路L0，L1，…，LM-1中分别附加数值范围0～SID1-1，SID1～SID2-1，…，SIDM-1～SIDMAX。这里，假设0＜SID1＜SID2＜…＜SIDM-1≤SIDMAX。
为表示副链路识别号涉及哪个元链路，副链路识别号被与元链路的链路识别号组合。即，当将元链路的链路识别号设为idx，将上述副链路识别号设为sid时，在代替链路中附加综合链路识别号idxsid。比如，当将元链路L的链路识别号设为idx时，在代替链路L0，L1，…，LM-1中，附加综合链路识别号idx0～idxSID1-1，idxSID1～idxSID2-1，…，idxSIDM-1～idxSIDMAX。
在本实施方式中，假设SIDMAX＝255，在比如具有链路识别号103的元链路Ld3的代替链路Ld3’，Ld3”中，附加副链路识别号0～127，128～255，其结果如图16所示，在代替链路Ld3’，Ld3”中，附加综合链路识别号1030～103127，103128～103255。
此外，链路识别号与综合链路识别号之间在方便性即数据标记上的大小关系设定如下。比如，设想一种具有三个链路识别号id1、id2、id3，而且具有与链路识别号id2、id3相关联的二个综合链路识别号id2sid2，id3sid3的状态。链路识别号与综合链路识别号之间在数据标记上的大小关系设定如下。
如果id1＞id2则id1＞id2sid2，如果id1＝id2则id1＝id2sid2，如果id1＜id2则id1＜id2sid2。
综合链路识别号之间在数据标记上的大小关系规定如下。
如果id2＞id3则id2sid2＞id3sid3，id2＝id3时，如果sid2＞id3则id2sid2＞id3sid3，如果sid2＝id3则id2sid2＝id3sid3。
此外假设链路识别号之间在数据标记上的大小关系遵从于链路识别号在数据标记上的大小关系。
如后所述，根据上述数据标记上的大小关系，可表示串联连接的多个显示系链路所占据的链路识别号范围。该链路识别号范围用于路径计算系数据帧的更新。
图17是与图7同样的附图，表示在路径计算系数据帧的更新中，被虚拟分配到由变更了的路径计算中使用的道路0、1、3、6组成的道路网的节点、链路。这里，假设所追加的道路6被用于路径计算。如图17所示，设有对应于新设道路6的链路Lr5。图7的链路Lr1被分割为链路Lr1’、Lr2”，链路Lr3被分割为链路Lr3’、Lr3”。换言之，链路Lr1被置换为链路Lr1’、Lr1”，链路Lr3被置换为链路Lr3’、Lr3”。此外伴随道路6的新设，节点Nr6、Nr7被新设。
路径计算系链路Lr1’与图16的显示系链路Ld2、Ld3’对应，链路Lr1”与图16的链路Ld3”、Ld4对应，链路Lr3’与图16的链路Ld7、Ld8’对应，链路Lr3”与图16的链路Ld8”、Ld9对应，链路Lr5与图16的链路Ld14对应。
图16的显示系链路Ld2、Ld3’，即路径计算系链路Lr1’所占据的链路识别号范围基于元链路识别号102及综合链路识别号1030～103127，根据上述标记上的大小关系，被决定为102～103127，它被标记为102/103127。此外图16的显示系链路Ld3”、Ld4，即路径计算系链路Lr1”所占据的链路识别号范围基于综合链路识别号103128～103255及元链路识别号104，根据上述标记上的大小关系，被决定为103128～104，标记为103128/104。图17的链路识别号范围与图9的前端链路识别号/终端链路识别号对相对应。
链路识别号范围102～103127中，包含元链路识别号102，103、综合链路识别号1020～102255、1030～103127。此外链路识别号范围103128～104中，包含元链路识别号103，104、综合链路识别号103128～103255、1040～104255。
如上所述作为代替链路的链路识别号，通过采用元链路识别号和副链路识别号，可实现版本各异的地图信息的数据帧(比如旧版的显示系数据帧与新版的路径计算系数据帧)中的显示系链路与路径计算系链路的对应。
通过同样的方法，如图17所示，路径计算系链路Lr3’，Lr3”中，也基于元链路识别号和综合链路识别号来附加链路识别号的范围。对于未变更的路径计算系链路Lr0，Lr2，Lr4，前端链路识别号/终端链路识别号对不变更。对新设的Lr5，前端链路识别号及终端链路识别号均为114。
图18所示的道路数据帧是表示图16的道路网的更新了的道路数据帧。图18所示的道路数据帧中，链路串记录MR0’、MR1’、MR5’与道路0、1、5分别对应，是图10的道路数据帧中，对链路串记录MR0、MR1、MR5的一部进行了更新的记录。此外追加了表示新的链路串6的链路串记录MR6。道路数据标头也根据这些链路串记录的更新而被更新。
图19表示图18中的链路串记录MR0’(对应于链路串0)的节点链路记录NLR00～NLR05及链路串记录MR5’(对应于链路串5)中的节点链路记录NLR50、NLR51。图19中链路串记录的各节点链路记录结构与图11所示的元链路串记录的各节点链路记录结构相同。图19中的新链路串记录MR0’相对图11中的元链路串记录MR0，不同点在于，插入了新节点链路记录NLR04I，具有改变了旧节点链路记录NLR03的新节点链路记录NLR03’。
新追加的节点链路记录NLR04I与图16所示新设的节点Nd12及存在于其顺向上的链路Ld3”对应。此外旧节点链路记录NLR03与图8所示的节点Nd3及链路Ld3对应，而改变了的新节点链路记录NLR03’与图16所示的节点Nd3及链路Ld3’对应。元链路Ld3被分割为新链路Ld3’、Ld3”，与此相伴，新节点链路记录NLR03’中，副链路识别有无信息为显示「有」而被变更，内插点数及内插点坐标被更新，插入副链路识别信息。此外被追加的节点链路记录NLR04I中同样，副链路识别有无信息表示出「有」，副链路识别信息有效。
节点链路记录NLR03’、NLR04I的副链路识别信息中，寄存被附加到链路Ld3’、Ld3”的副链路识别号的最小值(如图16所示，在链路Ld3’中为0，在链路Ld3”中为128)。被附加到各链路的副链路识别号的范围可以从该节点链路记录及下一个节点链路记录的链路识别号、副链路识别号来判定。比如，由于节点链路记录NLR03’、NLR04I的链路识别信息相同(链路识别号＝103)，节点链路号为4(参照图10(b))的节点链路记录NLR04I的副链路识别信息为128，因而可判定节点链路号为3的链路Ld3’中提供了其范围为0～127(＝128-1)的副链路识别号。由于节点链路号为4、5的节点链路记录NLR04I、NLR04的链路识别信息各异，因而可判定链路Ld3”中提供了128～255副链路识别号。
另一方面，链路串记录MR5’(对应于链路串5)是变更了图11中元链路串记录MR5中的节点链路记录NLR50、NLR51的交叉信息的节点链路号的记录。这是因为通过向链路串0增加节点Nd12(参照图16)，现有的节点Nd4(对应于节点链路记录NLR50)的节点链路号从4变为5，通过向链路串1增加节点Nd13，现有的节点Nd10(对应于节点链路记录NLR51)的节点链路号也从4变为5。
图20表示图18中的链路串记录MR1’(对应于链路串1)的节点链路记录。链路串记录MR1’按照类似于链路串记录MR0’的形式被更新。即，图20的新链路串记录MR1’相对图12中的元链路串记录MR1的不同点在于，插入了新节点链路记录NLR14I，具有改变了旧节点链路记录NLR13的新节点链路记录NLR13’。
此外，伴随着这些链路串记录MR0’、MR1’、MR5’的内容更新，各链路串记录的链路串标头(参照图10(b))也被更新。
图21表示表示图17所示变更后的道路网的路径计算数据�。�22表示图21的一个节点记录的数据结构。图21及图22的路径计算数据帧及节点记录的结构与图13及图14所示的元路径计算数据帧及节点记录的结构相同。图21中的路径计算数据帧相对图13中的元路径计算数据帧的不同点在于，追加了新节点记录NrR6、NrR7，具有改变了旧节点记录NrR1、NrR2、NrR4、NrR5的新节点记录NrR1’、NrR2’、NrR4’、NrR5’。
新追加的节点记录NrR6、NrR7与图17所示的新设的节点Nr6、Nr7分别对应。此外更新了的节点记录NrR1’、NrR2’、NrR4’、NrR5’与旧节点记录NrR1’、NrR2’、NrR4’、NrR5’同样，与节点Nr1、Nr2、Nr4、Nr5分别对应。此外根据节点记录的更新，路径计算数据标头也被更新。
对图21的节点记录，以节点记录NrR1’(对应于节点Nr1)为例作以说明。图22表示图21的节点记录NrR1’的数据结构。图22的节点记录NrR1’是对图14的节点记录NrR1的节点记录标头及连接记录CR10进行了以下更新的记录。
首先，通过道路6的追加，在图17中取代元链路Lr1的代替链路Lr1’被连接到节点Nr1，节点Nr1的邻接节点取代节点Nr2，成为节点Nr6，因而将连接记录CR10的连接记录标头的对应副链路识别有无信息(终端)设为「有」，将邻接节点号从值2置换为表示节点Nr6的值6，将链路成本置换为与链路Lr1’对应的值，将对应链路识别信息的终端链路识别号置换为103。对应副链路识别有无信息的终端表示「有」这一点表示元链路(比如Lr1)在沿其顺向移动的途中被分割，即代替链路(比如Lr1’)的终端具有副链路识别号。反之，对应副链路识别有无信息的前端表示「有」这一点表示元链路(比如Lr1)在沿其反向移动的途中被分割，即代替链路的前端具有副链路识别号。
此外，插入将前端副链路识别号设为0，将终端副链路识别号设为127的对应副链路识别信息。在前端副链路识别号中，提供被附加到该代替链路的副链路识别号范围的最小值，在终端副链路识别号中，提供该副链路识别号范围的最大值。这些对应链路识别信息及对应副链路识别信息协同动作，表示链路Lr1’与图16所示的其链路识别号范围为102～103127的串联链路，即链路Ld2、Ld3’对应。因此，可基于新版的路径计算数据帧来判定旧版的道路数据帧中的对应链路。
图23表示作为图21的路径计算数据帧中追加的节点记录示例，构成节点记录NrR6的连接记录的主要内容。图23的连接记录CR60、CR61、CR62与被连接到与该节点记录NrR6对应的节点Nr6的链路Lr1”、Lr5、Lr1’分别对应。连接记录CR60由邻接节点号来表示通过了链路Lr1”的节点Nr6的邻接节点是节点Nr2(参照图17)，由对应链路识别信息及对应副链路识别信息，表示链路Lr1”与图16所示的其链路识别号范围为103128～104的串联链路即链路Ld3”、Ld4对应。连接记录CR61由邻接节点号来表示通过了链路Lr5的节点Nr6的邻接节点是节点Nr7，由对应副链路识别有无信息及对应链路识别信息，表示链路Lr5与图16所示的其链路识别号范围为114的链路即链路Ld14对应。连接记录CR62由邻接节点号来表示通过了链路Lr1’的节点Nr6的邻接节点是节点Nr1，由对应链路识别信息及对应副链路识别信息，表示链路Lr1’与图16所示的其链路识别号范围为102～103127的串联链路即链路Ld2、Ld3’对应。
以上，更新了的地图信息具有基于边参照图15至图23边说明的基本原理的数据结构。通过作为上述代替链路的链路识别号来采用元链路识别号及副链路识别号，版本各异的地图信息的数据帧(比如旧版的显示系数据帧及新版的路径计算系数据帧)中的显示系链路与路径计算系链路的对应成为可能。
因此，如果地图信息处理装置a1能获取更新了的地图信息，则该地图信息处理装置a1中也可进行有关最新的实际道路的地图显示、地图匹配及路径计算。如上所述，由于即使假设显示系数据帧与路径计算系数据帧的版本各异，链路的对应也是可能的，因而即使只能由地图信息处理装置a1获取单方的数据�。部上允菊返穆肪�。作为用于地图信息处理装置a1获取更新了的地图信息的方法，在本实施方式中，地图信息提供装置a2将更新指示信息发送到地图信息处理装置a1，地图信息处理装置a1根据更新指示信息来变更元地图信息后，便可获得更新了的地图信息(即，即使在各地图信息处理装置a1中也可更新地图信息)。
接下来，对地图信息处理装置a1更新地图信息的方法作以说明。图24表示寄存于地图信息提供装置a2的更新指示信息存储装置11(参照图3)的更新指示信息数据库的结构。当地图信息提供者将更新指示信息(后述)追加到更新指示信息数据库时，伴随着追加，对更新指示信息数据库的其它要素(后述的版数管理信息)进行必要的改变。
更新指示信息数据库具有一个版数管理信息和一个以上的版别信息组。各版别信息是用于将某版本的地图信息更新为最新版的地图信息的信息，只存在现有版数。版数管理信息是管理这些版别信息的信息，表示各版别信息的版数、所在位置及数据长等。
各版别信息具有一个更新指示信息管理信息和一个以上的更新指示信息组。更新指示信息对该版的显示系数据帧及路径计算系数据帧而设置，为将各版的显示系数据帧及各版的路径计算系数据帧更新为最新版而设置。但对管理信息帧、导向检索数据帧(参照图4)或其它数据�。部梢陨柚酶轮甘拘畔�。更新指示信息管理信息是管理这些更新指示信息的信息，表示各更新指示信息的所在位置及数据长等。
地图信息提供装置a2从地图信息处理装置a1接收到更新指示信息请求后，参照更新指示信息存储装置11内的更新指示信息数据库中的版数管理信息及更新指示信息管理信息，获取所需要的更新指示信息，将其发送到地图信息处理装置a1。
图25表示图24所示的更新指示信息的数据结构示例。如图25所示，更新指示信息具有一个更新指示信息标头、一个以上的更新操作记录组。更新指示信息标头表示更新对象数据帧的种类区分及区域(相应地域)。即，更新指示信息标头具有指定管理信息帧、显示系数据帧、路径计算系数据帧等应更新的数据帧的种类区分(参照图4)的更新数据区分指定及表示更新的数据帧的相应区域的区域指定(地域指定)。
更新操作记录表示为对更新指示信息标头所示的数据帧进行更新而应实施的数据操作。各更新操作记录具有更新对象类别、更新操作指定、更新对象位置、更新数据。更新对象类别作为更新指示信息标头所示的数据帧内成为更新对象的数据的类别，指定显示系数据标头、道路数据帧、路径计算系数据标头、或路径计算数据帧等。更新指定操作指定删除、追加、插入、改写等更新操作的种类。
更新对象位置表示由更新对象类别指定的数据内更新对象的位置。更新数据是被追加、插入或改写的数据内容本身。在删除的场合下，不设置更新数据。
更新对象位置更具体地说，具有第1记录号、第2记录号、更新对象偏置及更新对象数据长。第1记录号表示成为更新对象的链路串记录的链路串号(参照图10(a)及图18)、或成为更新对象的节点记录的节点号(参照图13及图21)等。第2记录号表示由第1记录号指定的记录内节点链路记录的节点链路号(参照图10(b))、连接记录的记录号(参照图14及图22)。更新对象偏置中，由来自由第2记录号指定的记录前端的字节数来表示由第2记录号指定的记录(节点链路记录、连接记录等)内的更新位置的前端。更新对象数据长表示删除或更新的数据的数据长。
然而，由于在标头(道路数据标头、链路串标头、路径计算数据标头、节点记录标头等)中，不提供链路串号、节点链路号、节点号等编号，因而对表示道路数据标头、路径计算数据标头等的第1记录号提供-1，对表示链路串标头、节点记录标头的第2记录号也提供-1。此外，在应更新的标头或各记录中不更新特定位置，对标头或记录总体进行统一更新的场合下，由于不进行更新对象偏置的指定，因而对更新对象偏置提供-1。
在第1记录号、第2记录号及更新对象偏置中，使用更新前的版本中所使用的值。
参照图26(a)及图26(b)，对用于将图10(a)的道路数据帧更新为图18的道路数据帧的更新指示信息作以说明。图26(a)表示包含用于道路数据帧的更新的更新操作记录的更新指示信息。图示的更新指示信息标头中，虽没有详细的图示，但将更新数据区分指定设为表示显示系数据帧的1，将区域指定(地域指定)设为显示系数据帧的相应区域。图中的更新操作记录组OPD1是用于更新显示系数据帧中的道路数据标头的更新操作记录的集合。更新操作记录组OPD2是用于将图10(a)的链路串记录MR0、MR1、MR5更新为图18的链路串记录MR0’、MR1’、MR5’的更新操作记录的集合。更新操作记录组OPD3是用于追加图18的链路串记录MR6的更新操作记录的集合。
图26(b)表示用于将图10(a)的链路串记录MR0更新为图18的链路串记录MR0’的更新操作记录0、1、2、3。即，图示的更新操作记录0～3是图26(a)的更新操作记录组OPD2的一部分。对于图26(b)中的更新对象位置，第1记录号0表示链路串号0，即，旧链路串记录MR0，第2记录号-1、3、4表示节点链路号「无」、3、4，即旧链路串标头与旧节点链路记录NLR03、NLR04。此外更新指示信息偏置-1表示对标头或记录总体进行统一更新。
因此，更新操作记录0指定用图18的链路串记录MR0’内的链路串标头来改写图10(a)的链路串记录MR0内的链路串标头的操作。更新操作记录1指定删除图11的链路串记录MR0内的节点链路号3的节点链路记录NLR03的操作。更新操作记录2指定在图11的链路串记录MR0内的节点链路号4的节点链路记录NLR04之前，插入图19的链路串记录MR0’的节点链路号3的节点链路记录NLR03’的操作。更新操作记录3指定在图11的链路串记录MR0的节点链路号4的节点链路记录NLR04之前，插入图19的链路串记录MR0’的节点链路号4的节点链路记录NLR04I的操作。
在由更新操作记录2、3插入的节点链路记录NLR03’、NLR04I中，作为代替链路Ld3’的链路识别信息及副链路识别信息，包含表示元链路Ld3的链路识别号103及代替链路Ld3’的副链路识别号0～127的信息(参照图19)，作为代替链路Ld3”的链路识别信息及副链路识别信息，包含表示元链路Ld3的链路识别号103及代替链路Ld3”的副链路识别号128～255的信息(参照图19)。
因此，接收到图26(a)及图26(b)所示的更新指示信息后，通过在地图信息处理装置a1中，进行基于上述更新操作记录的指示的更新操作，可对由更新指示信息标头指定的数据帧即显示系数据帧进行更新。
接下来，参照图27(a)及图27(b)，对用于将图13的路径计算数据帧更新为图21的路径计算数据帧的更新指示信息作以说明。图27(a)表示包含用于路径计算数据帧的更新的更新操作记录的更新指示信息。图示的更新指示信息标头中，尽管没有详细的图示，但将更新数据区分指定设为表示路径计算系数据帧的2，将区域指定(地域指定)设为路径计算系数据帧的相应区域。图中的更新操作记录组OPR1是用于更新路径计算系数据帧中的路径计算数据标头的更新操作记录的集合。更新操作记录组OPR2是用于将图13的节点记录NrR1、NrR2、NrR4、NrR5更新为图21的节点记录NrR1’、NrR2’、NrR4’、NrR5’的更新操作记录的集合。更新操作记录组OPR3是用于追加图21的节点记录NrR6、NrR7的更新操作记录的集合。
图27(b)表示用于将图14的节点记录NrR1更新为图22的节点记录NrR1’的更新操作记录0、1、2。即，图示的更新操作记录0～2是图27(a)的更新操作记录组OPR2的一部分。对于图27(b)中的更新对象位置，第1记录号1表示节点号1，即，旧节点记录NrR1，第2记录号-1、0、1表示连接记录号无、0、1，即旧节点记录标头与旧连接记录CR10、CR11。此外更新指示信息偏置-1表示对标头或记录总体进行统一更新。
因此，更新操作记录0指定用图22的节点记录NrR1’内的节点记录标头来改写图14的节点记录NrR1内的节点记录标头的操作。更新操作记录1指定删除图14的节点记录NrR1内的连接记录号0的连接记录CR10的操作。更新操作记录2指定在图14的节点记录NrR1内的连接记录号1的连接记录CR11之前，插入图22的节点记录NrR1’的连接记录号0的连接记录CR10的操作。
在由更新操作记录2插入的连接记录CR10中，作为路径计算系链路Lr1’的对应链路识别信息及对应副链路识别信息，包含表示元显示系链路Ld2、Ld3的链路识别号102、103及代替链路Ld3’的副链路识别号0～127的信息(参照图22)。
因此，接收到图27(a)及图27(b)所示的更新指示信息后，通过在地图信息处理装置a1中，进行基于上述更新操作记录的指示的更新操作，可对由更新指示信息标头指定的数据帧即路径计算系数据帧进行更新。
图28是表示地图信息提供装置a2的动作的流程图。在本实施方式中，每当从地图信息处理装置a1发出更新指示信息请求，地图信息提供装置a2便将必要的更新指示信息发送到地图信息处理装置a1。地图信息提供装置起动后，在步骤ST100，直至收发装置10接收到从相应的任意一个地图信息处理装置a1的收发装置3发送的更新指示信息请求，更新指示信息分布装置12处于待机状态。如果接收到更新指示信息请求，动作便进入步骤ST101。
在步骤ST101，更新指示信息分布装置12获取收发装置10所接收到的更新指示信息请求。该更新指示信息请求具有表示所请求的地图信息处理装置a1的地图信息处理装置识别符、表示所请求的地图信息处理装置a1的导航处理中所必需的区域(地域)及数据帧的种类的数据帧识别符及地图信息的版数识别符。该版数识别符表示地图信息处理装置a1当前所具有的数据帧的版本。
接下来在步骤ST102，更新指示信息分布装置12基于所获取的更新指示信息请求中的版数识别符，对更新指示信息存储装置11的版数管理信息(参照图24)进行检索，求出用于从地图信息处理装置a1当前具有的数据帧的版本更新到最新版的判别信息的所在位置。这样，基于更新指示信息请求中的数据帧识别符，对判别信息中的更新指示信息管理信息(参照图24)进行检索，获得与必要的数据帧对应的更新指示信息。
比如，假设图18的道路数据帧、图21的路径计算数据帧是最新版的数据，在发出了更新指示信息请求的地图信息处理装置a1的地图信息存储装置4中，图10(a)的道路数据帧、图13的路径计算数据帧被存储。在该场合下，显示系数据帧与路径计算系数据帧的更新指示信息请求被从地图信息处理装置a1的收发装置3发送后，地图信息提供装置a2的更新指示信息分布装置12获取包含用于将图10(a)的道路数据帧更新为图18的道路数据帧的图26(a)及图26(b)的更新操作记录的显示系数据帧的更新指示信息、以及包含用于将图13的路径计算数据帧更新为图21的路径计算数据帧的图27(a)及图27(b)的更新操作记录的路径计算系数据帧的更新指示信息。
这样，从更新指示信息存储装置11获取必要的一个以上的更新指示信息后，更新指示信息分布装置12由收发装置10将更新指示信息向所请求的地图信息处理装置a1发送。此后，其动作进入步骤ST100，直至收发装置10接收从相应的任意地图信息处理装置a1的收发装置3发送的更新指示信息请求，更新指示信息分布装置12再次待机。
通过上述过程，可将更新指示信息发送到请求了更新指示信息的地图信息处理装置a1。由于该更新指示信息为使比如图26(b)所示的更新操作记录2、3包含更新了的节点链路记录NLR03’、NLR04I(参照图19)，而对应更新的数据部分及其处理方式进行指定，因而可使地图信息处理装置a1进行地图信息更新。
图29是表示地图信息处理装置a1的处理器6的动作的流程图。地图信息处理装置a1起动后，首先在步骤ST200，处理器6实行输入受理处理。在输入受理处理期间，使用者利用输入装置1，将用于操作地图的显示比例尺、显示地图的滚动指示、目的地选择、路径计算的指示等的地图信息处理装置a1的指示提供到地图信息处理装置a1。输入装置1根据使用者的操作或指示，向处理器6提供各种指示信号，在输入受理处理期间，处理器6从输入装置1取入各种指示信号。接下来在步骤ST201，处理器6由位置检测装置2来识别当前位置。
此外在步骤ST202，基于在步骤ST200获得的指示信号、在步骤ST201识别出的当前位置、以及地图信息存储装置4中寄存的地图信息，处理器6决定导航处理中所必需的区域(地域)的显示系数据帧及路径计算系数据帧。这样，处理器6生成包含表示这些必需的数据帧的数据识别符、上述地图信息的版数识别符、以及表示该地图信息处理装置a1自身的地图信息处理装置识别符的更新指示信息请求，由收发装置4将更新指示信息请求向地图信息提供装置a2发送，由此来请求用于将必要的显示系数据帧及路径计算系数据帧更新为最新版的更新指示信息的发送。
接下来，在步骤ST203，根据步骤ST202的更新指示信息请求，处理器6通过收发装置3来接收从地图信息提供装置a2发送的显示系数据帧的更新指示信息及/或路径计算系数据帧的更新指示信息。处理器6将由收发装置3接收的更新指示信息寄存到更新指示信息存储装置5的更新指示信息寄存部。比如，在图18的道路数据帧、图21的路径计算数据帧是最新版的数据，在发出了更新指示信息请求的地图信息处理装置a1的地图信息存储装置4中存储图10(a)的道路数据帧、图13的路径计算数据帧的场合下，包含用于将图10(a)的道路数据帧更新为图18的道路数据帧的图26(a)及图26(b)的更新操作记录的显示系数据帧的更新指示信息以及包含用于将图13的路径计算数据帧更新为图21的路径计算数据帧的图27(a)及图27(b)的更新操作记录的路径计算系数据帧的更新指示信息被寄存到更新指示信息存储装置5。
图30表示地图信息处理装置a1的更新指示信息存储装置5内的更新指示信息寄存部的结构。在更新指示信息寄存部中，寄存一个更新指示信息管理数据和一个以上的更新指示信息0、1、2、…。更新指示信息管理数据进行更新指示信息寄存部中寄存的更新指示信息0、1、2、…的管理，因而具有表示各更新指示信息的寄存位置(存储装置内的地址)、数据长、获取状态等的更新指示信息管理记录。在上述的更新指示信息的接收中，在获取了更新指示信息的场合下，处理器6在将该更新指示信息寄存到更新指示信息寄存部的同时，将为表示其寄存位置、数据长、已获取了获取状态而设定的更新指示信息管理记录寄存到更新指示信息管理数据。另一方面，在由于通信障碍等而未获取更新指示信息的场合下，处理器6在将与所请求的更新指示信息的更新指示信息标头相当的数据作为更新指示信息来寄存到更新指示信息寄存部的同时，将为表示其寄存位置、数据长、未获得获取状态而设定的更新指示信息管理记录寄存到更新指示信息管理数据。因此，每当地图信息处理装置a1发送更新指示信息请求，更新指示信息寄存部中寄存的更新指示信息0、1、2、…便增加。
在接收到了更新指示信息的场合下，比如具有用于将图10(a)的道路数据帧更新为图18的道路数据帧的更新操作记录的图26(a)及图26(b)的显示系数据帧的更新指示信息、具有用于将图13的路径计算系数据帧更新为图21的路径计算数据帧的更新操作记录的图27(a)及图27(b)的路径计算系数据的更新指示信息、以及管理这些更新指示信息的更新指示信息管理记录被寄存到更新指示信息寄存部。
接下来，在步骤ST204，处理器6从地图信息存储装置4获取(读出)在步骤ST202决定的显示系数据帧(更新前)。比如，获取具有图10(a)的道路数据帧的显示系数据帧。
在步骤ST205，处理器6对在步骤ST204中获取的显示系数据帧进行更新。具体地说，首先处理器6从更新指示信息存储装置5的更新指示信息寄存部获取所需区域(地域)的显示系数据帧的更新指示信息，检查有关该更新指示信息的更新指示信息管理记录内的获取状态。如果有关该更新指示信息的获取状态表示获取结束，则处理器6根据所获取的更新指示信息，对在步骤ST204中获取的显示系数据帧进行更新，将更新了的显示系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。另一方面，如果有关更新指示信息的获取状态表示未获�。虼砥�6对在步骤ST204中获取的显示系数据帧不作任何变更，寄存到更新指示信息存储装置5的地图信息寄存部。
因此，如果有关更新指示信息的获取状态表示获取结束，则根据更新指示信息的更新操作记录的指示，对具有图10(a)的道路数据帧的显示系数据帧实施更新操作，将所获得的更新结束显示系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。此时地图信息寄存部中寄存的显示系数据帧的道路数据帧被更新为图18的道路数据帧。即根据更新指示信息，处理器6对显示系数据帧进行更新，由此地图信息处理装置a1可获得更新后的显示系数据帧。此外如果有关更新指示信息的获取状态表示未获�。蚓哂形锤碌耐�10(a)的道路数据帧的显示系数据帧被寄存到地图信息寄存部。
图31表示更新指示信息存储装置5内的地图信息寄存部的结构一例。地图信息寄存部寄存与多个区域(地域)分别对应的多个显示系数据帧、以及与多个区域分别对应的多个路径计算系数据帧等，同时具有用于管理这些显示系数据帧及路径计算系数据帧的管理信息帧。管理信息帧具有表示各显示系数据帧、及各路径计算系数据帧的所在位置(更新指示信息存储装置5内的地址)的数据。在本质上，地图信息寄存部的内容与图4所示的地图信息存储装置4内的地图信息相同。
此外在步骤ST206，处理器6从地图信息存储装置4获取(读出)在步骤ST202决定的路径计算系数据帧(更新前)。比如，获取具有图13的路径计算数据帧的路径计算系数据帧。
在步骤ST207，处理器6对在步骤ST206中获取的路径计算系数据帧进行更新。具体地说，首先处理器6从更新指示信息存储装置5的更新指示信息寄存部获取所需区域(地域)的路径计算系数据帧的更新指示信息，检查有关该更新指示信息的更新指示信息管理记录内的获取状态。如果有关该更新指示信息的获取状态表示已获�。虼砥�6根据所获取的更新指示信息，对在步骤ST204中获取的路径计算系数据帧进行更新，将更新了的路径计算系数据帧寄存到更新指示信息存储装置5内的地图信息寄存部。另一方面，如果有关更新指示信息的获取状态表示未获�。虼砥�6对在步骤ST204中获取的路径计算系数据帧不作任何变更，寄存到更新指示信息存储装置5的地图信息寄存部。
因此，如果有关更新指示信息的获取状态表示获取结束，则根据更新指示信息的更新操作记录的指示，对具有图13的路径计算数据帧的路径计算系数据帧实施更新操作，将所获得的更新结束路径计算系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。此时地图信息寄存部中寄存的路径计算系数据帧的路径计算数据帧被更新为图21的路径计算数据帧。即根据更新指示信息，处理器6对路径计算系数据帧进行更新，由此地图信息处理装置a1可获得更新后的路径计算系数据帧。此外如果有关更新指示信息的获取状态表示未获�。蚓哂形锤碌耐�13的路径计算数据帧的路径计算系数据帧被寄存到地图信息寄存部。
在步骤ST208，实行导航处理子步骤，在其结束后，其动作返回步骤ST200并重复。导航处理利用在步骤ST205、步骤ST207中被寄存到更新指示信息存储装置5的地图信息寄存部的显示系数据帧、路径计算系数据�。菰诓街鑃T200获得的指示信号来进行。
图32是表示作为步骤ST208的导航处理，进行地图显示、路径计算及路径显示时的动作的流程图。
首先，在步骤ST300，利用更新指示信息存储装置5的地图信息寄存部中寄存的所需区域的显示系数据�。砥�6在输出装置7的显示装置上显示出地图画面。如果该显示系数据帧是已被更新的数据�。蚓哂型�18的道路数据�。蚨缤�33(b)所示，显示出图15的道路，如果显示系数据帧不是被更新了的数据�。蚓哂型�10(a)的道路数据�。蚨缤�33(a)所示，显示出图5的道路。
在步骤ST301，利用更新指示信息存储装置5的地图信息寄存部中寄存的所需区域的路径计算系数据帧的路径计算数据�。砥�6进行基于达库斯特法等的路径计算。由该路径计算求出从出发地至目的地的所需时间等成本成为最小的路径，获取按节点的经由顺序来排列的经由该从出发地至目的地的节点的节点号的经由节点信息。将这些节点称为经由节点。
在步骤ST302，基于由步骤ST301求出的经由节点信息，从所需区域的路径计算系数据帧的路径计算数据帧抽出有关构成最佳路径的链路的信息，基于此来作成路径信息。
图34表示由地图信息处理装置a1作成的路径信息的结构。路径信息具有表示与连接路径节点之间的路径计算系链路对应的显示系链路的链路识别号的路径链路记录排序及表示该路径链路记录数的路径链路记录数。路径链路记录具有从图14及图22所示的连接记录抽出的副链路识别信息有无信息、对应链路识别信息、对应副链路识别信息。由于对应链路识别信息表示该路径计算系链路对应的显示系链路的链路识别号范围，因而具有前端链路识别号和终端链路识别号。由于对应副链路识别信息表示代替链路的副链路识别号范围，因而具有前端副链路识别号和终端副链路识别号。对应副链路识别有无信息表示对应副链路识别信息的前端对应副链路识别号、终端对应副链路识别号的有无。
对各路径节点，从路径节点的节点记录中找出将下一次经由的路径节点作为邻接节点的连接记录，抽出该连接记录中的对应对应链路识别信息、副链路识别信息，将其设定到路径链路记录的对应对应链路识别信息、副链路识别信息，由此来获得路径信息。
图35及图36表示路径信息内容的具体示例。图35是基于更新了的路径计算数据帧来作成的路径信息的内容，表示作为路径计算的结果所获得的路径经由图17的节点Nr3、Nr4、Nr1、Nr6、Nr2。对应链路识别信息及对应副链路识别信息表示与图17的路径计算系链路Lr2、Lr4、Lr1’、Lr1”对应的图16的显示系链路的链路识别号。其结果是，可看出图16的显示系链路Ld5、Ld6、Ld11、Ld2、Ld3’、Ld3”、Ld4相当于最佳的路径。
图36是基于未更新的路径计算数据帧来作成的路径信息内容，表示作为路径计算的结果所获得的路径经由图9的节点Nr3、Nr4、Nr1、Nr2。对应链路识别信息及对应副链路识别信息表示与图9的路径计算系链路Lr2、Lr4、Lr1对应的图8的显示系链路的链路识别号。其结果是，可看出图8的链路Ld5、Ld6、Ld11、Ld2、Ld3、Ld4相当于最佳的路径。
在步骤ST303，处理器6判断路径信息内是否有未取出的路径链路记录。在为后述的步骤ST304而全部取出路径链路记录的场合下，步骤ST303的判断成为否定，动作结束(即图29的步骤ST208的导航处理结束)。另一方面，在路径信息内有未取出的路径链路记录的场合下，其动作转入步骤ST304。
在步骤ST304，处理器6从路径信息取出一个未取出的路径链路记录。该取出用于基于所取出的各路径链路记录，特定显示系链路的形状，使显示装置进行显示。
在步骤ST305，处理器6判断更新指示信息存储装置5的地图信息寄存部中寄存的所需区域的显示系数据帧的道路数据帧内是否有未取出的节点链路记录。在为后述的步骤ST306而全部取出节点链路记录的场合下，步骤ST305的判断成为否定，动作返回步骤ST303。另一方面，在所需区域的显示系数据帧的道路数据帧内有未取出的节点链路记录的场合下，其动作进入步骤ST306。
在步骤ST306，处理器6从更新指示信息存储装置5的地图信息寄存部中寄存的所需区域的显示系数据帧的道路数据帧取出一个未取出的节点链路记录。
在步骤ST307，判断在步骤ST304已取出的路径链路记录是否与在步骤ST306取出的节点链路记录相关联。更具体地说，基于上述链路识别号及综合链路识别号在数据标记上的大小关系，判定由在步骤ST306取出的节点链路记录的链路识别信息及副链路识别信息所示的链路识别号的范围(以下称范围A)是否被包含在由在步骤ST304取出的路径链路记录的对应链路识别信息及对应副链路识别信息所示的链路识别号的范围内(以下称范围B)。如果范围A包含在范围B内，则动作进入步骤ST308，如果不包含，则返回步骤ST305。
通过上述处理，使附加了路径信息中各路径链路记录中指定的链路识别号范围B的链路与附加了显示系数据帧中所需的节点链路记录中指定的链路识别号范围A的链路相对应。接下来，在步骤ST308，处理器6获得相对应的节点链路记录的节点坐标、内插点坐标。即，对与在步骤ST304从路径信息取出的路径链路记录对应的显示系链路形状进行特定。
在步骤ST309，利用在步骤ST308获取的节点坐标、内插点坐标，使该路径链路的形状显示于在步骤ST300在输出装置7的显示装置中显示的地图画面上。如图37(a)或图37(b)所示，该最佳路径链路通过粗于表示通常道路的线的粗线，与道路重合显示。
步骤ST309之后，动作返回步骤ST303，此后重复步骤ST303～309，基于下一路径链路记录来显示路径链路，最终在地图画面上显示出图37(a)或图37(b)所示的路径。
在本实施方式中，由所需区域的更新指示信息的接收状态即获取状态，在地图信息处理装置a1中，所需区域的路径计算数据帧及显示系数据帧的更新状态相同或各异。即，存在以下4种状态。
在第1状态，在地图信息处理装置a1，所需区域的路径计算数据帧及显示系数据帧共同被更新。根据更新指示信息，比如图21所示的路径计算数据帧及图18所示的道路数据帧由地图信息处理装置a1作成，寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，在步骤ST307使用的链路识别号范围A、B成为共同更新后的范围。
在第2状态，所需区域的路径计算数据帧被更新，但显示系数据帧不更新。比如，图21所示的更新后的路径计算数据帧和图10所示的旧版道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A更新后，范围B成为更新前(旧版)的范围。
在第3状态，所需区域的路径计算数据帧不更新，但显示系数据帧被更新。比如，图13所示的旧版路径计算数据帧和图18所示的更新后的道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A更新前，范围B成为更新后的范围。
在第4状态，所需区域的路径计算数据帧及显示系数据帧不共同更新。比如，图13所示的旧版路径计算数据帧和图10所示的旧版道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A、B共同成为更新前的范围。
在上述的步骤ST307的判定中，路径链路记录及节点链路记录的相关联具体按下述来进行。
在上述第1状态下，假设基于更新了的路径计算数据帧来作成图35所示的路径信息。对路径链路记录0，具有其链路识别号范围为105～106的链路识别号的节点链路记录是图20的链路串记录MR1’的节点链路记录NRL10、NLR11(对应于图16的Ld5，Ld6)。对路径链路记录1，具有其链路识别号范围为111～111的链路识别号的节点链路记录是图12的链路串记录MR3的节点链路记录NRL30(对应于图16的Ld11)。对路径链路记录2，具有其链路识别号范围为102～103127的链路识别号的节点链路记录是图19的链路串记录MR0’的节点链路记录NRL02、NLR03’(对应于图16的Ld2，Ld3’)。对路径链路记录3，具有其链路识别号范围为103128～104的链路识别号的节点链路记录是图19的链路串记录MR0’的节点链路记录NRL04I、NLR04(对应于图16的Ld3”，Ld4)。
因此，相当于图16的链路Ld5、Ld6、Ld11、Ld2、Ld3’、Ld3”、Ld4的最佳路径链路被显示于显示画面。其显示结果如图37(b)所示。即，最佳路径链路在变更后的道路显示上重合显示。
在上述第2状态下，假设基于更新了的路径计算数据帧来作成图35所示的路径信息。对路径链路记录0，具有其链路识别号范围为105～106的链路识别号的节点链路记录是图12的链路串记录MR1的节点链路记录NRL10、NLR11(对应于图8的Ld5，Ld6)。对路径链路记录1，具有其链路识别号范围为111～111的链路识别号的节点链路记录是图12的链路串记录MR3的节点链路记录NRL 30(对应于图8的Ld11)。对路径链路记录2，具有其链路识别号范围为102～103127的链路识别号的节点链路记录是图11的链路串记录MR0的节点链路记录NRL02、NLR03(对应于图8的Ld2，Ld3)。对路径链路记录3，具有其链路识别号范围为103128～104的链路识别号的节点链路记录是图19的链路串记录MR0’的节点链路记录NRL03、NLR04(对应于图8的Ld3，Ld4)。
因此，相当于图8的链路Ld5、Ld6、Ld11、Ld2、Ld3、Ld4的最佳路径链路被显示于显示画面。其显示结果如图37(a)所示。即，最佳路径链路在变更前的道路显示上重合显示。
在第3状态下，假设基于未更新的路径计算数据帧来作成图36所示的路径信息。对路径链路记录0，具有其链路识别号范围为105～106的链路识别号的节点链路记录是图20的链路串记录MR1’的节点链路记录NRL10、NLR11(对应于图16的Ld5，Ld6)。对路径链路记录1，具有其链路识别号范围为111～111的链路识别号的节点链路记录是图12的链路串记录MR3的节点链路记录NRL30(对应于图16的Ld11)。对路径链路记录2，具有其链路识别号范围为102～104的链路识别号的节点链路记录是图19的链路串记录MR0’的节点链路记录NRL02、NLR03’、NLR04I、NLR04(对应于图16的Ld2、Ld3’、Ld3”、Ld4)。
因此，相当于图16的链路Ld5、Ld6、Ld11、Ld2、Ld3’、Ld3”、Ld4的最佳路径链路被显示于显示画面。其显示结果如图37(b)所示。即，最佳路径链路在变更后的道路显示上重合显示。
在上述第4状态下，假设基于未更新的路径计算数据帧来作成图36所示的路径信息。对路径链路记录0，具有其链路识别号范围为105～106的链路识别号的节点链路记录是图12的链路串记录MR1的节点链路记录NRL10、NLR11(对应于图8的Ld5，Ld6)。对路径链路记录1，具有其链路识别号范围为111～111的链路识别号的节点链路记录是图12的链路串记录MR3的节点链路记录NRL30(对应于图8的Ld11)。对路径链路记录2，具有其链路识别号范围为102～104的链路识别号的节点链路记录是图12的链路串记录MR0的节点链路记录NRL02、NLR03、NLR04(对应于图8的Ld2、Ld3、Ld4)。
因此，相当于图8的链路Ld5、Ld6、Ld11、Ld2、Ld3、Ld4的最佳路径链路被显示于显示画面。其显示结果如图37(a)所示。即，最佳路径链路在变更前的道路显示上重合显示。
虽然在上述第2状态及第3状态下，在地图信息处理装置a1中存储版本各异的显示系数据帧及路径计算系数据�。缟纤觯诒臼凳┓绞较拢」芟允鞠凳葜〖奥肪都扑阆凳葜〉陌姹靖饕欤钥山辛绰范杂�。因此，在地图信息处理装置a1中，即使只能获取单方数据�。钥上允菊返穆肪�。
如上所述，根据本实施方式1，地图信息的数据结构中，地图显示用的道路数据部分(道路数据帧)具有表示元链路的链路识别信息、用于表示代替链路的副链路识别信息，对于各链路，链路识别信息与副链路识别信息相对应，由地图信息处理装置(计算机、逻辑电路或其组合)，其元链路与代替链路的相关联成为可能(参照图11、图12、图19及图20)。此外路径计算用的路径计算数据部分(路径计算数据帧)也具有表示元链路的链路识别信息(对应链路识别信息)、用于表示代替链路的副链路识别信息(对应副链路识别信息)，对于各链路，链路识别信息与副链路识别信息相对应，由地图信息处理装置，其元链路与代替链路的相关联成为可能(参照图14、图22及图23)。因此，即使道路数据帧的版本与路径计算数据帧的版本各异，新设的代替链路也可与元链路对应。因此，在地图信息处理装置a1中，即使只能更新单方数据帧，仍可显示正确的路径。
此外，更新指示信息的数据结构中，将有关代替链路的信息部分追加到地图信息的更新操作记录具有表示元链路的链路识别信息、表示该代替链路的副链路识别信息(参照图26(b)及图27(b))，因而对上述地图信息的道路数据帧的更新或路径计算数据帧的更新均适合，接收了更新指示信息的地图信息处理装置a1中，处理器6可根据更新操作记录的指定来自动更新该记录。
在该实施方式下，在更新指示信息的数据结构中，各更新操作记录将更新对象类别及更新对象位置指定到地图信息处理装置(计算机、逻辑电路或其组合)，因而可只将更新所必需的更新数据(链路串标头、节点链路记录、节点记录或连接记录)提供到地图信息处理装置a1来更新。即可缩小更新指示信息的长度。
实施方式2接下来，对本发明的实施方式2作以说明。图1至图3所示的地图信息处理装置a1及地图信息提供装置a2也用于实施方式2。实施方式2中的地图信息处理装置a1及地图信息提供装置a2的各构成要素的功能与实施方式1中的功能基本相同。此外地图信息处理装置a1中使用的地图信息(图4)的内容也与实施方式1中的地图信息内容基本类似，具有与参照图10至图14在上文记述的显示系数据帧及路径计算系数据帧相同的数据帧。
不过，显示系数据帧的道路数据帧中链路串记录的结构与图11所示相异。图38表示实施方式2涉及的链路串记录的结构。图38的链路串记录中，节点链路标头除了对应链路的内插点数及副链路识别有无信息，还寄存表示对应链路是无效还是有效的无效链路信息。在初版地图信息中，无效链路信息中 寄存设为有效的值。
对该实施方式，结合图5至图9所示的地图显示来作说明。因此图38所示的链路串记录也基于图5、图6及图8所示的地图来作成，无效链路信息以外的结构及数值与图11所示的链路串记录相同。
接下来，对由于道路网的变更或根据现实道路补充地图信息的地图信息更新作以说明。与有关实施方式1的说明同样，如图15所示，假设新记述一个道路6。图39是与图16同样的附图，表示在显示系数据帧的更新中，为表示图15的变更了的道路0～6的连接关系而被假想分配的节点、链路、链路串、链路识别号。
如图所示，设有对应于新设或应在地图信息中新记述的道路6的链路串6，设有与链路串6连接的新链路串7、8。链路串7对应于与图8的元链路Ld3相同的道路部分r0(参照图5)，具有对应于道路部分r00、r01(参照图15)的代替链路Ld3’、Ld3”。链路串8对应于与图8的元链路Ld8相同的道路部分r1(参照图5)，具有对应于道路部分r10、r11(参照图15)的代替链路Ld8’、Ld8”。
这样，链路串7通过其两端的节点Nd3”、Nd4”连接到对应于变更前道路网中道路0的道路部分r0的链路Ld3两端的节点Nd3、Nd4，同样链路串8通过其两端的节点Nd3”、Nd4”连接到对应于变更前道路1的道路部分r1的链路Ld8两端的节点Nd9、Nd10。此外链路串7通过其节点Nd12连接到链路串6前端的节点Nd12’，链路串8通过其节点Nd13连接到链路串6终端的节点Nd13’。此外通过后述的方法，链路Ld3、Ld8被看作是无效链路，即这些链路Ld3、Ld8被看作不存在。此外与图16的链路Ld3’、Ld3”、Ld8’、Ld8”相同的链路识别号分别被附加到链路Ld3’、Ld3”、Ld8’、Ld8”。
图40表示表示图39的道路网的道路数据帧。道路数据帧具有与图10(a)的道路数据标头同样的道路数据标头、多个链路串记录MR0S～MR8S。链路串记录MR0S～MR8S被设置为与图39的链路串0～8分别对应，有关对应的链路串的信息被寄存。
图41表示图40的链路串记录MR0S的内容。图41中的链路串记录的各节点链路记录的结构与图38所示的元链路串记录的各节点链路记录的结构相同。链路串记录MR0S是对图38的链路串记录MR0进行了以下更新的记录。
图41中改变了的节点链路记录NLR03S(对应于节点Nd3及元链路Ld3)是使元节点链路记录NLR03的无效链路信息无效，同时为使节点Nd3的连接目的地节点表示链路串7的节点Nd3”而变更交叉信息的记录。此外改变了的节点链路记录NLR04S(对应于节点Nd4及链路Ld4)是为使链路Ld3、Ld4之间的节点Nd4的连接目的地节点表示链路串7的节点Nd4”而变更元节点链路记录NLR04的交叉信息的记录。
图42表示图40的链路串记录MR7S(对应于新设的链路串7)的内容。链路串记录MR7S的节点链路记录NLR70S、NLR71S、NLR72S与顺向追溯链路串7时出现的节点与链路对(Nd3”，Ld3’)、(Nd12，Ld3”)、(Nd4”，无)分别对应。在链路串记录MR7S中，使节点链路记录的无效链路信息全部有效，表示链路Ld3’、链路Ld3”有效。与链路串7的节点Nd3”、Nd12、Nd4”对应的节点链路记录NLR70S、NLR71S、NLR72S的交叉信息被设定为连接目的地分别成为链路串4的节点Nd3’、链路串6的节点Nd12’、链路串5的节点Nd4’。此外，作为链路Ld3’、Ld3”的链路识别信息，将与链路Ld3相同的链路识别号103设定到节点链路记录NLR70S、NLR71S。此外，作为链路Ld3’、Ld3”的副链路识别信息，分别将0、128设定到节点链路记录NLR70S、NLR71S。
从图41所示的节点链路记录NLR03S的交叉信息的链路串号7、节点链路号0，导出图42所示的节点链路记录NLR70S，反之从节点链路记录NLR70S的链路串号0、节点链路号3，导出节点链路记录NLR03S。此外从图41所示的节点链路记录NLR04S的交叉信息的链路串号7、节点链路号2，导出图42所示的节点链路记录NLR72S，反之从节点链路记录NLR72S的链路串号0、节点链路号4，导出节点链路记录NLR04S。因此可看出，元链路Ld3由节点Nd3(Nd3”)及节点Nd4(Nd4”)与代替链路Ld3’、链路Ld3”交叉。
图43表示图40的链路串记录MR6S(对应于新设的链路串6)的内容。链路串记录MR6S的节点链路记录NLR60S、NLR61S与顺向追溯链路串6时出现的节点与链路对(Nd12’，Ld14)、(Nd13’，无)分别对应。在链路串记录MR6S中，使节点链路记录的无效链路信息全部有效，表示链路Ld14有效。与链路串7的节点Nd12’、Nd13’对应的节点链路记录NLR60S、NLR61S的交叉信息被设定为连接目的地分别成为链路串7的节点Nd12、链路串8的节点Nd13。此外，作为链路Ld14的链路识别信息，将链路识别号114设定到节点链路记录NLR60S。
图40的链路串记录MR1S(对应于链路串1)、链路串记录MR8S(对应于新设的链路串8)也与上述同样，被设定为表示图39的道路网。
以上，更新后的地图信息的显示系数据帧具有遵从参照图39至图43说明的基本原理的数据结构。具有路径计算数据帧的路径计算系数据帧具有与实施方式1同样的数据结构，更新后的路径计算数据帧也具有与实施方式1同样的数据结构(参照图17、图21～图23)。
如上所述，在道路数据的现有的链路串记录中，通过由串联连接的代替链路(比如Ld3’、Ld3”)来置换元链路(比如Ld3)的更新，既不进行元链路的节点链路记录(比如NLR03)删除也不进行代替链路的节点链路记录插入。因此，对应于图39的链路串0的节点Nd4、Nd5及链路串1的节点Nd10、Nd11的图40的链路串记录MR0S、MR1S中的节点链路记录(比如NLR04S、NLR05)的节点链路记录号与图10(a)的链路串记录MR0、MR1中的节点链路记录号相同。因此，在具有使用这些节点链路记录号的交叉信息的图40的链路串记录MR2S～MR5S中，提供与图10(a)的链路串记录MR2～MR5的节点链路号相同的值。即，有关图39的链路串0、链路串1的更新对有关链路串2～链路串5的链路串记录MR2～MR5不产生影响，不必进行不变更对应道路的链路串2～链路串5的链路串记录MR2～MR5的更新。比如，从图38的节点链路记录NLR50的链路串号0及节点链路号4导出图41的节点链路记录NLR04S，从节点链路记录NLR04S的链路串号7及节点链路号2导出图42的节点链路记录NLR72S，因而交叉信息的可靠性也可被维持。
对于传统的地图信息的数据结构，伴随道路的新设等，在有必要进行数据更新的场合下，有可能应更新的信息量较多，各使用者的地图信息处理装置中更新所需的时间增加。比如，在新设道路或在地图信息上重新表示现有道路的场合下，在道路地图显示用数据中，伴随重新表示道路的链路串记录的追加，该道路的链路所交叉的元链路被分割为代替链路，因而认为有必要进行表示与按顺向移动在元链路之后出现的所有节点及链路有关的节点链路记录的节点链路号的重新分配。因此认为在修正一个节点链路记录的节点链路号后，尽管在有关与对应于该节点链路记录的链路交叉的其它链路的节点链路记录中，不变更链路，但有必要改变交叉信息中的节点链路号。即，不仅只追加与新表示的道路直接相关联的信息，还有必要变更与其间接关联的大量信息。
不过，在该实施方式2中，不必进行对应道路未被变更的链路串的链路串记录更新。因此，应更新的信息量可以较少，由地图信息处理装置更新处理的操作量较少。在上述示例中，对应于道路0、1、6、7、8的链路串记录MR0S、MR1S、MR6S、MR7S、MR8S有必要进行显示系数据帧的道路数据帧中的更新处理。
如果地图信息处理装置a1能获取更新了的地图信息，则也可由该地图信息处理装置a1来进行有关最新的实际道路的地图显示、地图匹配及路径计算。作为用于由地图信息处理装置a1来获取更新了的地图信息的方法，在本实施方式中，也由地图信息提供装置a2向地图信息处理装置a1发送更新指示信息。地图信息处理装置a1根据更新指示信息来变更元地图信息后，可获取更新了的地图信息(即也可由各地图信息处理装置a1来更新地图信息)。
接下来，对地图信息处理装置a1更新地图信息的方法作以说明。与实施方式1同样，地图信息提供装置a2的更新指示信息存储装置11(参照图3)中，存储有具有图24所示结构的更新指示信息数据库。地图信息提供者将更新指示信息追加到更新指示信息数据库时，伴随着追加，在更新指示信息数据库的版数管理信息中进行必要的改变。
与实施方式1相同，更新指示信息数据库的各版别信息具有用于显示系数据帧的更新指示信息及用于路径计算系数据帧的更新指示信息。用于显示系数据帧的更新指示信息对地图信息处理装置a1的处理器6，将图10的旧版道路数据帧更新为图40的新版道路数据帧。用于显示系数据帧的更新指示信息如图44所示。另一方面，用于路径计算系数据帧的更新指示信息对地图信息处理装置a1的处理器6，将图13的旧版路径计算数据帧更新为图21的新版路径计算数据帧。用于路径计算系数据帧的更新指示信息具有图27(a)及图27(b)所示的结构。
参照图44，对用于将图10的旧版道路数据帧更新为图40的新版道路数据帧的显示系数据帧的更新用更新指示信息作以说明。该更新指示信息具有与用于实施方式1的图25的更新指示信息相同的数据结构。图中的更新操作记录组OPDS1是用于更新显示系数据帧中的道路数据标头的更新操作记录的集合。更新操作记录组OPDS2是用于将图10(a)的链路串记录MR0更新为图40的链路串记录MR0S的更新操作记录的集合。更新操作记录组OPDS3是用于将图10(a)的链路串记录MR1更新为图40的链路串记录MR1S的更新操作记录的集合。更新操作记录组OPDS4是用于追加图40的链路串记录MR6S、MR7S、MR8S的更新操作记录的集合。
用于将链路串记录MR0更新为链路串记录MR0S的更新操作记录组OPDS2指定按照表示无效的形式来改写对应于图38的链路串记录MR0内的元链路Ld3的节点链路记录NLR03的无效链路信息的操作，指定按照元链路Ld3的两端节点的连接目的地表示新链路串7两端的节点的形式来变更对应于元链路Ld3的两端节点的节点链路记录NL03、NL04的交叉信息的操作。即，更新操作记录组OPDS2具有用于将链路串记录MR0的节点链路记录NL03、NL04各自置换(改写)为节点链路记录NL03S、NL04S的二个链路串记录和用于将旧链路串标头置换为新链路串标头的链路串记录。这些链路串记录形式通过有关实施方式1的图26(b)的说明可由从业者予以理解。
同样，用于将链路串记录MR1更新为链路串记录MR1S的更新操作记录组OPDS3指定将对应于图38的链路串记录MR1内的链路Ld8的节点链路记录的无效链路信息变更为无效的操作，指定按照链路Ld8的两端节点的连接目的地表示链路串8两端的节点的形式来变更对应于链路Ld8的两端节点的节点链路记录的交叉信息的操作。
追加链路串记录MR6S、MR7S、MR8S的更新操作记录组OPDS4具有追加新链路串记录MR6S、MR7S、MR8S的更新操作记录、追加这些内容的更新操作记录。比如，包含追加表示代替链路Ld3’、Ld3”的节点链路记录NLR70S～NLR72S的指示的更新操作记录包含使对应节点链路记录NLR70S～NLR72S具有表示代替链路Ld3’、Ld3”在地图显示上有效的无效链路信息和表示代替链路Ld3’、Ld3”与元链路Ld3交叉的交叉信息的指示。
如上所述，在由串联连接的代替链路来置换元链路的更新中，不必进行对应道路不变更的链路串2～链路串5的链路串记录MR2～MR5的更新，对应于道路0、1、6、7、8的链路串记录MR0S、MR1S、MR6S、MR7S、MR8S有必要进行显示系数据帧的道路数据帧中的更新处理。因此，更新指示信息中，不需要用于更新有关链路串2～链路串5的链路串记录MR2～MR5的更新指示信息，不包含为此目的的更新操作记录。
此外，由于路径计算系数据帧的路径计算数据帧与实施方式1同样更新，因而用于路径计算系数据帧的更新指示信息可与实施方式1相同(参照图27(a)及图27(b))。
在实施方式2中同样，用于显示系数据帧的更新指示信息及用于路径计算系数据帧的更新指示信息与图28所示的实施方式1相同，根据来自地图信息处理装置a1的请求，被从地图信息提供装置a2单独地提供到地图信息处理装置a1。这样，将对于设置置换元链路的代替链路的更新，表示元链路无效的无效链路信息、用于追加具有代替链路的链路串的链路串记录MR7S及MR8S、包含用于连接该链路串与元链路的交叉信息的更新指示信息向地图信息处理装置提供。由于更新指示信息中不包含有关对应道路未变更的链路串的信息，因而可不增大更新指示信息，在更短的时间内发送更新指示信息。
实施方式2中的地图信息处理装置a1的处理器6的动作与参照图29所说明的实施方式1的地图信息处理装置a1的处理器6的动作几乎相同(但如后所述，步骤ST208的导航处理不同)。因此，根据用于在步骤ST203接收到的显示系数据帧的更新指示信息，处理器6对具有图10的旧版道路数据帧的显示系数据帧实施更新处理，在步骤ST205将包含作为其结果所获得的图40的最新版道路数据帧的显示系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。此外根据用于在步骤ST203接收到的路径计算系数据帧的更新指示信息，处理器6对具有图13的旧版路径计算数据帧的路径计算系数据帧实施更新处理，在步骤ST206将包合作为其结果所获得的图21的最新版路径计算数据帧的路径计算系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。
由于更新指示信息的更新操作记录指定了应更新的数据部分及其处理方式，因而通过进行基于上述更新操作记录的指示的更新操作，地图信息处理装置a1可进行地图信息的更新。由于更新指示信息中不包含有关对应道路未变更的链路串的信息，因而在地图信息处理装置a1中，也可缩短更新指示信息的接收时间，可减少更新处理量，更新处理的时间也可缩短。
接下来，参照图45，对基于实施方式2的导航处理(图29的步骤ST208)作以说明。图45的流程图具有在步骤ST306与步骤ST307之间追加的步骤ST400，这一点与图32的流程图不同。其它处理与实施方式1相同。
在步骤ST400，处理器6对在步骤ST306取出的节点链路记录的无效链路信息进行检查。如果无效链路信息表示无效，其动作便返回步骤ST305。这是因为该显示系链路由于无效而对路径显示不起作用。另一方面，如果无效链路信息表示有效，其动作便进入步骤ST307，判断在步骤ST304已取出的路径链路记录与在步骤ST306取出的节点链路记录是否关联。因此，由代替链路置换的元链路并非作为路径来显示，而与之相反，显示与代替链路对应的路径。
在该实施方式中同样，根据所需区域的更新指示信息的接收状态即获取状态，地图信息处理装置a1中，所需要区域的路径计算数据帧及显示系数据帧的更新状态相同或相异。即，存在以下4种状态。
在第1状态下，在地图信息处理装置a1中所需要区域的路径计算数据帧及显示系数据帧被共同更新。根据更新指示信息，比如图21所示的路径计算数据帧及图40所示的道路数据帧由地图信息处理装置a1来作成，被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，在步骤ST307采用的链路识别号的范围A、B共同成为更新后的范围。因此基于更新后的路径计算数据帧及显示系数据�。渎肪侗徽废允�。该显示结果如图37(b)所示。即，在变更后的道路显示上，最佳路径链路被重合显示。
在第2状态下，所需要区域的路径计算数据帧被更新，但显示系数据帧不更新。比如，图21所示的更新后的路径计算数据帧及图10所示的旧版道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A更新后，范围B成为更新前(旧版)的范围。不过，由于更新前的链路识别号的范围与更新后的链路识别号的范围的对应成为可能，因而基于更新后的路径计算数据帧及更新前的显示系数据帧，其路径被正确显示。该显示结果如图37(a)所示。即，在变更前的道路显示上，最佳路径链路被重合显示。
在第3状态下，所需要区域的路径计算数据帧不被更新，但显示系数据帧被更新。比如，图13所示的旧版路径计算数据帧及图40所示的更新后的道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A更新前，范围B成为更新后的范围。不过，由于更新前的链路识别号的范围与更新后的链路识别号的范围的对应成为可能，因而基于更新前的路径计算数据帧及更新后的显示系数据�。渎肪侗徽废允�。该显示结果如图37(b)所示。即，在变更后的道路显示上，最佳路径链路被重合显示。
在第4状态下，所需要区域的路径计算数据帧及显示系数据帧均不被更新。比如，图13所示的旧版路径计算数据帧及图10所示的旧版道路数据帧被寄存到更新指示信息存储装置5的地图信息寄存部。在该场合下，链路识别号范围A、B共同成为更新前的范围。因而基于旧版路径计算数据帧及旧版显示系数据�。渎肪侗徽废允�。该显示结果如图37(a)所示。即，在变更前的道路显示上，最佳路径链路被重合显示。
如上所述，根据本实施方式2，地图信息的数据结构中，地图显示用的道路数据部分(道路数据帧)的各节点链路记录具有表示对应于现实的道路部分的链路的链路识别信息、表示设置了置换元链路的代替链路的场合下，其元链路在地图显示上无效的无效链路信息、使由代替链路组成的链路串与元链路相对应的连接信息(交叉信息)，由此由地图信息处理装置(计算机、逻辑电路或其组合)，其元链路与代替链路的相关联成为可能(参照图38、图41及图42)。此外路径计算用的路径计算数据部分(路径计算数据帧)具有表示元链路的链路识别信息(对应链路识别信息)、用于表示代替链路的副链路识别信息(对应副链路识别信息)，对于各链路，链路识别信息与副链路识别信息相对应，由地图信息处理装置，其元链路与代替链路的相关联成为可能(参照图14、图22及图23)。因此，在旧版道路数据帧与新版路径计算数据帧混杂的场合下，可利用旧版道路数据帧的链路识别信息，来进行基于新版路径计算数据帧的路径显示。即，在变更前的道路显示上，最佳路径链路被重合显示。反之，在新版道路数据帧与旧版路径计算数据帧混杂的场合下，可忽视新版道路数据帧中的无效元链路的节点链路记录，利用有效的代替链路的节点链路记录的交叉信息，来进行基于旧版路径计算数据帧的路径显示。即，在变更后的道路显示上，最佳路径链路被重合显示。这样，即使在地图信息处理装置a1中只能获取单方的数据�。部上允菊返穆肪丁�
此外，如果利用本实施方式涉及的地图信息的数据结构，在伴随更新，将表示现有的道路部分的元链路分割为多个的场合下，可表示表示元链路的节点链路记录是无效的，另一方面，可追加表示代替链路串的链路串记录。因此，即使将元链路分割为多个，也不必在与元链路相关联的现有链路串记录内，插入新的节点链路记录，表示节点链路记录的节点链路号也不变更。因此，链路未变更的其它链路串的链路串记录中，也不必变更交叉信息中的节点链路号。因此，应更新的信息量可以较少，由地图信息处理装置更新处理的操作量较少。因此，在地图信息处理装置a1中，也可缩短更新指示信息的接收时间，可减少更新处理量，更新处理的时间也可缩短。
此外，用于道路数据帧的更新的更新指示信息的数据结构中，包含使地图信息处理装置(计算机、逻辑电路或其组合)变更表示元链路Ld3的节点链路记录NLR03S(图41)的指示的更新操作记录OPDS2包含为表示元链路Ld3在地图显示上无效而改写无效链路信息的指示、为使元链路Ld3与代替链路交叉而改写交叉信息的指示，包含追加表示代替链路Ld3’、Ld3”的节点链路记录NLR70S～NLR72S的指示的更新操作记录OPDS4包含表示代替链路Ld3’、Ld3”在地图显示上有效的无效链路信息、为使对应节点链路记录NLR70S～NLR72S具有表示代替链路Ld3’、Ld3”与元链路Ld3交叉的交叉信息而进行的指示。因此，接收了更新指示信息的地图信息处理装置a1中，处理器6可根据更新操作记录的指定来自动更新上述地图信息的道路数据帧中的该记录。
在该实施方式下，在更新指示信息的数据结构中，各更新操作记录将更新对象类别及更新对象位置指定到地图信息处理装置(计算机、逻辑电路或其组合)，因而可只将更新所必需的更新数据(链路串标头、节点链路记录、节点记录或连接记录)提供到地图信息处理装置a1来更新。即可缩小更新指示信息的长度。
此外虽然未图示，但在作为导航处理来进行采用了道路数据帧的地图匹配等其它处理的场合下，地图信息处理装置也可以不将对应于无效链路信息表示无效的节点链路记录的显示系链路作为处理对象。这样，可进行正确的地图匹配等处理。
实施方式3接下来，对本发明的实施方式3作以说明。实施方式3是可用于上述实施方式1、2的任意一种的修正方式，涉及从地图信息提供装置a2发送到地图信息处理装置a1，用于使地图信息处理装置a1进行更新处理的更新指示信息。因此，图1至图3所示的地图信息处理装置a1及地图信息提供装置a2也用于实施方式3，实施方式3中的地图信息处理装置a1及地图信息提供装置a2的各构成要素的功能与实施方式1或实施方式2中的功能基本相同。此外地图信息处理装置a1中使用的地图信息(图4)的内容也与实施方式1或实施方式2中的地图信息内容基本相同。
对该实施方式，也结合图5至图9所示地图的显示作以说明。即，假设图10所示的道路数据帧及图13所示的路径计算数据帧被包括到寄存于地图信息处理装置a1的地图信息存储装置4的旧版地图信息的显示系数据帧及路径计算系数据�。桓碌牡赝夹畔⒕弑竿�18(实施方式1)或图40(实施方式2)所示的新版道路数据帧及图21所示的新版路径计算数据帧。
接下来，对地图信息处理装置a1更新地图信息的方法作以说明。与实施方式1或实施方式2同样，在地图信息提供装置a2的更新指示信息存储装置11(参照图3)中，存储具有图24所示结构的更新指示信息数据库。在地图信息提供者将更新指示信息追加到更新指示信息数据库时，伴随着追加，在更新指示信息数据库的判别信息中进行必要的改变。
与实施方式1或实施方式2同样，更新指示信息数据库的各版别信息具有用于显示系数据帧的更新指示信息及用于路径计算系数据帧的更新指示信息。用于显示系数据帧的更新指示信息使地图信息处理装置a1的处理器6将图10的旧版道路数据帧更新为图18或图40的新版道路数据帧。另一方面，用于路径计算系数据帧的更新指示信息使地图信息处理装置a1的处理器6将图13的旧版路径计算数据帧更新为图21的新版路径计算数据帧。
图46表示基于实施方式3的更新指示信息存储装置11中寄存的更新指示信息的结构。与图25所示的更新指示信息不同，图46的更新指示信息是一种用于在地图信息处理装置a1中，通过由更新信息标头指定的种类及版本的数据帧来置换(改写)旧版的同种数据帧的信息。与实施方式1同样，更新指示信息标头具有指定管理信息帧、显示系数据帧、路径计算系数据帧等应更新的数据帧的种类区分(参照图4)的更新数据区分指定及表示更新的数据帧的相应区域的区域指定(地域指定)。各更新操作记录包含更新了的数据帧本身，或包含分割了已更新的数据帧本身的数据部分。更新了的数据帧或数据部分可被压缩。
接收了更新指示信息的地图信息处理装置a1的处理器6对更新指示信息的更新指示信息标头进行分析，由接收的数据帧来置换由更新信息标头指定的种类及版本的数据帧。在所收发的数据帧被分割或压缩的场合下，从更新操作记录的内容来使更新了的数据帧复原，由复原了的数据帧来置换由更新信息标头指定的种类及版本的数据帧。
在实施方式3中同样，用于显示系数据帧的更新指示信息及用于路径计算系数据帧的更新指示信息与图28所示的实施方式1或实施方式2同样，根据来自地图信息处理装置a1的请求，被从地图信息提供装置a2单独提供到地图信息处理装置a1。
但在步骤ST102中，从更新指示信息存储装置11的更新指示信息数据库中寄存的版别信息来获取更新指示信息，在步骤ST103将在步骤ST102中获取的更新指示信息向请求了的地图信息处理装置a1发送。比如，在从具有存储了图10(a)的道路数据帧及图13的路径计算数据帧的地图信息存储装置4的地图信息处理装置a1请求了显示系数据帧及路径计算系数据帧的更新指示信息时，发送分别包括包含图18或图40的道路数据帧的显示系数据帧及包含图21的路径计算数据帧的路径计算系数据帧的更新指示信息。
图47是表示基于实施方式3的地图信息处理装置a1的处理器6的动作的流程图。图47的流程图与图29的流程图的不同之处在于其将图29的流程图的步骤ST204～207置换为步骤ST500、ST501。其它处理与实施方式1相同。以下与实施方式1同样，假设地图信息处理装置a1保持包含图10(a)的道路数据帧的显示系数据帧及包含图13的路径计算数据帧的路径计算系数据�。赝夹畔⑻峁┳爸胊2保持包含图18的道路数据帧的显示系数据帧及包含图21的路径计算数据帧的路径计算系数据�。缘赝夹畔⒋碜爸玫亩髯饕运得�。
在步骤ST203，处理器6通过收发装置3来接收包含图18的道路数据帧的显示系数据帧及包含图21的路径计算数据帧的路径计算系数据帧的更新指示信息。处理器6将由收发装置3接收的更新指示信息寄存到更新指示信息存储装置5的更新指示信息寄存部。因此，在设置了代替链路的地图信息更新中，如同图19的链路串记录MR0’的节点链路记录NLR03’、NLR04I，可获取表示具有元链路的链路识别信息及附加到代替链路的副链路识别信息的代替链路的节点链路记录的数据帧。
在上述更新指示信息的接收中，在获取了更新指示信息的场合下，处理器6在将该更新指示信息寄存到更新指示信息存储装置5内的更新指示信息寄存部(参照图30)的同时，将为表示其寄存位置、数据长、已获取了获取状态而设定的更新指示信息管理记录寄存到更新指示信息管理数据。另一方面，在由于通信障碍等而未获取更新指示信息的场合下，处理器6在将与请求了的更新指示信息的更新指示信息标头相当的数据作为更新指示信息来寄存到更新指示信息寄存部的同时，将为表示其寄存位置、数据长、未获取获取状态而设定的更新指示信息管理记录寄存到更新指示信息管理数据。
在步骤ST500，处理器6取出(读出)显示系数据帧。具体地说，首先处理器6从更新指示信息存储装置5内的更新指示信息寄存部检查有关所需要区域(地域)的显示系数据帧的更新指示信息的更新指示信息管理记录内的获取状态。如果有关在步骤ST202决定的区域的显示系数据帧的更新指示信息的获取状态表示获取结束，则处理器6将该更新指示信息中包含的更新结束的显示系数据帧从更新指示信息存储装置5的更新指示信息寄存部取出，寄存到更新指示信息存储装置5的地图信息寄存部(图31)。另一方面，如果更新指示信息管理记录内的获取状态表示未获�。虼砥�6从地图信息存储装置4取出在步骤ST202中决定的区域的显示系数据�。拇娴礁轮甘拘畔⒋娲⒆爸�5的地图信息寄存部。因此，接收了显示系数据帧的更新指示信息的地图信息处理装置a1可根据更新指示信息来更新显示系数据帧。
在步骤ST501，处理器6取出(读出)路径计算系数据帧。具体地说，首先处理器6从更新指示信息存储装置5内的更新指示信息寄存部检查有关所需要区域(地域)的路径计算系数据帧的更新指示信息的更新指示信息管理记录内的获取状态。如果有关在步骤ST202决定的区域的路径计算系数据帧的更新指示信息的获取状态表示获取结束，则处理器6将该更新指示信息中包含的更新结束的路径计算系数据帧从更新指示信息存储装置5的更新指示信息寄存部取出，寄存到更新指示信息存储装置5的地图信息寄存部(图31)。另一方面，如果更新指示信息管理记录内的获取状态表示未获�。虼砥�6从地图信息存储装置4取出在步骤ST202中决定的区域的路径计算系数据�。拇娴礁轮甘拘畔⒋娲⒆爸�5的地图信息寄存部。因此，接收了路径计算系数据帧的更新指示信息的地图信息处理装置a1可根据更新指示信息来更新路径计算系数据帧。
根据本实施方式3，通过上述动作，地图信息处理装置a1可自动地，而且不进行更新对象位置等的判断地简单地更新地图信息。此外通过采用了实施方式1或实施方式2的地图信息的数据结构，即使在地图信息处理装置a1中，版本各异的道路数据帧与路径计算系数据混杂，也可正确显示包含代替链路的路径。
实施方式4接下来，对本发明的实施方式4作以说明。实施方式4是可用于上述实施方式或实施方式2的任意一种的修正方式，这里，地图信息处理装置a1自身检测出道路的新设，基于该新设道路来作成用于使地图信息处理装置a1进行更新处理的更新指示信息。图1至图3所示的地图信息处理装置a1及地图信息提供装置a2也用于实施方式4，实施方式4中的地图信息处理装置a1及地图信息提供装置a2的各构成要素的功能与实施方式1或实施方式2中的功能基本相同。此外地图信息处理装置a1中使用的地图信息(图4)的内容也与实施方式1或实施方式2中的地图信息内容基本相同。此外，用于显示系数据帧的更新指示信息及用于路径计算系数据帧的更新指示信息如图28所示，与实施方式1或实施方式2同样，根据来自地图信息处理装置a1的请求，被从地图信息提供装置a2单独提供到地图信息处理装置a1。
但在该实施方式4中，地图信息处理装置a1的更新指示信息存储装置5中设有寄存表示车辆即地图信息处理装置a1行走的位置的时间推移的行走轨迹信息的行走轨迹寄存部、更新指示信息暂时寄存部。除了这些行走轨迹寄存部及更新指示信息暂时寄存部，更新指示信息存储装置5中还如上所述设有更新指示信息寄存部及地图信息寄存部。
图48是表示基于实施方式4的地图信息处理装置a1中处理器6的动作的流程图。图48的流程图与图29的流程图的不同点在于在图29的流程图中还附加了步骤ST600、ST617～ST621。在步骤ST203接收更新指示信息，寄存到更新指示信息存储装置5后，其动作转入步骤ST600的内部更新指示信息获取子程序。
图49是表示内部更新指示信息获取子程序的详细动作的流程图。在步骤ST610，将在步骤ST201获取的该车辆的当前位置寄存到更新指示信息存储装置5的行走轨迹寄存部。
在步骤ST611，处理器6判断是否检测出了新设道路。具体地说，对更新指示信息存储装置5的行走轨迹寄存部所示的该车辆的行走轨迹与地图信息存储装置4中寄存的道路数据帧中寄存的各链路的内插点信息进行比较，在行走轨迹所示的道路形状与道路数据帧中寄存的链路的内插点信息所示的道路形状的任意一点不一致的场合下，意味着检测出了新设道路。更具体地说，在从道路数据帧中寄存的链路上的某个位置出发，到达另一链路上的某个位置时检测出了新设道路后，其动作进入步骤ST612，在与之相反之时结束内部更新指示信息获取子程序。比如，在该车辆从图8的链路Ld3的中间位置到达链路Ld8的中间位置时，将图15的道路6作为新设道路检测出来。
在步骤ST613，生成用于将在步骤ST612检测出的新设道路追加到道路数据帧、路径计算数据帧的更新指示信息，将所生成的用于道路数据帧的更新指示信息寄存到更新指示信息存储装置5的更新指示信息寄存部，将所生成的用于路径计算数据帧的更新指示信息暂时寄存到更新指示信息存储装置5的更新指示信息暂时寄存部。此时生成的更新指示信息的数据结构与从地图信息提供装置发送的更新指示信息的数据结构相同。比如如上所述，在将图15的道路6作为新设道路检测出的场合下，处理器6生成用于将图8的道路网更新为图39的道路网的与图44所示同样的更新指示信息，寄存到更新指示信息存储装置5的更新指示信息寄存部。此外生成用于将图9的道路网更新为图17的道路网的与图27所示同样的更新指示信息，暂时寄存到更新指示信息存储装置5的更新指示信息暂时寄存部。
此外在步骤ST613，为重新准备新设道路的检测，删除更新指示信息存储装置5的行走轨迹寄存部中寄存的行走轨迹，然后结束内部更新指示信息获取子程序。
结束了步骤ST600的内部更新指示信息获取子程序后，处理器6根据用于更新指示信息存储装置5的更新指示信息寄存部中寄存的道路数据帧(显示系数据帧)的更新指示信息对从地图信息存储装置4读出的显示系数据帧进行更新，将更新了的显示系数据帧寄存到更新指示信息存储装置5的地图信息寄存部(步骤ST204、ST205)。因此，如果通过内部更新指示信息获取子程序检测出新设道路，则显示系数据帧基于由地图信息处理装置a1自身生成的更新指示信息被更新。否则，显示系数据帧基于从地图信息提供装置a2提供的更新指示信息被更新。
此外，在步骤ST206、ST207，处理器6根据用于更新指示信息存储装置5的更新指示信息寄存部中寄存的路径计算系数据帧的更新指示信息对从地图信息存储装置4读出的路径计算系数据帧进行更新，将更新了的路径计算系数据帧寄存到更新指示信息存储装置5的地图信息寄存部。因此，不论是否通过内部更新指示信息获取子程序检测出了新设道路，路径计算系数据帧均基于从地图信息提供装置a2提供的更新指示信息被更新。
这样，在步骤ST208的导航处理子程序，在输出装置7的显示画面的地图显示上进行路径显示。如果通过内部更新指示信息获取子程序检测出新设道路，则地图显示表示由地图信息处理装置a1自身检测出的新设道路。在该场合下，路径计算系数据帧不反映地图信息处理装置a1自身的检测，但即使显示系数据帧与路径计算系数据帧的版本各异，也可进行地图显示及路径显示，这一点同上所述。
该地图信息处理装置a1的操作者可观察该地图显示，对新设道路与自己记忆中的该车辆的行走轨迹进行比较。步骤ST208的导航处理结束后，在更新指示信息存储装置5的更新指示信息暂时寄存部中剩余内部获取的路径计算数据帧的场合下(步骤ST617)，在步骤ST618，处理器6利用输出装置7询问操作者所显示的新设道路是否正确，接下来在步骤ST619，为操作者确认新设道路而待机一定期间。操作者在此期间可将回答输入到输入装置1。只在操作者回答了新设道路正确的场合下，输入装置1将旨在进行路径计算数据帧的更新的指示提供到处理器6。
接下来，在步骤ST620，处理器6判断是否由输入装置1发出了是否进行基于该地图信息处理装置a1的操作者的路径计算数据帧的更新的指示。在进行路径计算数据帧的更新的场合下，其动作进入步骤ST621，在不进行的场合下，返回步骤ST200。
在步骤ST621，对内部获取的路径计算数据帧进行更新。具体地说，将用于更新指示信息存储装置5的更新指示信息暂时寄存部中暂时寄存的路径计算数据帧的更新指示信息寄存到更新指示信息存储装置5的更新指示信息寄存部。这样，路径计算系数据帧基于由新设道路而引起，由地图信息处理装置a1自身生成的更新指示信息被更新，同版的显示系数据帧及路径计算系帧被寄存到更新指示信息寄存部。
如上所述，在实施方式4中，可不由地图信息提供装置a2，而只由地图信息处理装置a1来生成更新指示信息，对道路数据帧及路径计算数据帧进行更新。此外通过采用与实施方式1或实施方式2同样的地图信息的数据结构，即使在基于由地图信息处理装置a1生成的更新指示信息，只更新了道路数据帧的场合下，也可正确显示包含代替链路的路径。此外通过采用实施方式1或实施方式2的更新指示信息的数据结构，地图信息处理装置a1可根据更新操作记录的指定来自动更新该记录。
此外在本实施方式中同样，如果采用与实施方式2同样的地图信息的数据结构，如上所述，即使对应道路不变更的其它链路串的链路串记录中，也无需变更交叉信息中的节点链路号，因而应更新的信息量可以较少，即使是信息处理能力低的地图信息处理装置a1中，也可作成更新指示信息。此外信息处理能力低的地图信息处理装置a1中，可以不增大更新处理，在更短的时间进行道路数据帧的更新。
此外在实施方式1～4涉及的说明中，所表示的是用二个代替链路来置换一个元链路的场合，但也可以用三个以上的代替链路来置换一个元链路。
在实施方式1～4涉及的说明中，所表达的是由代替链路串表示的道路形状与由元链路表示的道路形状相一致的场合，但代替链路的道路形状与元链路的道路形状也可以不一致。比如在现实中，在新建道路时，与新建道路交叉的道路部分的形状有时发生变更。在这种场合下，代替链路的两端或一端的节点的坐标及内插点的坐标被变更，但由包含改写坐标信息的指示的更新指示信息，地图信息处理装置a1可更新地图信息。
此外在实施方式1～4中，每当获取当前位置信息，地图信息处理装置a1便将更新指示信息请求发送到地图信息提供装置a2，但本发明并非限定于本实施方式，更新指示信息请求的发送定时也可根据用途任意选择。比如，地图信息处理装置a1也可以在事前询问地图信息提供装置a2是否有更新了的数据，只在有更新必要的场合，地图信息处理装置a1将更新指示信息请求发送到地图信息提供装置a2。
此外，在实施方式1～4中，地图信息处理装置a1将更新了的地图信息寄存到更新指示信息存储装置5，但也可将更新了的地图信息寄存(即改写保存)到地图信息存储装置4。
此外，在实施方式1～4中，为从地图信息提供装置a2获取更新指示信息而采用了通信单元，但更新指示信息的分布并非限定于通信，比如也可以采用存储卡或存储盘之类的移动式存储媒体。
此外上述实施方式下的地图信息处理装置a1是搭载于汽车上的车用导航装置，但本发明并非限定于实施方式，地图信息处理装置a1也可以设置到便携电话、便携信息终端等移动体。或者地图信息处理装置a1也可以是固定的计算机终端。在这些代替方式中，位置检测装置2被设置于地图信息处理装置a1是移动体的场合，但在固定终端的场合下则不需要。
此外本发明涉及的数据结构也可以用于不同于上述形式的地图信息。比如，可以用于只记述主要道路的地图显示用数据帧和除了主要道路还记述了二次道路的比例尺各异的地图显示用数据帧被分层化了的地图信息。在该地图信息中，在这种用途各异的地图显示用数据帧之一被更新，而其它的不更新的场合下，有可能发生由更新了的地图显示用数据帧来显示新的主要道路，不由旧版的地图显示用数据帧来显示该主要道路的事态。然而，通过由本发明来进行元链路与代替链路的关联，可消除基于新版与旧版的差异的显示的不统一。
如上所述，根据本发明，地图信息的数据结构具备有链路识别信息，其表示与现实的道路部分分别对应的各元链路；副链路识别信息，其用于表示为置换任意元链路而设置的二个以上的代替链路，对各链路其链路识别信息与副链路识别信息相对应，由地图信息处理装置可使元链路与代替链路相关联。因此，即使更新了的数据与更新失败的数据混杂，在地图信息处理装置中代替链路与元链路也可对应，因而可实现适当的处理。
根据本发明，地图信息的数据结构具备有多个节点链路信息，其分别表示与现实的道路网的道路部分对应的各链路，各节点链路信息具有链路识别信息，其表示与现实的道路部分对应的链路；无效链路信息，其表示在设置置换元链路的二个以上的代替链路的场合下其元链路无效；连接信息，其使由上述代替链路组成的链路串与上述元链路相对应，这样由地图信息处理装置可使元链路与代替链路相关联。因此，即使更新了的数据与更新失败的数据混杂，在地图信息处理装置中代替链路与元链路也可对应，因而可实现适当的处理。
权利要求
1.一种地图信息的数据结构，包括链路识别信息，其表示与现实的道路部分分别对应的各元链路；副链路识别信息，其用于表示为置换任意元链路而设置的二个以上的代替链路，关于各链路，链路识别信息与副链路识别信息相对应，可以由地图信息处理装置使元链路与代替链路相关联。
2.一种地图信息的数据结构，其特征在于包括地图信息处理装置所处理的用途各异的多个数据部分，上述数据部分各自具有权利要求1中记载的数据结构。
3.一种规定了用于使地图信息处理装置对具有权利要求1中记载的数据结构的现有地图信息进行更新的指示的更新指示信息的数据结构，包括更新操作信息，其使地图信息处理装置将与为置换元链路而设置的代替链路相关联的信息部分追加到上述地图信息，用于各代替链路的各更新操作信息具有表示元链路的链路识别信息和表示该代替链路自身的副链路识别信息。
4.一种地图信息处理装置，包括寄存部，其寄存具有权利要求1中记载的数据结构的地图信息；接收部，其接收规定了用于使地图信息处理装置更新上述地图信息的指示的、具有权利要求3中记载的数据结构的更新指示信息；更新处理部，其根据上述更新指示信息来更新上述地图信息。
5.一种地图信息的数据结构，包括多个节点链路信息，其分别表示与现实道路网的道路部分对应的各链路，各节点链路信息具有链路识别信息，其表示与现实的道路部分对应的链路；无效链路信息，其表示在设置置换元链路的二个以上的代替链路的场合下其元链路无效；连接信息，其使由上述代替链路组成的链路串与上述元链路相对应，这样，可以由地图信息处理装置使元链路与代替链路相关联。
6.一种规定了用于使地图信息处理装置对具有权利要求5中记载的数据结构的现有地图信息进行更新的指示的更新指示信息的数据结构，包括第1更新操作信息，其包含使地图信息处理装置变更表示元链路的节点链路信息的指示；第2更新操作信息，其包含使地图信息处理装置将表示为置换元链路而设置的代替链路的节点链路信息追加到上述地图信息的指示，上述第1更新操作信息包含为表示上述元链路无效而改写无效链路信息的指示；为使上述元链路与上述代替链路对应而改写连接信息的指示，上述第2更新操作信息包含使对应节点链路信息具有表示上述代替链路有效的无效链路信息和表示上述代替链路与上述元链路相对应的连接信息的指示。
7.一种地图信息处理装置，包括寄存部，其寄存具有权利要求5中记载的数据结构的地图信息；接收部，其接收规定了用于使地图信息处理装置更新上述地图信息的指示的、具有权利要求6中记载的数据结构的更新指示信息；更新处理部，其根据上述更新指示信息来更新上述地图信息。
8.一种地图信息提供装置，包括更新指示信息存储部，其寄存有规定了用于使地图信息处理装置更新地图信息的指示的、具有权利要求3或权利要求6中记载的数据结构的更新指示信息；发送部，其将上述更新指示信息发送到地图信息处理装置。
全文摘要
即使更新了的数据与未更新数据并存，也可实现适当的处理。为此，表示地图显示用的道路数据帧链路的各节点链路记录包括表示道路变更前的元链路的链路识别信息、用于表示道路变更后的代替链路的副链路识别信息。表示路径计算用的路径计算数据帧的节点连接关系的连接记录也包括表示元链路的对应链路识别信息、用于表示代替链路的对应副链路识别信息。根据元链路和副链路的识别信息，即使版本各异的道路数据帧及路径计算数据帧也可实现链路的对应。
文档编号G01C21/00GK1499399SQ20031011385
公开日2004年5月26日 申请日期2003年10月31日 优先权日2002年11月1日
发明者御厨诚, 下谷光生, 生, 春, 梅津正春, 哉, 池内智哉 申请人:三菱电机株式会社
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
