CN1590962A

CN1590962A - 地图数据结构、存储媒体和更新方法及地图信息处理装置

Info

Publication number: CN1590962A
Application number: CNA2004100685448A
Authority: CN
Inventors: 御厨诚; 梅津正春; 池内智哉; 下谷光生; 大木秀彦
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2003-08-26
Filing date: 2004-08-26
Publication date: 2005-03-09
Anticipated expiration: 2024-08-26
Also published as: US20050058155A1; JP4543637B2; JP2005070482A; US7526492B2; DE102004041342A1; CN100595517C

Abstract

本发明的目的是使地图数据更新容易。该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，其中对将所述道路网的道路连接作为所述链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开，另行设置所述道路网各节点的节点数据，授予所述道路网各节点识别节点用的节点标识符，并且所述链路数据具有示出根据链路串方向决定的链路端一个节点的节点标识符的信息。

Description

地图数据结构、存储媒体和更新方法及地图信息处理装置

技术领域

本发明涉及汽车向导装置、便携电话、便携信息终端等移动设备或固定计算机终端中使用的地图数据的数据结构、存储媒体和更新方法以及地图信息处理装置。

背景技术

汽车向导装置、便携电话、便携信息终端等移动设备或固定计算机终端中使用的已有地图数据，用表示道路上的地点的节点、表示所述地点间的道路的链路、将道路连接表示为链路连接的链路串表示道路网，在表示链路串的链路串数据中存放有关链路串包含的节点、链路的信息，并且利用链路串数据中存放的表示链路串间的相同性的相同节点信息表示道路网各链路的连接关系(参考例如专利文献1、非专利文献2)。

为了表示节点中链路之间的通行规则，已有的地图数据用基于相同节点信息的节点循环顺序规定对节点的进入链路、脱离链路(参考例如非专利文献1)。

为了分层道路网间与链路的相对应、与路径计算用等别的用途中所设的道路网之间与链路的相对应，已有的地图数据授予构成最下层道路网的各链路在全国唯一的链路号，使该号在链路串内连续。又，授予链路规定范围的链路号，即使划分链路时，也通过授给规定范围内的链路号，保持链路串内的链路号连续性(参考例如非专利文献1、专利文献2)。

为了使进行交叉点上的路径引导的路径引导数据与节点关联，已有的地图数据在链路串内的节点设有表示路径引导数据的存放位置的信息(参考例如非专利文献1)。

【专利文献1】

日本专利公开平8-292716号公报

【专利文献2】

日本专利公开2002-175593号公报

【非专利文献1】

“Kiwi Format Ver.1.22 7.2节道路数据帧”，Kiwi-W社

2003年7月23日检索

因特网<URL：http//kiwi-w.mapmaster.co.jp>

然而，专利文献1、非专利文献1所记载的已有地图数据，在表示链路串的链路串数据中混杂存放表示链路串包含的节点的节点数据和表示链路的链路数据。

因此，在多个链路串中包含多个链路串交叉的节点的节点数据，重复存放相同内容的节点数据，因而节点数据更新时，必须更新多个链路串的节点数据，存在更新处理烦杂的问题。

在专利文献1、非专利文献1所记载的已有地图数据中，已知利用设在链路串的各节点的相同节点信息示出与链路串的节点相同的其它链路串的节点，按照相同节点信息的指示从某节点依次查找其它链路串的节点，将返回第1节点前出现的节点都作为相同的，并且对连接这些节点上连接的各链路串的链路之间主连接。

因此，新设链路串X时，在指示链路串X的某相同节点信息示出的已有链路串Y的节点B的情况下，从节点B的相同节点信息出发，依次查找相同节点信息示出的其它已有链路串的节点，找出指示已有链路串Y的节点B的链路串Z的节点C，必须将链路串Z的节点C的相同节点信息改变成指示链路串X的节点A，存在新设链路串时需要烦杂的更新信息处理的问题。

非专利文献1所记载的已有地图数据中，利用相同节点信息查找节点的进入链路、脱离链路时，所述节点用出现的顺序表示。由于所述顺序因按相同节点信息进行查找中出现的链路串废弃、新设而变化，已有的表示从进入链路到脱离链路的通行规则的信息必须改变，存在更新处理烦杂的问题。

又，专利文献1、非专利文献1所记载的已有地图数据中，划分链路时，其后连接的节点的链路串内节点号、存放位置变化，因而必须改变在所述节点交叉的其它已有链路串的相同节点信息，存在更新处理烦杂的问题。

又，专利文献2所记载的已有地图数据中，作为链路标识符，授予链路与其链路长度成正比的范围的链路号，因而链路长度长的山间道路、高速道路的链路号范围较大，链路长度短的街市地带的链路号范围较小，对已有道路进行扩宽和新设交叉道路的频度高的街市地带中，划分链路的频度高，产生不能尽量按所需次数划分链路的情况。这种情况下，授给能划分的链路新链路号，从而也需要对包含这些链路的上层链路以及路径计算用的道路网的链路提供新链路号，存在更新处理烦杂的问题。

又，非专利文献1所记载的已有地图数据中，作为节点关联信息，设有指示交叉点上的引导信息的路径引导数据，并在链路串数据内设有对链路串内的各节点示出引导数据的存放位置的地址信息，因而由于废弃或新设路径引导数据而已有的引导数据存放位置变化，必须改变已有的示出链路串数据的引导数据的存放位置的地址信息，存在更新处理烦杂的问题。

本发明是为消除上述问题而完成的，其目的是使地图数据的更新容易。

发明内容

本发明的地图数据的数据结构如下，即该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，其中对将所述道路网的道路连接作为所述链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点识别节点用的节点标识符，并且所述链路数据具有示出根据链路串方向决定的链路端一个节点的节点标识符的信息。

又，分别授予各链路固有范围链路号，将授予划分前链路的所述范围链路号分配给划分后的链路，并根据等分所述划分前链路的链路号的范围所得的范围，决定所述分配获得的划分后链路的链路号范围。

又，分别授予各链路固有范围链路号的地图数据中，将授予划分前链路的所述范围链路号分配给划分后的链路，并根据所述划分前链路的链路长度与所述划分后链路的链路长度的比，决定所述分配获得的划分后链路的链路号范围。

根据本发明，将地图数据做成由链路串数据和与链路串数据分开设置的各节点的节点数据组成的数据结构，并且所述链路串的链路数据具有根据链路串的方向决定的链路端的一个节点的节点标识符，因而不必重复存放节点数据，具有能容易更新地图数据的效果。

附图说明

图1是示出本发明实施方式1的地图信息处理装置的组成的框图。

图2是示出本发明实施方式1的地图信息概略数据结构的图，

图3是示出本发明实施方式1的道路网例的图。

图4是示出一例本发明实施方式1的道路网数据的数据结构的图。

图5是示出一例本发明实施方式1的节点表、节点附加列表的数据结构的图。

图6是示出一例本发明实施方式1的链路串表、链路串附加列表的数据结构的图。

图7是示出一例本发明实施方式1的链路串记录的数据结构的图。

图8是示出一例本发明实施方式1的链路串附加记录的数据结构的图。

图9是示出本发明实施方式1的链路串记录存放例的图。

图10是示出本发明实施方式1的链路串0的链路串附加记录#0的存放例的图。

图11是示出一例本发明实施方式1的节点记录的数据结构的图。

图12是示出一例本发明实施方式1的节点添加记录的数据结构的图。

图13是示出本发明实施方式1的节点记录存放例的图。

图14是示出本发明实施方式1的节点添加记录存放例的图。

图15是示出一例本发明实施方式1的路径引导数据的数据结构的图。

图16是示出本发明实施方式1的路径引导数据存放例的图。

图17是示出本发明实施方式1中更新道路网后得到的道路网的图。

图18是示出本发明实施方式1中更新后得到的节点表、节点附加列表的存放例的图。

图19是示出本发明实施方式1中更新后得到的链路串表、链路串附加列表的例子的图。

图20是示出本发明实施方式1中链路串表的链路串记录存放例的图。

图21是示出本发明实施方式1中更新后得到的链路串0的链路串附加记录#0的链路串附加首部、链路表的存放例的图。

图22是示出本发明实施方式1中节点表的各节点记录存放例的图。

图23是示出本发明实施方式1中更新后得到的节点添加记录存放例的图。

图24是示出本发明实施方式1中划分后得到的链路串5的链路串附加记录#5的存放例的图。

图25是示出本发明实施方式1中划分链路时授给链路号的例子的图。

图26是示出本发明实施方式1更新后得到的路径引导数据例的图。

图27是示出本发明实施方式1更新用DVD-ROM存储的地图更新信息的概略数据结构的图。

图28是示出一例本发明实施方式1的更新记录的数据结构的图。

图29是示出本发明实施方式1的道路网更新数据存放例的图。

图30是示出本发明实施方式1的路径引导更新数据存放例的图。

图31是示出本发明实施方式1的地图信息处理装置的运作的流程图。

图32是示出本发明实施方式1的处理器5的存储器分配的图。

图33是示出本发明实施方式1中路径计算数据表示的道路网的例子的图。

图34是示出一例本发明实施方式1的路径数据的图。

图35是示出本发明实施方式1中路径计算数据获取、更新的详细流程图。

图36是示出本发明实施方式1中地图数据获取、更新的详细流程图。

图37是示出本发明实施方式1中道路网数据更新的详细流程图。

图38是示出本发明实施方式1中路径显示的详细流程图。

图39是示出本发明实施方式2中授予划分后的链路链路号的例子的图。

图40是示出本发明实施方式2中由划分后得到的链路组成的链路串的链路附加列表存放例的图。

附图中，1是输入装置，2是位置检测装置，3是地图信息存储装置，4是更新信息获取部，5是处理器，6是输出装置，10是运作控制数据部，11是行驶轨迹数据部，12是当前位置数据部，13是路径数据部，14是所需路径计算数据管理部，15是路径计算数据部，16是路径计算更新数据部，17是所需地图数据管理部，18是地图数据部，19是地图更新数据部。

最佳实施方式

下面说明本发明的实施方式。

实施方式1

图1中，输入装置1按照使用者的操作或指示将指示信号供给处理器5。具体而言，虽然图中未示出，但输入装置1可具有识别使用者的声音并根据声音输出指示信号的声音识别装置、由使用者手动存操作输出指示信号的按键以及其它适当输入装置中的至少一种装置。

位置检测装置2用例如GPS(Global Positioning System：全球定位系统)接收机、车速传感器、角速度传感器检测出装载该地图信息处理装置的车辆的当前位置，并将检测到的位置信息供给处理器5。

作为读取地图数据的地图数据读取手段、获取地图数据的地图数据获取手段和获取地图更新数据的地图更新数据获取手段的地图信息存储装置3由例如将硬盘运作存储媒体的硬盘驱动器组成，预期存放地图数据，并存放由更新信息获取装置4取得的地图更新数据。

更新信息获取装置4由例如DVD(Digital Versatile Disk：数字多功能光盘)驱动器组成，读取更新用DVD-ROM(Read Only Memory：只读存储器)存放的地图更新信息，并且获得地图更新信息。

作为地图数据更新手段的处理器5用从位置检测装置2获得的当前位置和从地图信息存储装置3读出的地图信息，进行各种地图信息处理。

作为地图信息处理，包含根据从位置检测装置2获得的位置信息和地图数据估计车辆当前位置的地图核对、算出出发处至目的地的路径的路径计算(路径搜索)、将计算结果所得的候补较佳路径连同道路地图显示在显示装置屏幕上的路径显示、按照较佳路径进行出发处至目的地的向导的路径引导以及当前位置周边的地图的显示处理等。

利用更新信息获取装置4将从DVD-ROM读取的地图更新信息预先存放于地图信息存储装置3，并且在上述地图信息处理时从地图信息存储装置3读取地图信息和地图更新信息，用地图更新信息更新地图信息。

输出装置6按照处理器5的地图信息处理输出，给使用者提示信息。具体而言，虽然未示出，但输出装置6具有显示地图、当前位置、路径、引导信息等的显示装置、以及用声音对使用者指示或引导的声音发生装置即可。

下面说明本发明实施方式1的地图数据的数据结构。

图2示出地图信息存储装置3中存放的地图信息的概略数据结构。作为地图信息，具有地图管理信息、1个以上的地图数据、1个以上的路径计算数据。

地图数据按道路网的详细程度分层，每层将全国划分成若干区，每层对应于各区进行设置，用表示道路上的地点的节点、表示所述地点间的道路的链路和道路的连接表示为链路的连接的链路串表示各区的道路网；路径计算数据也同样按道路网的详细程度分层，每层将全国划分成若干区，每层对应于各区进行设置，用表示道路上的地点的节点、表示所述地点间的道路的链路表示各区的道路网。

地图管理信息是按每层分别管理地图数据、路径计算数据的数据，每层具有使各区与各地图数据、路径计算数据对应的信息、各地图数据、路径计算数据在该地图信息中的存放位置、数据规模。

还具有示出该地图信息的版本的版本信息等。

如图2所示，地图数据包含：具有表示用于地图核对和道路显示的道路形状、道路连接关系的道路网数据，表示河川、海等地图背景用的背景数据，用文字表示地名等名称的名称数据、在交叉点等处进行路径引导用的路径引导数据等。

路径计算数据是用与所述道路网数据不同的数据结构表示路径计算用的道路网的数据，具有与路径计算用的道路网的链路对应的所述道路网数据的链路的链路号，使道路网的链路相互对应。

图3是表示最详细的道路网的最下层的矩形区A的地图数据表示的道路网的例子。

图3中，在节点N0～N7和链路L00、L01、L02、L10、L20、L30、L31组成的道路网上，链路L00、L01、L02形成链路串0，链路L10形成链路串1，链路L20形成链路串2，链路L30、L31形成链路串3。

假设各链路串中存在将链路串的终点节点作为始点节点的链路，并称之为假想链路。假想链路没有终点节点。下面，将链路串当作包含假想链路进行处理。

图3中，把以链路串0的节点N3为始点节点的链路当作假想链路L02’。将链路串0作为由链路L00、L01、L02和假想链路L02’组成链路串进行处理。

同样，也对链路串1、2、3分别假设存在假想链路L10’、L20’、L30’。

将链路串两端的节点中的一个作为始点、另一个作为终点时，把从始点到终点的方向作为链路串的方向。

图3中，实线箭头号表示链路串的方向，例如链路串0的始点节点为N0，终点节点为N3，从节点N0往节点N3的方向为链路串0的方向。

与链路串方向相同的方向称为正向，与链路方向相反的方向称为反向。

使链路方向与链路串方向相同。因此，链路的始点节点是链路的链路串始点方的节点，其终点节点是链路串的终点方的节点。

图3中，链路L01的始点节点是N1，终点节点是N2，链路L01的正向为节点N1到节点N2的方向。

关于某节点N连接的链路，对节点N处在所述链路所属的链路串的正向方的链路称之为节点N的正向链路，将处在其反向侧的链路称为节点N的反向链路。节点N的正向链路仅存在包含节点N的链路串的数量。

图3中，节点N1连接的链路L00、L01属于链路串0，对节点N1而言，链路L01处在链路串0的正向方，因而是节点N1的正向链路；链路L00处在链路串0的反向侧，因而是节点N1的反向链路。同样，链路L30是节点N1的反向链路，链路L31是节点N1的正向链路。节点N1的正向链路是2条链路L01、L31。

属于某节点N连接的相同链路串的链路Lx、Ly中，链路Lx为节点N的反向链路、链路Ly为节点N的正向链路时，即链路Lx位于链路Ly的前方时，把链路Lx称为链路Ly的前方链路，链路Ly则称为链路Lx的后方链路。

在图3，节点N1连接的链路串0的链路L00、L01中，链路L00是链路L01的前方链路，链路L01是链路L00的后方链路。

某节点N的反向链路成为节点N的正向链路的前方链路，从而节点N连接的链路径节点N的正向链路及其前方链路组成。因此，通过规定节点的正向链路，就能规定节点连接的全部链路。

在图3，节点N1连接的链路L00、L01、L30、L31中，如果规定节点N1的正向链路L01、L31，就能求出链路L00、L30为链路L01、L31的前方链路。

为了识别节点连接的链路，每一节点授予节点连接的各链路唯一的节点单元链路标识符。但是，如上文所述，用节点的正向链路规定节点连接的链路，因而作为节点单元链路标识符，仅授予节点的正向链路识别它们用的编号，将该编号称为节点单元链路号。

又将示出规定的链路是节点单元链路号指示的链路(下文称为自链路)还是节点单元链路号指示的链路的前方链路的信息称为前方指定。

能利用节点单元链路号和前方指定规定节点连接的链路、

图3中，分别授予节点N1的正向链路L01、L31节点单元链路号0、1的节点单元链路号，分别授予节点N2的正向链路L02、L10’、L20节点单元链路号0、1、2。

节点N1中，可通过使节点单元链路号＝0，前方指定＝前方链路，规定链路L00，可通过使节点单元链路号＝1，前方指定＝自链路，规定链路L31。

图3中，区域B是区域A下侧相邻的区域，节点N4、节点NX分别是设在区域A的边界和区域B的边界上的节点。处在区域边界上的节点称之为边界节点，处在不包含边界的区域内部的节点称之为内部节点。

节点N4和节点NX是设在同一道路的同一地点，即设在道路与区域A和区域B的边界线的交点的节点，通过节点N4和节点NX，使区域A和B的道路网接合。把节点NX称为节点N4的相邻边界节点。

边界节点只连接1条链路。

作为识别由地图信息的道路网数据表示的整个区域的全部链路用的链路标识符，授予各链路称为固有范围链路号的编号。实施方式1中，授予各链路预定的一定范围链路号，因而授予链路串内的各链路链路串方向上从小到大连续的链路号。但是，不授予假想链路链路号。

将所述预定的一定范围称为链路号设定常数，每一区域分别决定。

本实施方式1中，使链路号设定常数为256，分别授予图3中链路串0的链路L00、L01、L03链路号0～255、256～511、512～767，授予链路串1的链路L10链路号768～1023，授予链路串2的链路L20链路号1024～1279，授予链路串3的链路L30、L31链路号1280～1535、1536～1791。也同样授予其它地图数据的链路与上述不同的链路号。

以下为授予图3中各条链路上述链路号的情况。

图4示出一例道路网数据的数据结构。道路网数据由道路网数据首部、节点表、节点附加列表、链路串表、链路串附加列表组成。

道路网数据首部是存放构成道路网的节点数、节点附加列表的数据规模、构成道路网的链路串数、链路串附加列表的数据规模、链路号设定常数等的数据。

图5示出一例表示图3的道路网的道路网数据的节点表、节点附加列表的数据结构。

节点表是与节点对应设置的固定长度节点记录的排列，节点附加列表是与节点对应设置的可变长度节点附加记录的排列。

图5中，设置节点记录#0～#7、节点附加记录#0～#7，使其对应于图3的节点N0～N7。

将有关节点的信息分为固定长度部和可变长度部，在节点记录和节点附加记录中分别存放固定长度部和可变长度部。用节点记录和节点附加记录构成节点数据。

作为识别节点用的节点标识符，采用对应的节点数据的排列顺序，并称之为节点号。但是，由于将节点数据分为节点表和节点附加链路存放，作为节点数据排列顺序，采用构成该节点数据的节点记录在节点表中的排列顺序。图3的节点N0、N1、……、N7的节点号为各自的节点记录的排列顺序，即0、1、……、7。

图6示出一例表示图3的道路网的道路网数据的链路串表、链路串附加列表的数据结构。

链路串表是与链路串对应设置的固定长度链路串记录的排列，链路串附加列表是与链路串对应设置的可变长度链路串附加记录的排列。

图6中，设置链路串记录#0～#3、链路串附加记录#0～#3，使其对应于图3的链路串0～3。

作为识别链路串用的链路串标识符，采用对应的链路串记录的排列顺序，并称之为链路串号。

图3的链路串0、链路串1、链路串2、链路串3的链路串号分别为0、1、2、3。

将有关链路串的信息分为固定长度部和可变长度部，在链路串记录中存放固定长度部，在链路串附加记录中存放可变长度部。用链路串记录和链路串附加记录构成链路串数据。

以上所述那样，将节点数据和链路串数据独立存放，因而对1个节点存放1个节点数据，不重复存放相同的节点数据。

图7示出一例链路串记录的数据结构，链路串记录具有链路串状态、链路串类别。

链路串状态示出链路串的状态为延续或废弃，延续意味着该链路串继续存在，废弃意味着废弃该链路串。

链路串类别示出该链路串的道路类别，表示相当于高速道路(0)、都市高速道路(1)、国道(2)、主要地方道路(3)、都道府县道路(4)、一般道路(5)等等。上述括号内的值表示作为链路类别存放在链路串记录中的值。

即使链路串受到废弃，废弃链路串状态，也不删除其链路串记录，并且已有的链路串的链路串号不因链路串废弃而变化。

废弃链路串时，删除其链路串附加记录，防止保持不需要的数据，并进一步减小更新后道路网数据的数据规模。

新设的链路串的链路串记录添加在链路串表的末尾，防止已有链路串的链路串号变化。

图8示出一例链路串附加记录的数据结构，链路串附加记录由链路串附加首部、链路表、链路附加列表组成。

链路串附加首部具有链路串附加记录规模、链路记录数、最小链路号、最大链路号、缺省幅员信息、线路号。

链路串附加记录规模示出该链路串附加记录的数据规模。

链路记录数示出该链路串附加记录的链路表具有的链路记录数。

最小链路号示出授予该链路串的链路的链路号最小值。

最大链路号示出授予该链路串的链路的链路号最大值。

缺省幅员信息示出该链路串的道路幅员。

线路号示出该链路串的道路号。

链路表是与链路串内的链路对应设置的固定长度链路记录的排列，链路附加列表是与链路串内的链路对应设置的可变长度链路串附加记录的排列。

将有关链路的信息分为固定长度部和可变长度部，在链路记录中存放规定长度部，在链路附加记录中存放可变长度部。用链路记录和链路附加记录保持链路数据。

链路表是按该链路串的正向链路排列顺序配置与链路对应设置的链路记录的数据。

作为识别链路串内的链路用的链路串内链路标识符，采用与链路对应的链路记录的排列顺序，并称之为链路串内链路号。这样，以依赖于链路串方向的方式授予链路该链路串内链路标识符，即链路串内链路号。

链路附加表是按该链路串的正向链路排列顺序配置与链路对应设置的链路附加记录的数据。但是，不配置不需要链路附加记录的链路的链路附加记录。

废弃或划分链路时，废弃和划分链路状态，不删除其链路串记录，并且已有的链路的链路串内链路串号不因链路废弃或划分而变化。

废弃或划分链路串时，删除其链路附加记录，防止保持不需要的数据，并进一步减小更新后道路网数据的数据规模。

链路记录具有链路状态、链路有无附加信息、划分链路串号、链路类别、单向通行信息、始点节点号、链路添加指针。

链路状态示出该链路处在延续、废弃或划分的状态。延续意味着该链路继续存在，废弃意味着废弃有关链路，划分意味着划分有关链路。

链路有无附加信息示出是否存在该链路所对应的链路附加记录。不对链路状态为废弃或划分的链路、链路状态延续且没有链路附加记录中应存放的信息的链路、假想链路设置链路附加记录。

用链路状态和划分链路串号表示划分链路串涉及的信息，划分链路串号仅在链路串状态划分时有效，示出划分该链路所得的链路组成的链路串的链路串号。

将划分链路所得的链路组成的链路串称为划分链路串。

以上所述那样，作为有关划分链路串的信息，根据具有链路状态，可知是否划分链路；根据具有划分链路串号，立即可知划分链路串的链路串记录的地址。

链路类别示出依据上下线非分离主线链路(0)、上下线分离主线链路(1)、主线间传递链路(2)、交叉点内链路(3)等道路结构等的链路的类别。

单向通行信息示出该链路的单向通行规则为没有限制(0)、禁止正向通行(1)或禁止反向通行(2)。

始点节点号示出该链路的始点节点的节点号。这样，链路记录具有根据链路串方向决定的该链路端的1个节点(即所述始点节点)的节点号。可从后方链路的链路记录的始点节点号求出链路的终点节点的节点号，因而使链路记录仅持有始点节点的节点号，不持有终点节点的节点号，从而减小道路网数据的数据规模。

链路附加指针指示该链路所对应的链路附加记录的链路附加列表的存放位置，即以链路附加列表的始端为基准的地址。上述括号内的值表示作为链路类别、单向通行信息存放到链路记录中的值。

链路附加记录具有链路附加首部、链路形状信息、链路号信息、幅员信息。

链路附加首部具有表示链路附加记录的数据规模的链路附加记录数据规模、指示有无链路形状信息的链路形状有无信息、指示有无链路号信息的链路号有无信息、指示有无幅员信息的幅员有无信息。

链路形状信息示出该链路的道路形状，具有用折线近似表达道路形状时表示各折线顶点的地理位置的插补点坐标的排列和插补点坐标的数量。道路形状为直线时，不设链路形状信息。

链路号信息示出该链路的链路号的最小值。存在链路号信息时，该链路的链路号最小值等于链路号信息指示的值，最大值等于该链路的后方链路最小链路号的最小值减1所得的值。但是，由链路附加首部的最大链路号给出将链路串终点的节点作为终点节点的链路的链路号的最大值。

链路号信息不存在时，如果使链路串附加首部的最小链路号为LIDMIN，该链路的链路串内链路号为LN，则由以下的式1、式2节点决定该链路的链路号的最小值、最大值。

最小值＝LIDMIN+链路号设定常数×LN ……(式1)

最大值＝LIDMIN+链路号设定常数×(LN+1)-1 ……(式2)

幅员信息示出该链路的道路幅员，存在幅员信息时，该链路的道路幅员为该幅员信息指示的值，不存在幅员信息时，该幅员为链路串附加首部的缺省幅员信息指示的值。

图9示出图6的链路串记录的存放例。图9中，图3的链路串0～3延续，对链路串记录#0～#3的链路串状态存放0(延续)。链路串0由都道府县道路的链路组成，对链路串记录#0的链路串类别存放4(都道府县道路)。链路串1～3由一般道路的链路组成，对链路串记录#1～#3的链路串类别存放5(一般道路)。

图10示出图6的链路串0的链路串附加记录#0的存放例。图10中，设链路串0的全部链路延续，链路串0的链路串附加记录的数据规模为mlas0，链路串0的全部链路的道路类别为都道府县道，链路类别为上下线非分离主线，并且没有单向通行限制。

又设链路串0的链路L01以外的链路的道路幅员为dw0，链路L01的道路幅员为w01，链路串0的全部链路的路线号为m0，链路L00、L01的道路形状分别为用链路形状信息si00、si01表示的形状，并且链路L02的道路形状为直线，没有链路形状信息。

图10的链路串附加首部存放mlas0作为链路串附加记录的规模，存放包含假想链路的链路记录的值4作为链路记录数，存放链路L00的链路号最小值0作为最小链路号，存放链路L02的链路号最大值767作为最大链路号，存放幅员dw0作为缺省幅员信息，存放m0作为路线号。

图10的链路表中设置链路L00、L01和L02、假想链路L02’的链路记录#0～#3。链路L00、L01和L02、假想链路L02’的链路串内链路号分别为0、1、2、3。

链路记录#0～#3中，也对链路状态存放0(延续)，对链路类别存放0(上下线非分离主线)，对单向通行信息存放0(没有限制)，对划分链路号存放表示无效的特定值(无效值)。

链路L00、L01和L02、假想链路L02’的始点节点分别为N0、N1、 N2、N3，并且链路记录#0～#3的始点节点号中分别存放节点N0、N1、N2、N3的节点号0、1、2、3。

链路L02没有链路形状信息，并且幅员为缺省幅员信息表示的幅员dw0，因而不需要链路附加记录，并对链路记录#2的链路有无附加信息存放0(无附加)。又，链路记录#3与假想链路相对应，因此对链路有无附加信息存放0(无附加)。

链路L00具有链路形状信息，链路L01具有链路形状信息，同时幅员为与缺省幅员信息不同的幅员w01，因而具有幅员信息。因此，链路记录#0、#1链路有无附加信息中存放1(有附加)，并且对链路L00、L01设置链路附加记录#0、#1。链路记录#0、#1的链路附加指针中分别存放链路附加记录#0、#1的地址p0、p1。链路记录#3、#4的链路附加指针中由于没有相当的链路附加记录，存放任意值。

图10的链路附加记录#0中，存放设定该链路附加记录的数据规模las00、并设定成仅具有链路形状信息的链路附加首部，而且对链路形状信息存放si00。

图10的链路附加记录#1中，存放设定该链路附加记录的数据规模las01、并设定成具有链路形状信息和幅员信息的链路附加首部，而且对链路形状信息存放si01，对幅员信息存放w01。

图11示出一例节点记录的数据结构。节点记录具有节点状态、边界信息、有无引导信息等。

节点状态示出节点延续或被废弃。

边界信息示出节点处在该地图数据区的边界上还是处在其内部。

有无引导信息示出是否存在节点所对应的路径引导数据的路径引导记录。

即使废弃节点，使节点状态废弃，也不删除其节点记录，已有的节点的节点号不因节点废弃而变化。

废弃节点时，删除其节点附加记录，防止保持不需要的数据，以进一步减小更新后的道路网数据的数据规模。

新设的节点的节点记录添加在节点表的末尾，以防止已有节点的节点号变化。

图12示出一例节点附加记录的数据结构。节点附加记录具有节点附加首部、节点坐标、连接链路信息、链路间通行规则信息等。

节点附加首部具有表示节点附加记录的数据规模的节点附加记录规模、表示连接链路信息的连接链路记录数的连接链路记录数、表示链路间通行规则信息的通行规则记录数的通行规则记录数。

节点坐标表示纬度、经度，示出该节点附加记录所对应的节点的地理位置。

连接链路信息有由固定长度的连接链路记录的排列组成。连接链路记录有2种：内部连接链路记录和相邻连接链路记录。

内部连接链路记录示出该节点的正向链路和识别这些链路用的节点单元链路标识符，相邻连接链路记录示出该节点的相邻边界节点。

连接链路信息中配置只有包含该节点上连接的链路的链路串的数量的内部连接链路记录，该节点如果是边界节点，就进一步将相邻连接链路记录配置在所述内部连接链路记录的后面。

内部连接链路记录具有节点单元链路号、连接链路串号、连接链路串内链路号。

连接链路串号、连接链路串内链路号构成连接链路规定信息，规定包含该节点上连接的链路的链路串的该节点的正向链路，并示出所述正向链路的链路串号、链路串内链路号。

这样，连接链路规定信息就根据链路串的方向规定该节点的正向链路。

节点单元链路号示出授给连接链路串号、连接链路串内链路号表示的链路的编号。节点单元链路号是识别该节点的正向链路的节点单元链路标识符，以节点为单位授给唯一的编号。而且，节点单元链路号在该链路延续期间不变。

因此，节点单元链路号不因其它链路废弃、新设而变化。本实施方式中，授给0～15作为节点单元链路号。

如上所述，可根据内部连接链路记录的连接链路串号、连接链路串内链路号规定该节点的正向链路，并可通过从内部连接链路记录的连接链路串内链路号减1，获得该节点的正向链路所对应的反向链路的链路串内链路号。但是，连接链路串内链路号为0时，该节点的正向链路的对应的反向链路不存在。

这样，利用连接链路信息中配置的内部连接链路记录就能直接规定该连接的全部链路。

相邻连接链路记录具有相邻区指定和相邻边界节点号。相邻区指定示出该边界节点的相邻边界节点归属的相邻区中相对于该区的位置关系，即上(0)、右(1)、下(2)、左(3)，相邻边界节点号示出该边界节点的相邻边界节点的相邻区中的节点号。

上述括号内的值表示作为相邻区指定存放到相邻连接链路记录中的值。

所述连接链路信息中，在节点的正向链路及其前方链路的链路状态均为废弃或划分时，删除所述正向链路的连接链路记录。

某节点Nx新连接某链路Lx时，所述节点的连接链路信息中添加表示包含链路Lx的链路串的节点Nx的正向链路的连接链路记录。

利用上述连接链路记录的数据结构，能以删除、添加连接链路记录的简单处理进行节点连接的链路的更改。

在内部连接链路记录中存放正向链路的链路号、链路内链路号，因而直接知道连接的链路的链路记录的地址。

不设置节点的正向链路的前方链路所对应的内部连接链路记录，而是通过用节点的正向链路的内部连接链路记录表示链路的连接关系，能减小道路网数据的数据规模。

又，以节点为单位授给节点单元链路号，因而节点上连接的最大链路数为16左右，节点单元链路号所需的数据规模可为4位左右，与使用按链路串号和链路串内链路号规定链路那样的识别该区内的全部链路的信息时相比，能减小内部连接链路记录的数据规模。

由于已有的链路串、链路的链路串号、链路串内链路号不因链路串、链路的废弃、新设而变化，不需要因其它链路串、链路的废弃、新设而改变已有的内部连接链路记录。

又由于已有的节点的节点号不因节点的废弃、新设而变化，即使更新相邻区的地图数据，也不需要更改该区的相邻连接链路记录，不更新该道路网数据，就能连接版本不同的地图数据，并且在每一地区进行划分更新时，不更新不要求更新的地区的道路网数据，只更新所要求地区，也能保持道道路网之间连接的匹配。

链路间通行规则信息由固定长度的通行规则记录的排列组成，示出节点连接的链路之间的通行规则。

将通行规则记录的排列顺序称为通行规则记录号，用通行规则记录号指定通行规则记录。

通行规则记录具有进入侧节点单元链路号、进入侧前方指定、脱离侧链路单元链路号、脱离侧前方指定、通行规则码。

进入侧节点单元链路号、进入侧前方指定规定对该节点的进入链路，进入侧节点单元链路号示出规定进入链路用的节点单元链路号，进入侧前方指定示出进入链路对进入侧节点单元链路号而言，相当于自链路和前方链路中的哪一个。

脱离侧节点单元链路号、脱离侧前方指定规定对该节点的脱离链路，脱离侧节点单元链路号示出规定脱离链路用的节点单元链路号，脱离侧前方指定示出脱离链路对脱离侧节点单元链路号而言，相当于自链路和前方链路中的哪一个。

通行规则码示出该节点中从进入链路到脱离链路的通行所涉及的车种规则、数据规则等各种通行规则。

如上文所述那样，通行规则码在进入链路、脱离链路指定中使用节点单元链路号，节点单元链路号不对其它链路的废弃、新设产生变化，因而不必对其它链路的废弃、新设改变通行规则码。

图13示出图5的节点记录的存放例。图13中，节点N0～N7延续，对全部节点记录的节点状态存放0(延续)。

节点N4是边界节点，其它节点是内部节点，因而对节点记录#4的节点状态存放1(边界)，对其它节点记录的节点状态则存放0(内部)。

存在节点N1、N2所对应的引导记录，对节点记录#1、#2有无引导信息存放1(有引导)，对其它节点记录的有无引导信息则存放0(无引导)。

图14示出图5的节点附加记录的存放例。

图14的节点附加记录#0中，节点N0的正向链路是L00，没有链路间通行限制，对节点附加首部的链路记录数存放1，对通行规则记录数存放0，并且对节点附加记录规模存放节点附加记录#0的数据规模nrs0。

作为节点坐标，存放节点N0所处位置的纬度x0、经度y0。

作为连接链路信息，设置表示链路L00的内部连接链路记录C00，并存放0作为节点单元链路号，存放链路L00归属的链路串0的链路串号0作为连接链路串号，存放链路L00的链路串0的链路串内链路号0作为连接链路串内链路号。

由于没有链路间通行规则，因此不存放链路间通行规则信息。

图14的节点N6的节点附加记录#6也与上述节点附加记录#0同样地进行存放。

图14的节点附加记录#3中，节点N3的正向链路是假想链路L02’，没有链路间通行规则，并且对节点附加首部的连接链路记录数存放1，对通行规则记录数存放0。对节点附加记录规模存放节点附加记录#0的数据规模nrs3。

作为节点坐标，存放节点N3所处位置的纬度x3、经度y3。

作为连接链路信息，设置表示链路L02’的内部连接链路记录C30，并存放3作为节点单元链路号，存放假想链路L02’所属的链路串0的链路串号0作为连接链路串号，存放假想链路L02’的链路串0的链路串内链路号3作为连接链路串内链路号。

由于没有链路间通行规则，不存放链路间通行规则信息。

图14的节点N5、N7的节点附加记录#5、7也与上述节点附加记录#3同样地进行存放。

图14的节点附加记录#1中，节点N1的正向链路是链路L01、L31，作为链路间通行规则，具有从链路L00到链路L30的通行规则rc10、从链路L31到链路L00的通行规则rc11，并且对节点附加首部的连接链路记录数存放2，对通行规则记录数存放2。对节点附加记录规模存放节点附加记录#1的数据规模nrs1。

作为节点坐标，存放节点N1所处位置的纬度x1、经度y1。

作为图14的节点附加记录#1的连接链路信息，设置表示链路L01的内部连接链路记录C10，设置表示链路L31的内部连接链路记录C11。

内部连接链路记录C10中，存放链路L01归属的链路串0的链路串号0作为连接链路串号，存放链路L01的链路串0中的链路串内链路号1作为连接链路串内链路号，又在内部连接链路记录C11中，存放链路L31归属的链路串3的链路串号3作为连接链路串号，存放链路L31的链路串3中的链路串内链路号1作为连接链路串内链路号。

内部连接链路记录C10中，存放1作为节点单元链路号；内部连接链路记录C11中，存放1作为节点单元链路号。这样，作为节点单元链路号，对节点N1的正向链路，即链路L01、L31，分别在节点N1授给唯一的编号0、1。

作为图14中节点附加记录#1的链路间通行规则信息，设置表示从链路L00到链路L30的通行规则的通行规则记录R10、表示从链路L31到链路L00的通行规则的通行规则记录R11。

通行规则R10中，对进入侧节点单元链路号存放节点N1的正向链路L01的节点单元链路号0(＝内部连接链路记录C10的节点单元链路号)，对进入侧前方指定存放1(前方链路)。根据上文所述，指示进入链路是链路L00。

又，对脱离侧节点单元链路号存放节点N1的正向链路L31的节点单元链路号1(＝内部连接链路记录C11的节点单元链路号)，对进入侧前方指定存放1(前方链路)。根据上文所述，指示脱离链路是链路L30。

作为通行规则码，存放表示从链路L00到链路L30的通行规则的rc10。

通行规则R11中，对进入侧节点单元链路号存放节点N1的正向链路L31的节点单元链路号1(＝内部连接链路记录C11的节点单元链路号)，对进入侧前方指定存放0(自链路)。根据上文所述，指示进入链路是链路L31。

又，对脱离侧节点单元链路号存放节点N1的正向链路L01的节点单元链路号0(＝内部连接链路记录C10的节点单元链路号)，对进入侧前方指定存放1(前方链路)。根据上文所述，指示脱离链路是链路L00。

作为通行规则码，存放表示从链路L31到链路L00的通行规则的rc11。

图14中的节点N2的节点附加记录#2也与节点附加记录#1同样地进行存放。

图14的节点附加记录#4中，节点N4是边界节点，其正向链路是链路L10，没有链路间通行限制，对节点附加首部的连接链路记录数存放2，对通行规则码数存放0。对节点附加记录规模存放节点附加记录#4的数据规模nrs4。

作为节点坐标，存放节点N4所处位置的纬度x4、经度y4。

作为连接链路信息，设置与链路L10对应的内部连接链路记录C40、相邻连接链路记录C41，内部连接链路记录C40与节点附加记录#0的内部连接链路记录同样地进行存放。

由于节点N4的相邻边界节点NX属于该区A下方相邻的区B，相邻连接链路记录C41中，对相邻区指定存放2(下)，对相邻边界节点号存放节点NX的区B的道路网数据中的节点号nx。

由于没有链路间通行限制，不存放链路间通行观测信息。

图15示出一例路径引导数据的数据结构。路径引导数据是与节点对应设置的路径引导记录的排列。如上述路径引导记录那样，将设置得与节点关联的信息称为节点关联信息。

把路径引导记录的排列顺序称为路径引导记录号，用路径引导记录号识别路径引导记录。

路径引导记录由路径引导记录首部、表示节点的交叉点的名称的交叉点名称数据、表示节点上连接的链路的道路名称的道路名称数据、表示节点上连接的链路的目的处的方向名称数据等节点中引导所需的各种数据组成。

路径引导记录首部具有表示该路径导记录的数据规模的路径引导记录规模、对应的节点的节点号、表示交叉点名称数据、道路名称数据、方向名称数据等的数据规模的数据。这样，作为节点关联信息的路径引导记录具有对应的节点的节点标识符，即节点号。

路径引导记录按对应节点号从小到大的顺序配置，能方便地进行基于节点号的路径引导记录的检索。

如上文所述那样，利用对应节点号，使路径引导数据记录与节点相关，因而即使进行路径引导数据记录删除、添加、数据规模改变的内容更改等更新，也不产生这些更新带来的道路网数据的改变。而且，由于已有节点的节点号不对节点的废弃、新设发生变化，不必更改已有路径引导记录的对应节点号，不产生道路网数据更新带来的路径引导数据的更改。

图16示出路径引导数据的存放例。图16中，对应于图3的节点N1、N2，设置路径引导记录#0、路径引导记录#1。路径引导记录#0、路径引导记录#1的路径引导记录首部的对应节点号中存放节点N1、N2的节点号1、2。

图17示出更新图3的道路网后得到的道路网。图17中，废弃链路L01、链路串2，新设链路L40、L41组成的链路串4，新设由划分链路L00后得到的链路L50、L51组成的链路串5，废弃节点N5，并新设节点N8、N9。L41’是链路4的假想链路，L51’是链路5的假想链路。

划分链路L00后得到的链路L50、L51为代替链路L00设置的链路即可，可使链路L50、L51表示的道路形状与链路L00表示的道路形状不一致。将链路L00那样的划分的链路称为划分前链路，链路L50、L51那样的划分后得到的链路则称之为划分后链路。

图17中，为了防止链路串0的各链路的链路串内链路号变化，不是将划分前链路L00置换成划分后链路L50、L51，而是另行设置链路L50、L51组成的链路串5，在链路L00的始点节点、终点节点分别连接链路串5的始点节点和终点节点。

下面说明将道路网从图3更新成图17时的道路网数据的更新。

图18示出更新图5后得到的节点表、节点附加列表的存放例。

图18中，由于新设节点N8、N9，在节点表的末尾添加节点N8、N9的节点记录#8、#9。

又，在图18的节点附加列表中，通过废弃节点N5，删除节点N5的节点附加记录#5，通过新设节点N18、N19，在节点附加列表的末尾添加节点N8、N9的节点附加记录#8、#9。

图19示出更新图6后得到的链路串表、链路串附加列表的例子。

图19的链路串表中，由于新设链路串4、5，在链路串表的末尾添加链路串4、5的链路串记录#4、#5。

而且，图19的链路串附加列表中，由于废弃链路串2，删除链路串附加记录#2，又由于新设链路串4、5，在链路串附加列表的末尾添加链路串4、5的链路串附加记录#4、#5。

图22示出图18的节点表的各节点记录的存放例。图22中，由于废弃节点N5，将节点N5的节点记录#5的节点状态改为1(废弃)；废弃节点N1的引导，使节点N1的节点记录#1的有无引导信息变为0(无引导)；新设对节点N7的路径引导记录，使节点N7的节点记录#7的有无引导信息变为1(有引导)。

图23示出更新图14后得到的节点附加记录的存放例。

图23中，如上文所述那样，删除节点附加记录#5，添加节点附加记录#8、#9。

图23的节点N0的节点附加记录#0中，由于划分链路L00，删除连接链路记录C00，并且在连接链路信息中添加表示新设的链路L50的连接链路记录C01。按照上文所述，节点N0上连接划分后得到的链路L50，以代替链路L00。

节点N1的节点附加记录#1中，在对被划分的链路L00划分的同时，废弃链路L01，因而删除连接链路记录C11后，在连接链路信息中添加表示假想链路L51’的连接链路记录C12。

按照上文所述，节点N1连接划分后得到的链路L51，以代替链路L00，不连接链路L01。

再者，新添加的连接链路记录的节点单元链路号，授给添加前存在的连接链路记录不使用的节点单元链路号中最小的号。节点N1中，添加连接链路记录C12前使用的节点单元链路号仅为1，因而存放0作为连接链路记录C12的节点单元链路号。

上述更新的结果，通行规则记录R10示出从链路L31到链路L51的通行规则，通行规则记录R11示出从链路L51到链路L30的通行规则，但即使链路L00换成链路L51，链路间通行规则也不变，因而不进行通行规则码的更新。

图23的节点N2的节点附加记录#2中，由于废弃链路串2(即链路L20)，删除连接链路记录C22，然后连接链路信息中添加表示新设的链路L40的连接链路记录C23。按照上文所述，节点N2连接链路L40。添加连接链路记录C23前使用的节点单元链路号为0、1，因而存放上述0、1以外的最小链路号2，作为连接链路记录C23的节点单元链路号。

通过废弃链路串2，删除表示从链路L20到链路L01的通行规则的通行规则记录R21，在链路间通行规则信息中添加表示从新设的链路L40到链路L10的通行规则的通行规则记录R22。

又，即使节点N2连接的链路因新设链路串4而变化，节点N2中已有的链路L02、L01’的节点单元链路号也不变，因而节点N2中已有的通行规则记录R20不必更改。

图23的节点N7的节点附加记录#7中，在连接链路信息添加表示新设的链路L41的连接链路记录C71。按照上文所述，节点N7连接链路L40、L41。添加连接链路记录C71前使用的节点单元链路号为0，因而存放上述0以外的最小链路号1，作为连接链路记录C71的节点单元链路号。

又，将节点附加首部的节点附加记录规模更改为nrs7加连接链路记录C71部分所得的nrs7’。

图20示出图19的链路串表中的链路串记录的存放例。由于废弃链路串2，将链路串2的链路串记录#2的链路串状态改为1(废弃)，并且对新设的链路串4添加链路串状态为0(延续)、链路串类别为5(一般道路)的链路串记录#4，对新设链路串5添加链路串状态为0(延续)、链路串类别与划分链路前同样为4(都道府县道路)的链路串记录#5。

图21示出更新图10后得到的链路串0的链路串附加记录#0的链路串附加首部、链路表的存放例。

图21中，由于划分链路L00，将链路记录#0的链路状态改为2(划分)，链路有无附加信息改为0(无附加)，划分链路号改为划分链路L00后的链路组成的链路串5的链路串号5。

如上文所述，不将划分前链路L00的链路记录置换成划分后的链路L50、L51的2个链路记录，所以链路记录的组成不因链路划分而变化，链路串0的链路L01、L02、L02’的链路串内链路号不变。

又，如上文所述，链路L00的链路记录中存放表示划分的链路状态、划分链路串号，因而直接可知链路L00的划分链路串5的链路串记录的地址。

由于废弃链路L01，使链路记录#1的链路状态为1(废弃)，链路有无附加信息为0(无附加)。

又，通过划分链路L00并废弃链路L00，删除链路附加列表的链路附加记录#0、#1。

又，将链路串附加首部的链路附加记录规模改为从mlas0减去删除的链路附加记录#0、链路附加记录#1的份额后得到的mlas0’。

图24示出链路L00划分后的链路L50、51组成的链路串5的图21中的链路串附加记录#5的存放例。

图24的链路串附加记录#5的各数据与上述各链路串附加记录同样地进行存放。但是，图24的链路串附加首部中，对最小链路号、最大链路号存放划分前的链路L00的最小链路号0、最大链路号255。图24的链路附加列表中，对链路L51的链路附加记录#1的链路号信息存放128。

因此，链路L50的链路号的最小值，根据式1，为0；其最大值为作为链路L51的链路附加记录#1的链路号信息存放的128减去1后得到的127。而且，链路L51的链路号的最小值为作为链路附加记录#1的链路号信息存放的128，最大值为链路串首部附加首部中的最大链路号255。即，授予链路L50链路号0～127，授予链路L51链路号128～255。

这样，将划分前的链路L00的范围0～255的链路号等分后，给划分后的链路L50、L51各自分配范围0～127、128～255的链路号。

图25示出后续于上述划分，又对链路L00进行划分时授给链路号的例子。又将链路L50划分成链路L50-0、L50-1，分别给链路L50-0、L50-1分配把链路L50的范围0～127的链路号等分的范围0～63、64～127的链路号。下面，每次划分链路，也同样等分划分前链路的链路号，将其分配给划分后链路。判明链路L00可划分达8次。

由于将链路号设定常数取为256，图3的其它链路也于上文所述相同，能划分达8次。

上文中，将链路号设定常数取为256，但把链路号设定常数设定为257，并等分范围0～256的链路号时，相当于分配范围0～127.5、127.5～256的链路号，但链路号为整数，因而分配对上述范围的上限、下限的小数部分进行舍去、舍入后所得的范围0～127、128～256的链路号，使上述范围不重复。这样对划分后的链路分配的链路号，只要根据上文所述那样等分所得的范围决定即可。

图26示出更新图16后得到的路径引导数据的例子。

图26的路径引导数据是废弃节点N1的路径引导，并新设节点N7的路径引导时的路径引导数据，其中废弃节点N2所对应的路径引导记录#0，添加节点N7所对应的路径引导记录#2，并存放节点N7的节点号7作为路径引导记录#2对应的节点号。

将节点记录、节点附加记录做成以上那样的数据结构，因而可作为节点号与节点记录的数据规模的乘积求出节点记录在节点表中的存放位置。节点附加记录在节点附加列表中的存放位置用依赖于节点状态，并从节点附加列表的始端进行累加的简单运算处理，就能求出。例如，图23中，通过依次进行A0＝0、A1＝A0+nrs0、A2＝A1+nrs1、A3＝A2+nrs2、A4＝A3+nrs3、A5＝A4+nrs4、A6＝A5、A7＝A6+nrs6、A8＝A7+nrs7’，A9＝A8+nrs8的运算，能算出节点附加记录#q(q＝0、1、2、……、9)的存放位置Aq(q＝0、1、2、……、9)。但是，废弃节点N5，节点状态为废弃，因而计算节点N6的节点附加记录#6的存放位置A6时，节点N5的节点附加记录规模为0，作为A6＝A5求出。首次使用道路网数据时，预先如以上那样求出各节点附加记录的存放位置，按节点号的顺序编制配置A0、A1、A2、A3、A4、A5、A6、A7、Ag、A9和节点附加记录存放位置的节点附加记录存放位置表，则通过参照节点附加记录存放位置表，能直接求出所要求节点号的节点附加记录的存放位置。这样，将节点号用作节点标识符，能根据节点标识符迅速取得所用的节点的节点数据。

下面说明本发明实施方式1的更新地图信息用的地图更新信息的数据结构。

图27示出存放在插入到更新信息获取装置4的更新用DVD-ROM的地图更新信息的概略数据结构。图27中，地图更新信息具有地图更新管理信息、1以上的地图更新数据、路径计算更新数据。

地图更新管理信息是每一层管理更新数据的数据，每层具有使各区与各地图更新数据、路径计算更新数据对应的信息，各地图更新数据、路径计算更新数据的地图信息存放位置、数据规模。

还具有表示该DVD-ROM存放地图更新信息的数据识别信息、表示该地图更新信息是作为更新对象的地图信息的版本数的更新对象版本信息、表示由该地图更新信息进行更新后得到的地图信息的版本的更新版本信息。

地图更新数据是更新地图数据用的数据，与地图数据对应设置。不存放对不需要更新的地图数据的地图更新数据。路径计算更新数据是更新路径计算数据用的数据，与路径计算数据对应设置。不存放对不需要更新的路径计算数据的路径计算更新数据。

地图更新数据具有对道路网数据、背景数据、名称数据、路径引导数据等进行更新用的道路网更新数据、背景更新数据、名称更新数据、路径引导更新数据等以及地图更新首部。不存放不需要更新的数据的更新数据，上述更新数据由1个以上的更新记录组成。

地图更新首部是管理上述各更新数据用的数据，具有上述各更新数据的该地图数据的存放位置、数据规模、更新记录数等。

图28示出一例更新记录的数据结构。图28中，更新记录由更新对象实体类别、更新对象数据类别、更新操作类别、参数数量、操作数数量、更新对象实体指定、更新操作列表组成。

更新对象实体类别表示无指定(0)、节点(1)、链路(2)、链路串(3)等作为更新对象的地理实体的类别，更新对象数据类别表示构成道路网数据等的数据的类别，更新操作类别表示废弃(0)、新设(1)、链路划分(2)等有关地理实体的更新操作、盖写(10)、删除(11)、置换(12)、添加(13)等有关数据的更新操作的类别，参数数量表示更新对象指定具有的参数的数量，操作数数量表示更新操作数具有的操作数的数量，更新对象实体指定利用节点号、链路串号、链路串内链路号等参数指定更新的对象实体，更新操作数列表示出用于节点记录、节点附加记录等的更新的数据。作为更新对象实体指定、更新操作数列表存放的数据，其含义由更新对象实体类别、更新对象数据类别、更新操作类别决定。

作为所述更新对象数据类别，例如作为有关节点的数据，定为节点记录(10)、节点状态(12)、边界信息(12)、有无引导信息(13)、节点附加记录(100)、节点附加首部(110)、节点坐标(120)、连接链路信息(130)、链路间通行规则信息(140)、通行规则记录(141)等。

上文中，括号内的值是存放到更新记录的值。

为了使连接链路记录的删除方便，有关链路更新的更新记录按照链路所属链路串顺序递升的方式配置，属于相同链路串的链路的更新所涉及的更新记录按照链路串内链路号顺序递升的方式配置。

新设链路串时，可用新设的链路串记录和链路串附加记录编制新设链路的连接链路记录，并能作为已有连接链路记录没有使用的最小节点单元链路号授给新设链路的节点单元链路号，因而将用于新设链路串的更新记录配置在表示节点新设、链路废弃、链路划分、链路串废弃的更新记录后。

图29示出将道路网从图3更新为图17用的道路网更新数据的存放例。图29中，更新记录#r0表示盖写节点号1的节点(节点N1)的链路记录有无用的信息，具有引导信息(＝0(无))作为应在更新操作数列表上盖写的数据。

更新记录#r1表示删除节点号2的节点(节点N2)的链路间通行规则信息的通行规则记录号为1的通行规则记录R21。

更新记录#r2表示对节点号2的节点(节点N2)的链路间通行规则记录添加通行规则记录，具有图23的通行规则记录R22作为应在更新操作数列表上添加的数据。

更新记录#r3表示废弃节点号5的节点N5。更新记录#r4表示新设节点，具有图18的节点记录#8、节点附加记录#8作为应添加到更新操作数列表以新设节点的数据。更新记录#r5表示新设节点，具有图18的节点记录#9、节点附加记录#9作为应添加到更新操作数列表以新设节点的数据。

更新记录#r6具有的数据表示划分链路串号0的链路串0的链路串内链路号0的链路L00，并且更新操作数列表中该划分链路串的链路串号为5，即链路串5。更新记录#r7表示废弃链路串号0的链路串0的链路串内链路号1的链路L01。

更新记录#r8表示废弃链路串号2的链路串2。更新记录#r9表示新设链路串，具有应添加到更新操作数列表以新设链路串的数据，即图19的链路串记录#4、链路串附加记录#4。更新记录#r10表示新设链路串，具有应添加到更新操作数列表以新设链路串的数据，即图19的链路串记录#5、链路串附加记录#5。

图30示出将图16的路径引导数据更新为图25的路径引导数据用的路径引导更新数据的存放例。图30中，更新记录#g0表示删除路径引导记录号0的路径引导记录#0。更新记录#g1表示添加路径引导记录，作为更新操作数，具有应为新设路径引导记录添加的数据，即图25的路径引导记录#2。

图31是示出图1所示地图信息处理装置的运作的流程图。下面，以将图3的道路网更新为图17的道路网的情况为例，根据图31的流程图说明图1所示的地图信息处理装置的运作。

图32示出处理器5的存储器分配。图32中，在处理器5的存储器中分配存放控制地图信息处理装置的运作用的数据的运作控制数据部10、存放作为该位置检测装置22中获得的位置信息的时间序列的行驶轨迹数据的行驶轨迹数据部11、存放表示该车辆的当前位置的数据的当前位置数据部12、存放表示从出发处到目的地的路径的路径数据的路径数据部13、存放所需路径计算管理数据的所需路径计算数据管理部14、存放路径计算数据的路径计算数据部15、存放路径计算更新数据的路径计算更新数据部16、存放所需地图管理数据的所需地图管理数据部17、存放地图数据的地图数据部18、存放地图更新数据的地图更新数据部19。

起动地图信息处理装置，使处理开始时，首先，在步骤ST10进行处理器5的存储器初始化后，进至步骤ST11。

步骤ST11中，证实是否将更新用DVD-ROM插入到更新信息获取装置4，插入时，进至步骤ST12，没有插入，则进至步骤ST13。

步骤ST12中，读取插入到更新信息获取装置4的更新用DVD-ROM存储的地图更新信息的地图更新管理信息，比较地图更新管理信息中存在的更新对象版本信息和地图信息存储装置3存储的地图信息的地图管理信息中存在的版本信息，如果一致，可进行基于上述地图更新信息的所述地图信息的更新，从而读取上述地图更新信息，存放到地图信息存储装置3后，进至步骤ST13。

步骤ST13中，根据按照使用者的操作或指示的指示信号，从输入装置1，将例如地图的显示缩小比例尺、目的地、路径计算的开始指示等控制地图信息处理装置运作用的数据存放到运作控制数据部10后，进至步骤ST14。

步骤ST14中，从位置检测装置2取得位置信息，将取得的位置信息累积存放到行驶轨迹数据部11，同时第1次的步骤ST14的处理中，将取得的位置信息作为当前位置存放到当前位置部12后，进至步骤ST15。

步骤ST15中，判断运作控制数据部10是否指示起动路径计算，如果指示，进至步骤ST16，没有指示，则进至步骤ST18。

步骤ST16中，将当前位置数据部12示出的位置作为出发处，存放到运作控制数据部10，并进行得到从运作控制数据部10示出的出发处到目的地的较佳路径用的路径计算所需的路径计算数据的获取和更新后，进至步骤ST17。

步骤ST17中，用步骤ST16获取、更新的路径计算数据进行路径计算，求出从所述出发处到目的地的较佳路径，将表现所述路径的路径数据存放到路径数据部13，并取消运作控制数据部10的路径计算起动指示后，进至步骤ST18。

图33示出图3的区A的路径计算数据表示的道路网的例子。

图33的道路网中，节点Nr0、Nr1、Nr3、Nr6、Nr7分别对应于图3的节点N0、N1、N3、N6、N7。

分别对应于图3的链路L00、L30、L31，授予图33的链路Lr00、Lr30、Lr31图3中对应的链路的链路号0～255、1280～1535、1536～1791。链路Lr01综合图3的链路L01和L02，授予前者综合后者的链路号256～511、512～767所得的链路号256～767。

图34时一例步骤ST17得到的路径数据，表示出发处为图33的节点Nr0、目的地为图33的节点Nr6时得到的链路Lr00、Lr30组成的路径，与图3的链路L00、L30对应。

路径数据由表示构成链路的数量的链路数、与构成路径的链路对应设置的路径记录组成，路径记录的组成部分包括对应的道路网数据的链路的链路号最小值和最大值、对用所述链路号表示的链路的路径方向。路径记录的路径方向在路径方向与按所述链路号发生对应关系的链路的方向相同时为正向(0)，相反时为反向(1)。

步骤ST18中，获取当前位置数据部12表示的当前位置周边的地图显示、地图核对以及路径引导所需的地图数据，把得到的地图数据存放到地图数据部18、存放的地图数据更新后，进至步骤ST19。

步骤ST19中，利用行驶轨迹数据部11的行驶轨迹数据和地图数据部18中存放的地图数据中的道路网数据，估计该车辆行驶的链路和链路上的位置，从而求出该车辆的当前位置，并将求出的当前位置存放到当前位置数据部12后，进至步骤20。

上述链路的估计、链路上位置的估计，可根据上述行驶轨迹数据与链路或连接的链路的形状的关系进行，并通过引用连接链路信息、链路间通行规则信息、单向通行信息，使链路估计精度进一步提高。

上述处理中，从链路记录的始点节点号所对应的节点附加记录中存放的节点坐标取得链路的始点节点的坐标值，从链路记录的链路形状信息取得链路的插补点的坐标值，从后方链路的链路记录的始点节点号所对应的节点附加记录中存放的节点坐标取得链路的终点节点的坐标值，从而得到表示链路的形状的坐标值。

不能规定链路时，将行驶轨迹数据部11的最新位置信息作为当前位置存放到当前位置数据部12。

步骤ST20中，在输出装置6显示由道路、背景、名称组成的地图画面，该画面按照地图数据部18存放的地图数据中的道路网数据、背景数据、名称数据描绘成运作控制数据部10表示的显示缩小比例尺的尺寸。然后，进至步骤21。

基于所述道路网数据的道路的画面描绘中，根据链路串记录的链路串类别决定道路的描绘彩色、宽度，按所述描绘彩色、宽度画出从链路记录的始点节点号所对应的节点附加记录取得的节点坐标和从链路附加记录取得的链路形状信息表示的折线。

步骤ST21中，在相当于步骤ST20中显示的地图画面上的当前位置数据部12表示的当前位置的部位显示表示当前位置的图形后，进至步骤22。

步骤ST22中，在步骤ST20中显示的地图画面上，增强显示成能将步骤ST17所得的路径数据表示的路径判别为路径，并且在所述路径显示后进至步骤23。

步骤ST23中，调查处在步骤ST19所得的该车辆行驶的链路的前方的节点的节点记录的有无路径引导信息，有对应的路径引导记录，则根据路径引导数据的该路径引导记录，由输出装置6进行所述节点涉及的引导画面显示、声音引导。

对于图34的路径数据，车辆在图3中往节点N1行驶链路L00时，根据图13的节点N1的节点记录#1的有无路径引导信息可知存在路径引导记录，从而以节点N1的节点号为关键字检索图16的路径引导数据，找到路径引导记录的相应节点号与节点N1的节点号1一致的路径引导记录#0，由输出装置6根据路径引导记录#0进行引导画面显示、声音引导。

上述处理后，返回步骤ST11，其后重复上述步骤ST11～ST23。

上文所述那样，使用根据更新用DVD-ROM存储的地图更新信息更新的地图数据，进行地图显示、地图核对、路径计算、路径引导等地图信息处理。

图35是图31的步骤ST16的路径计算数据获取、更新的详细流程图。步骤ST100中，求出获得运作控制数据部10表示的出发处到目的地的较佳路径用的路径计算所需的各路径计算数据的层、区，作为所需路径计算管理数据存放到所需路径计算数据管理部14后，进至步骤ST101。

步骤ST101中，从地图信息存储装置3的地图信息中读取所需路径计算数据管理部14的所需路径计算管理数据表示的路径计算数据，存放到路径计算数据部15后，进至步骤ST102。

步骤ST102中，如果地图信息存储装置3没有存放地图更新信息，进至步骤ST105，存放该信息，则根据地图信息存储装置3的地图更新信息的地图更新管理信息调查是否存在与步骤ST101中取得的路径计算数据同层、同区的路径计算更新数据，如果不存在，进至步骤ST105，存在，则进至步骤ST103。

步骤ST103在地图信息存储装置3存储的路径计算更新数据中读取地图更新信息的与步骤ST101取得的路径计算数据同层、同区的路径计算更新数据，存放到路径计算更新数据部16后，进至步骤ST104。

步骤ST104中，利用路径计算更新数据部16的步骤104中获得的路径计算更新数据更新路径计算数据部15的步骤103中获得的路径计算数据后，进至步骤ST105。

步骤ST105中，调查所需路径计算数据管理部14的路径计算管理数据表示的全部所需路径计算数据的读取是否结束，如果结束，使路径计算数据获取、更新处理结束，没有结束，则返回步骤ST101，重复步骤ST101～ST105。

图36是图31的步骤ST18的地图数据获取、更新的详细流程图。步骤ST200中，求出当前位置数据部12表示的当前位置周边的地图显示、地图核对、路径引导所需的各地图数据的层、区，作为所需地图管理数据存放到所需地图数据管理部17后，进至步骤ST201。

步骤ST201从地图信息存储装置3的地图信息中读取所需地图数据管理部17的所需地图管理数据表示的地图数据，存放到地图数据部18后，进至步骤ST202。

步骤ST202中，如果地图信息存储装置3中没有存放地图更新信息，进至步骤ST209，存放该信息，则根据地图信息存储装置3的地图更新信息的地图更新管理信息调查是否存在与步骤ST201取得的地图数据同层、同区的地图更新数据，如果不存在，进至步骤ST209，存在该数据，则进至步骤ST203。

步骤ST203中，从地图信息存储装置3的地图更新信息中读取与步骤ST201取得的地图数据同层、同区的地图更新数据，存放到地图更新数据部19后，进至步骤ST204。

步骤ST204中，根据地图更新数据部19的在步骤293得到的地图更新数据的道路网更新数据对地图数据部18的在步骤201得到的地图数据的道路网数据进行更新后，进至步骤ST205。

步骤ST205中，根据地图更新数据部19的在步骤203得到的地图更新数据的背景更新数据对地图数据部18的在步骤201得到的地图数据的背景数据进行更新后，进至步骤ST206。

步骤ST206中，根据地图更新数据部19的在步骤203得到的地图更新数据的名称更新数据对地图数据部18的在步骤201得到的地图数据的名称数据进行更新后，进至步骤ST207。

步骤ST207中，根据地图更新数据部19的在步骤203得到的地图更新数据的路径引导更新数据对地图数据部18的在步骤201得到的地图数据的路径引导数据进行更新。

根据图30的路径引导更新数据中的更新记录#g0，删除图16的路径引导数据的路径引导记录#0，根据更新记录#g1，在图16的路径引导数据中添加更新记录#g1的更新操作数列表内的路径引导记录#2，从而将图16的路径引导数据更新到图26的路径引导数据。

对上述更新，如图26的路径引导记录#1那样，已有的路径引导记录的相应节点没有变化，因而路径引导数据的更新不影响道路网数据，道路网数据不产生更改。

上述处理后，进至步骤ST208。

步骤ST208中，结合上述道路网数据、背景数据、名称数据、路径引导数据的更新，对所述地图数据的地图数据首部进行更新后，进至步骤ST209。

步骤ST209中，调查所需地图数据管理部17的地图管理数据表示的全部地图数据的读取是否结束，如果结束，使地图数据获取、更新处理结束，该读取没有结束，则返回步骤ST201，重复步骤ST201～ST209。

图37使图36的步骤ST204的道路网更新的详细流程图。步骤ST300中，从地图更新数据部18的在步骤203得到的地图更新数据中的道路网更新数据取得更新记录后，进至步骤ST301。

步骤ST301中，按照更新操作类别，用更新操作数列表的数据更新步骤ST300获得的更新记录的更新对象实体类别、更新对象数据类别、更新对象实体指定所决定的部分道路网数据，并更新随上述更新变化的节点附加首部、链路串附加首部、链路附加首部。以下的说明中，对节点附加首部、链路串附加首部、链路附加首部的更新省略其说明，但结合更新内容进行适当更新。

图29的道路网更新数据中，对更新记录#r0，在更新操作数列表的有无引导信息(＝0(无引导))上盖写节点号1的节点N1的图13所示的节点记录#1的有无引导信息，作为图22的节点记录#1。

对更新记录#r1，删除节点号2的节点N2的图14的节点附加记录#2的链路间通行规则信息的通行规则记录号1的通行规则记录R21，并随着所述删除，改变节点附加记录首部的节点附加记录规模、通行规则记录数量。

对更新记录#r2，在图14的节点附加记录#2的链路间通行规则信息中添加更新操作数列表的通行规则记录R22。

上文那样，利用更新记录#r1、#r2更新链路间通行规则信息，如图23的节点附加记录#2所示。

对更新记录#r3，将节点号5的节点N5的图13的节点记录#5的节点状态改为1(废弃)，并删除图5的上述节点的节点附加记录#5。

对更新记录#r4、更新记录#r5，在图5的节点表末尾添加更新操作数列表的节点记录#8、节点记录#r9，在图5的节点附加列表末尾添加更新操作数列表的节点附加记录#8、节点附加记录#r9。

上文那样，利用更新记录#r3、#r4、#r5可得图1 8的节点表、图22的节点记录、图18的节点附加列表、图23的节点附加记录#8、节点附加记录#9。但是，这时不存放节点附加记录#8、节点附加记录#9的连接链路记录C80、C90。

又，对更新记录#r6，使图10的链路串号0的链路串0中的链路串内链路号0的链路L00的链路记录#0的链路状态为2(划分)，划分链路号为更新操作数列表所示的划分链路号5，将链路有无附加信息改为0(无附加)，并删除图10的上述链路的链路附加记录#0。

对更新记录#r7，使图10的链路串号0的链路串0中的链路串内链路号1的链路L01的链路记录#1的链路状态为0(废弃)，将链路有无附加信息改为0(无附加)，并删除图10的上述链路的链路附加记录#0。

上文那样，利用更新记录#r6、#r7，可将链路串0的链路附加记录更新为图21所示的链路附加记录。

又，对更新记录#r8，将图9的链路串号2的链路串2的链路串记录#2的链路串状态改为0(废弃)，并删除图6的链路串2的链路串附加记录#2。

对更新记录#r9、更新记录#r10，在图6的链路串表末尾添加更新操作数的链路串记录#4、链路串记录#5，在图6的链路串附加列表末尾添加链路串附加记录#4、链路串附加记录#5。由此，图17的链路串4、链路串5的链路串号分别成为4、5。

上文那样，利用更新记录#r8、#r9、#r10，可得图19的链路串表、图20的链路串记录、图19的链路串附加列表、图24的链路串5的链路串附加记录。

上述处理后，进至步骤302。

步骤ST302中，由于废弃或划分链路而节点上连接的正向链路及其前方链路不存在时，删除示出所述正向链路的连接链路记录。但是，废弃所述节点的节点状态时，节点附加记录不存在，因而不进行连接链路记录的删除。

步骤ST300所得的更新记录表示链路串始端的链路废弃或划分时，删除更新记录表示的链路始点节点的节点附加记录的连接链路信息中的示出所示废弃的链路的连接链路记录。

更新记录表示链路废弃或划分而且先前的步骤ST300所得的更新记录表示所述链路的前方链路废弃或划分时，删除更新记录表示的链路的始点节点的节点附加记录的连接链路信息中的所述链路的连接链路记录。

更新记录表示链路串废弃时，对包含所述链路串的假想链路的各链路删除所述链路的始点节点的节点附加记录中的连接链路信息的所述链路的连接链路记录。

对图29的更新记录#r6，所述更新记录表示划分链路串0的始端链路L00，因而利用链路L00的图10的链路记录#0表示的始点节点号(＝0)，求出链路L00的始点节点N0，并删除节点N0的图14的节点附加记录#0中表示链路L00的连接链路记录C00。

对图29的更新记录#r7，所述更新记录表示废弃链路串0的链路L01，并且上次取得的图29的更新记录#r6表示划分链路L01的前方链路(即链路串0的链路L00)，因而从链路L01的链路记录的始点节点号求出始点节点N1，并删除节点N1的图14的节点附加记录#1中表示链路L01连接链路记录C1 0。

对图29的更新记录#r8，所述更新记录表示废弃链路串2，从各自的链路记录的始点节点号分别求出链路串2的链路L20、假想链路L20’的始点节点N2、N5，删除始点节点N2的图14的节点附加记录#2中表示链路L20的连接链路记录C22。始点节点由于被废弃，不进行连接链路记录的删除。

上述处理后，进至步骤ST303。

步骤ST303中，步骤ST300所得的更新记录表示显示链路串时，对新设的链路串的各链路，在链路的始点节点的节点附加记录中的连接链路信息上添加表示所述链路的连接链路记录。

而且，对添加的连接链路记录的节点单元链路号存放没有作为已有的连接链路记录的节点单元链路号使用的最小编号。

对图29的更新记录#r10，利用步骤301中得到的链路串5的图19、图24的链路串附加记录#5中的链路L50、L51、L51’的链路记录的始点节点号，求出它们的始点节点N0、N9、N1，在步骤301所得的图19的节点附加列表中的节点N0、N9、N1的节点附加记录#0、1、9的连接链路信息的末尾添加表示链路L50、L51、L51’的连接链路记录。由此，获得添加表示链路L50、L51、L51’的连接链路记录C01、C90、C12的图23的连接链路记录#0、#1、#9。

这时，对连接链路记录C12的连接链路串号存放链路串5的链路串号5，对连接链路串内链路号存放链路L50的链路串内链路号0，对节点单元链路号存放本步骤处理时存在的连接链路记录C11使用的编号1以外的最小值(即0)。对连接链路记录C01、C90也同样地进行存放。

对图29的更新记录#r9，也与上文相同，在节点N2、N7、N8的节点附加记录(即图19的节点附加记录#2、#7、#8)的连接链路信息的末尾添加表示链路L40、L41、L41’的连接链路记录。由此，获得添加表示链路L40、L41、L41’的连接链路记录C23、C71、C80的图23的节点附加记录#2、#7、#8。

上述处理后，进至步骤ST304。

步骤ST304中，根据上述道路网更新数据，调查是否全部更新记录获取结束，如果结束，进至步骤ST305，没有结束，则返回步骤ST300，重复步骤ST300至ST304。

步骤ST305中，对上述更新记录的更新结果以及更新后的链路串附加记录，参照有无链路附加记录信息，存放具有链路附加记录的链路记录的链路附加指针所对应的链路附加记录的地址。通过对从链路附加列表始端到对应的链路附加记录前所存放的各链路附加记录中的链路附加首部的链路附加记录规模进行累加，求出所述地址。

上述处理后，进至步骤ST306。

步骤ST306中，结合上述更新记录的更新结果，更新所述道路网数据的道路网数据首部，从而结束道路网数据更新。

利用上述步骤ST300～ST306，将作为表示图3的道路网的道路网数据的图5、图6、图9、图10、图13、图14的数据更新为表示图17的道路网的道路网数据，即图18、图19、图20、图21、图22、图23、图24所示的数据。

图38是图31的步骤ST22的路径显示的详细流程图。步骤ST400中，从步骤ST17所得的路径数据按其排列顺序取出1个路径记录后，进至步骤ST401。

步骤ST401中，规定具有步骤ST400中取得的路径记录的链路号最小值、最大值包含的链路号的链路。

不更新地图数据时，对图32的路径记录#0，根据图3的道路网所对应的图6的链路串表、链路串附加列表，规定链路号0～255的链路L00，从而得到图10的链路L00的链路记录#0、链路附加记录#0。对图34的路径记录#1，也同样地规定链路号1280～1535的链路L30，获得其链路记录、链路附加记录。

更新地图数据时，对图32的路径记录#0，根据图17的道路网所对应的图19的链路串表、链路串附加列表，规定链路号0～255的链路L00，从而得到图21的链路L00的链路记录#0、链路附加记录#0。对图34的路径记录#1，也同样地规定链路号1280～1535的链路L30，获得其链路记录、链路附加记录。

上述处理后，进至步骤ST402。

步骤ST402中，证实步骤ST401规定的链路的链路记录的链路状态是否延续，如果是延续，进至步骤ST403，不是延续，则进至步骤ST404。

不更新地图数据时，对图34的路径记录#0，由于链路L00的图10的链路记录#0的链路状态是延续，进至步骤ST403；更新地图数据时，对图34的路径记录#0，由于链路L00的图21的链路记录#0的链路状态是划分，进至步骤ST404。

对图34的路径记录#1，由于对应链路L30延续，进至步骤ST403。

步骤ST 403中，根据步骤ST401中规定的链路及其后方链路的链路记录始点节点号，求出步骤ST401中规定的链路两端的节点的节点号，又从节点表、节点附加表取得所述链路两端的节点的节点坐标，根据步骤ST401中规定的链路的链路附加记录取得链路形状信息，用取得的节点坐标、链路形状信息在步骤ST20中显示的地图画面上增强显示步骤ST401规定的链路的形状。

不更新地图数据时，对图34的路径记录#0，根据图14的节点附加记录#1、节点附加记录#2和链路L00的图10中的链路附加记录#0分别利用节点N0、N1的节点坐标(x0，y0)、(x1，y1)和链路形状信息si00，在所述地图画面上增强显示链路L00的形状。

对图34的路径记录#1，与上文同样地显示对应的链路L30的形状。

上述处理后，进至步骤ST404。

由步骤ST402、ST403在路径所对应的链路上显示延续的链路的形状。

步骤ST404中，证实步骤ST401中规定的链路记录的链路形状是否划分，如果划分，进至步骤ST405，不划分，则进至步骤ST406。

不更新地图数据时，对图34的路径记录#0，由于链路L00的图10的链路记录#0的链路状态为延续，进至步骤ST406；更新地图数据时，对图34的路径记录#0，由于链路L00的图21的链路记录#0的链路状态为划分，进至步骤ST405。

对图34的路径#1，由于对应的链路L30延续，进至步骤ST406。

步骤ST405中，在步骤ST20中显示的地图画面上增强显示步骤ST401规定的链路的链路记录中的划分链路号表示的链路串的各链路的链路形状。

更新地图数据时，对图34的路径记录#0，根据链路L00的图21的链路记录#0的划分链路串号，求出链路串号5的链路串5，并利用链路串5的图20中的链路串记录#5和链路串5的图24的链路串附加记录，与步骤ST403同样地在所述地图画面上显示链路L50、L51的链路形状。这样，即使划分链路L00，也不改变授予链路L00所对应的路径计算数据的链路(即图33的链路Lr00)的链路号，从而能保持链路的对应关系，可正确显示路径。

上述处理后，进至步骤ST406。

利用所述步骤ST404、ST405，在路径所对应的链路上显示划分后得到的链路的形状。

步骤ST406中，证实是否从路径数据获取完全部路径数据，如果未完，返回步骤ST400，重复上述步骤ST400～ST406，取完则结束路径显示。

上文那样，显示路径数据表示的路径所对应的链路的形状。又，根据链路状态、划分链路串号判明划分链路，同时直接判明该划分链路串的链路串记录的存放位置，因而即使划分链路时也快速显示路径。

图38是链路划分为一次时的例子，但链路划分为多次时，通过对划分链路串的各链路递归进行步骤ST402～ST405，也能显示路径。

实施方式1的地图数据做成上述那样的数据结构，因而使节点数据与链路串数据分开，存放到节点表、节点附加列表，因而不重复存放相同的节点数据，不必对相同的节点数据重复更新，具有能获得便于更新的地图数据的效果；通过将节点号用作节点标识符，具有能快速掌握节点数据的效果；又具有可利用存放所述数据结构的地图数据的媒体对地图信息处理装置提供更新方便且地图信息处理速度较高的地图数据的效果；通过使用存放在上述媒体的地图数据，使处理负载较轻，可使地图数据更新较快，具有能获得可使地图信息处理速度较高的地图信息处理装置的效果。

又，利用表示节点的正向链路的连接链路记录组成的连接链路信息表示节点连接的链路，因而能对伴随链路废弃、新设的连接链路信息更新进行连接链路记录删除、添加的简单处理，可获得便于更新的地图数据，并且由于仅设置表示节点正向链路的连接链路记录，具有能减小地图数据的数据规模的效果。又具有可利用存放所述数据结构的地图数据的媒体对地图信息处理装置提供更新方便的地图数据的效果；通过使用存放在上述媒体的地图数据，使处理负载较轻，具有能获得可使地图数据更新速度较快的地图信息处理装置的效果。

又，使用链路串号、链路串内链路号作为连接链路记录的连接链路规定信息，因而直接可知节点连接的链路的链路记录的地址，具有可获得能快速取得有关链路的信息的地图数据的效果，并且通过使用所述地图数据，使处理负载减轻，具有能获得可使地图数据更新速度较高的地图信息处理装置的效果。

又，授予节点连接的正向链路节点单元链路号，作为节点单元链路标识，因而能授给链路存在期间不变的节点单元链路号，已有的通行规则记录不必因其它链路的废弃、新设而改变其内容，具有可获得便于更新的地图数据的效果，并且通过使用所述地图数据，使处理负载减轻，具有能获得可使地图数据更新速度较高的地图信息处理装置的效果。

又，对链路的划分设置划分链路串，并且在链路记录设置有关链路划分的信息，即设置表示划分链路的链路状态、表示划分链路串的划分链路串号，因而可划分链路而不使划分的链路及其后的链路的链路串内链路号变化，能快速取得划分链路串的链路串记录、链路串附加记录，具有能得到可获得便于更新的地图数据，同时具有可以得到能使路径显示等快速显示的地图数据的效果，并且通过使用所述地图数据，使处理负载减轻，具有能获得可使地图数据更新速度较高、路径显示等可快速显示的地图信息处理装置的效果。

又，存放与链路引导记录之类的节点关联信息对应的节点号，因而不发生伴随节点关联信息更新的地图数据更新，具有能获得便于更新的地图数据的效果，并且通过使用所述地图数据，使处理负载减轻，具有能获得可使地图数据更新速度较高的地图信息处理装置的效果。

又，将授予划分前链路的链路号分配给划分后的链路，并根据等分划分前链路的链路号范围所得的范围，决定由分配得到的划分后链路的链路号范围，因而对哪条链路都能划分规定的次数，具有能获得链路划分时更新方便的地图数据的效果，并且具有可以利用存放上述数据结构的地图数据的媒体向地图信息处理装置提供便于更新的地图数据的效果，另外，通过使用存放于所述媒体的地图数据，使处理负载减轻，具有能获得可使地图数据更新速度更高的地图信息处理装置的效果。

又，作为废弃、新设节点时的地图数据更新方法，做成已有的节点的节点号不变，因而不必改变已有的链路记录的始点节点号，并且不必改变已有的路径引导记录，具有能速度较高地进行地图数据更新的效果。

又，作为废弃、新设链路时的地图数据更新方法，做成已有的链路串、链路的链路串号、链路串内链路号不变，因而不必改变已有的连接链路记录，地图数据更新容易完成，具有能速度较高地进行地图数据更新的效果。

又，作为链路串新设时的地图数据更新方法，根据新设的链路串的链路串数据，编制新设的链路串的链路连接的节点的连接链路记录，因而不需要添加连接链路记录用的更新记录，具有可用较少的道路网更新数据更新地图数据的效果。

又，作为划分链路串时的地图数据更新方法，做成授予链路一定范围的链路号，并且在划分链路时，授予完成链路划分的链路根据划分前链路的链路号范围的等分决定的范围的编号，因而对哪条链路都能划分规定的次数，具有能速度较高地进行地图数据更新的效果。

实施方式2

实施方式2在实施方式1中，划分链路时，划分后的链路的链路号范围进行分配，使授予划分前的链路的链路号范围与划分后链路的链路长度成正比。

图39示出将图3的链路L00划分成图17的链路L50、L51时授给链路号的例子。图39中，使链路L00的链路一端至另一端的距离(即链路长度)为100m，划分链路L00后得到的链路L50、L51的链路长度分别为25m、75m时，根据链路L50、L51的链路长度对链路L00的链路长度的比，分配授予链路L00的范围0～255的链路号，分别授予链路L50、L51范围0～63、64～255的链路号。

图40示出实施方式2中的链路L00的划分后的链路L50、L51组成的链路串5的链路附加列表的存放例。

实施方式2中的链路串5的链路串附加记录将图24的实施方式1中的链路串5的链路串根据记录的链路附加列表做成图40的链路附加列表。

图40的链路附加列表中，在链路附加记录#1设置值为64的链路号信息，并且链路L50、L51的链路号分别为0～63、64～255。

如图39所示，又将链路L50划分成链路长20m的链路L50-0和链路长5m的链路L50-1时，根据链路L50-0、L51-1的链路长对链路L50的链路长的比，分配授给链路L50的范围0～63，分别授予链路L50-0、L51-1范围0～51、52～63的编号。然而，按照所述的比分配的范围为0～51.2、51.2～63，但链路号为整数，因而对上述范围的小数部分舍去、舍入，使上述范围不重复。

下面，可同样地反复划分，直到不能分配。

根据上述实施方式2，在划分链路中，根据链路长的比分配链路号，因而与地图数据编制最初的链路长度的长短无关，对哪条链路都能作次数程度相同的划分，具有可获得在链路划分时便于更新的地图数据的效果，并且具有能利用存放上述数据结构的地图数据的媒体对地图信息处理装置提供便于更新的地图数据的效果；通过使用所述媒体存放的地图数据，使处理负载减轻，具有能获得可使地图数据更新速度较高的地图信息处理装置的效果。

又，作为划分链路时的地图数据更新方法，做成根据链路长的比分配链路号，因而具有能速度较高地进行地图数据更新的效果。

再者，实施方式1中，采用硬盘作为地图信息存储装置3，但也可用存储卡、光磁盘等可读写存储媒体。

将地图信息存放到地图信息存储装置3的硬盘，但也可将其

存放到CD-ROM(Compact Disc-Read Only Memory：小型光盘只读存储器)、DVD-ROM等读取专用的存储媒体，并设置该存储媒体的读取装置，利用读取装置读取存储媒体的地图信息。

采用DVD-ROM作为地图更新信息的存储媒体，但也可用CD-ROM、存储卡等可读出存储媒体；采用DVD驱动器作为更新信息获取装置，但也可用任意一个适合地图更新信息存储媒体的装置。

通过从地图信息存储装置3读取地图数据，但也可用通信手段从其它装置获取地图数据。

将利用更新信息获取装置4取得的地图更新信息存放到地图信息存储装置3，并从地图信息存储装置3读取地图更新数据，但也可利用更新信息获取装置4从地图更新信息存储媒体读取地图更新数据。

作为更新信息获取装置4，做成从地图更新信息存储媒体取得地图更新信息，但也可用通行手段从其它装置取得地图更新信息。

将利用更新信息获取装置4取得的地图更新信息存放到地图信息存储装置3，并从地图信息存储装置3读取地图更新数据，但也可用通信手段，从其它装置取得地图更新数据。

不在地图信息存储装置3存放更新的地图数据，但也可将更新的数据存放到地图信息存储装置3。

为了指定链路的始点节点，在链路记录中存放始点节点的节点号，但也可存放表示始点节点的节点记录存放位置的信息。

在链路记录中存放链路状态、划分链路串号作为有关划分链路的信息，但也可仅存放链路状态，并将具有链路状态为划分的链路的链路号的链路串作为划分链路串，查找划分链路串。

划分链路时，设置划分链路串，但也可不设置划分链路串，而将划分前的链路置换成划分后的链路。即，在节点表、节点附加记录中添加因划分链路而新产生的节点的节点记录、节点附加记录，将划分前的链路的链路记录、链路附加记录置换成划分后的各链路的链路记录、链路附加记录。

已有的链路串号和链路串内识别号都不因链路串、链路的废弃、新设而变化，但也可使已有的链路串号和链路串内识别号中的至少一个不变。

用路径计算数据进行路径计算，但也可用地图数据的道路网数据进行路径计算。

Claims

1.一种地图数据的数据结构，该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，其特征在于，对将所述道路网的道路连接作为所述链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，赋予所述道路网各节点以识别节点用的节点标识符，并且所述链路数据具有示出根据链路串的方向决定的链路端一个节点的节点标识符的信息。

2.如权利要求1中所述的地图数据的数据结构，其特征在于，该地图数据中，将表示节点数据排列顺序的节点号用作节点标识符。

3.如权利要求1中所述的地图数据的数据结构，其特征在于，该地图数据中，对应于各节点设置表示节点上连接的链路的连接链路信息，所述连接链路信息对应于包含所述链路的链路串设置连接链路规定信息，所述连接链路规定信息规定根据所述链路串的方向从对应的链路串中包含的所述链路中选择的链路。

4.如权利要求2中所述的地图数据的数据结构，其特征在于，该地图数据中，对应于各节点设置表示连接于节点的链路的连接链路信息，所述连接链路信息对应于包含所述链路的链路串设置连接链路规定信息，所述连接链路规定信息规定根据所述链路串的方向从对应的链路串中包含的所述链路中选择的链路。

5.如权利要求3或4中所述的地图数据的数据结构，其特征在于，该地图数据中，连接链路规定信息用授予链路串用于识别链路串的链路串标识符和以取决于链路串方向的方式授予链路用于识别链路串内的链路的链路串内链路标识符表示规定的链路。

6.如权利要求3～5中任一项权利要求所述的地图数据的数据结构，其特征在于，该地图数据中，每一链路串根据链路串的方向从节点上连接的链路选择1条链路，并授予所述链路以识别所述选择的链路用的节点单元链路标识符。

7.如权利要求3～6中任一项权利要求所述的地图数据的数据结构，其特征在于，该地图数据中，划分链路时，设置作为划分完链路所得的链路组成的链路串的划分链路串的链路串数据，并且被划分的链路的链路数据具有涉及所述划分链路串的信息。

8.如权利要求1～7中任一项权利要求所述的地图数据的数据结构，其特征在于，该地图数据中，设置节点关联信息，使其与节点关联，并且该节点关联信息具有关联的节点的节点标识符。

9.一种地图数据的数据结构，该地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路以固有范围的链路号，其特征在于，将授予划分前的链路的所述范围的链路号分配给划分后的链路，并根据等分所述划分前的链路的链路号的范围所得的范围，决定所述分配获得的划分后的链路的链路号的范围。

10.一种地图数据的数据结构，该地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路以固有范围的链路号，其特征在于，将授予划分前的链路的所述范围的链路号分配给划分后的链路，并根据所述划分前的链路的链路长度与所述划分后的链路的链路长度之比，决定所述分配获得的划分后的链路的链路号范围。

11.一种地图数据更新方法，该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，对将所述道路网的道路连接作为链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点以识别节点用的节点标识符，将表示节点数据排列顺序的节点号用作所述节点标识符，并且所述链路数据具有示出根据链路串方向决定的链路端一个节点的节点标识符的信息，其特征在于，废弃或新设节点时，进行更新，使已有的继续存在的节点的节点标识符不变。

12.一种地图数据更新方法，该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，对将所述道路网的道路连接作为链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点以识别节点用的节点标识符，在所述链路数据中设置示出根据链路串的方向决定的链路端的一个节点的节点标识符的信息，对应于所述道路网的各节点设置表示节点上连接的链路的连接链路信息，所述连接链路信息根据对应于包含所述链路的链路串设置连接链路规定信息，所述连接链路规定信息规定根据所述链路串的方向从对应的链路串中包含的所述链路中选择的链路，所述连接链路规定信息用授予链路串用于识别链路串的链路串标识符和以取决于链路串方向的方式授予链路用于识别链路串内的链路的链路串内链路标识符表示规定的链路，其特征在于，在废弃或新设节点时进行更新，使已有的继续存在的链路串的链路串标识符和已有的继续存在的链路的链路串内链路标识符中的至少一种标识符不变。

13.一种地图数据更新方法，该地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，对将所述道路网的道路连接作为链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点以识别节点用的节点标识符，所述链路数据中设置示出根据链路串方向决定的链路端一个节点的节点标识符的信息，对应于所述道路网的各节点设置表示节点上连接的链路的连接链路信息，所述连接链路信息对应于包含所述链路的链路串设置连接链路规定信息，所述连接链路规定信息规定根据所述链路串的方向从对应的链路串中包含的所述链路中选择的链路，所述连接链路规定信息用授予链路串用于识别链路串的链路串标识符和以取决于链路串方向的方式授予链路用于识别链路串内的链路的链路串内链路标识符表示规定的链路，其特征在于，在废弃或新设链路时，用更新后所得的链路串数据更新所述连接链路信息。

14.一种地图数据更新方法，该地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路以固有范围的链路号，其特征在于，将授予划分前的链路的所述范围的链路号分配给划分后的链路，并根据等分所述划分前的链路的链路号的范围所得的范围，决定所述分配获得的划分后的链路的链路号的范围。

15.一种地图数据更新方法，该地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路固有范围的链路号，其特征在于，将授予划分前的链路的所述范围链路号分配给划分后的链路，并根据所述划分前的链路的链路长度与所述划分后的链路的链路长度之比，决定通过所述分配获得的划分后链路的链路号范围。

16.一种地图数据存储媒体，其特征在于，存储的地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，对将所述道路网的道路连接作为所述链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点以识别节点用的节点标识符，将表示节点数据排列顺序的节点号用作所述节点标识符，并且所述链路数据具有示出根据链路串方向决定的链路端一个节点的节点标识符的信息。

17.一种地图数据存储媒体，其特征在于，存储的地图数据用示出有关表示道路上的地点的节点的信息的节点数据和示出有关表示所述地点间的道路的链路的信息的链路数据表示道路网，对将所述道路网的道路连接作为所述链路的连接表示的链路串，设置根据链路连接顺序配置构成所述链路串的链路的链路数据的链路串数据，与链路串数据分开另行设置所述道路网各节点的节点数据，授予所述道路网各节点以识别节点用的节点标识符，将表示节点数据排列顺序的节点号用作所述节点标识符，所述链路数据上设置示出根据链路串方向决定的链路端一个节点的节点标识符的信息，对应于所述道路网的各节点设置表示节点上连接的链路的连接链路信息，所述连接链路信息对应于包含所述链路的链路串设置连接链路规定信息，所述连接链路规定信息规定根据所述链路串的方向从对应的链路串中包含的所述链路中选择的链路。

18.一种地图数据存储媒体，其特征在于，存储的地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路以固有范围的链路号，将授予划分前链路的所述范围的链路号分配给划分后的链路，并根据等分所述划分前的链路的链路号的范围所得的范围，决定通过所述分配获得的划分后的链路的链路号范围。

19.一种地图数据存储媒体，其特征在于，存储的地图数据用表示道路上的地点的节点和表示所述地点间的道路的链路表示道路网，并分别授予所述道路网的各链路以固有范围的链路号，在存储的地图数据中，将授予划分前的链路的所述范围的链路号分配给划分后的链路，并根据所述划分前的链路的链路长度与所述划分后的链路的链路长度的之比，决定通过所述分配获得的划分后链路的链路号范围。

20.一种地图信息处理装置，其特征在于，具有获取具有权利要求1～10中任一项权利要求所述的数据结构的地图数据的地图数据获取手段、获取更新所述地图数据用的地图更新数据的地图更新数据获取手段、以及用所述地图更新数据手段获取的地图更新数据更新所述地图数据获取手段获取的地图数据的地图数据更新手段。

21.一种地图信息处理装置，其特征在于，具有读取权利要求16～19中任一项权利要求所述的地图数据存储媒体中存储的地图数据的地图数据读取手段、获取更新所述地图数据存储媒体中存储的地图数据用的地图更新数据的地图更新数据获取手段、以及用所述地图更新数据手段获取的地图更新数据更新所述地图数据读取手段读取的地图数据的地图数据更新手段。