用于基于地图数据来执行处理的电子设备

摘要

一种用于基于地图数据来执行处理的电子设备包括：地图数据存储器(13)；工作存储器(19c)；以及CPU(19a)，用于将来自所述地图数据存储器的地图数据发展到所述工作存储器内。该CPU基于经发展的地图数据来执行所述处理。所述地图数据提供了道路网络，所述道路网络是通过单元链路和链路连接关系来定义的，并且所述地图数据包括在每一个链路中的属性数据。所述CPU根据所述属性数据来产生节点表。所述节点表存储在作为与链路耦合的连接点的每一个节点中的链路连接信息。所述链路连接信息提供了在对应节点处彼此耦合的链路的标识。所述CPU将作为经发展的地图数据的节点表写入所述工作存储器内。

权利要求

1.一种用于基于地图数据来执行处理的电子设备，包括：地图数据存储器（13），用于存储所述地图数据，其中，所述地图数据不包括描述道路网络的节点的节点数据；

工作存储器（19c）；以及

CPU（19a），用于从所述地图数据存储器（13）读出所述地图数据，并且用于将所述地图数据发展到所述工作存储器（19c）内作为经发展的地图数据，其中，所述CPU（19a）基于在所述工作存储器（19c）中的经发展的地图数据来执行所述处理，其中，在所述地图数据存储器（13）中的所述地图数据提供了道路网络，所述道路网络是通过多个单元链路和多个链路连接关系来定义的，其中，每一个链路表示道路的一部分，

其中，每一个链路连接关系表示在连接点处的链路之间的连接，其中，所述地图数据包括在每一个链路中的属性数据，其中，所述属性数据提供了对应链路的属性和所述对应链路的端部的属性，其中，所述端部的所述属性包括在所述端部处的所述对应链路的连接关系信息，其中，所述CPU（19a）根据来自不包括节点数据的所述地图数据的所述属性数据来产生节点表，其中，所述节点表存储在作为与多个链路耦合的所述连接点的每一个节点中的链路连接信息，其中，所述链路连接信息提供了在对应节点处彼此耦合的所述多个链路的标识，以及其中，所述CPU（19a）将作为经发展的地图数据的所述节点表写入所述工作存储器（19c）内。

2.根据权利要求1所述的电子设备，

其中，在对应链路的端部处的所述对应链路的连接关系信息示出仅一个链路，所述仅一个链路为在与所述对应链路的所述端部耦合的一组其他链路中选择的连接目标链路。

3.根据权利要求1或2所述的电子设备，

其中，所述处理包括多个应用程序，

其中，所述CPU（19a）基于在所述工作存储器（19c）中的经发展的地图数据来执行每一个应用程序，其中，所述节点表包括多个专用节点表，其中每一个所述专用节点表对应于相应的应用程序，其中，所述CPU（19a）产生作为经发展的地图数据的一部分的每一个专用节点表，并且将所述专用节点表写入所述工作存储器（19c）中，其中，每一个专用节点表包括对于对应应用程序可用的关于每一个节点的信息，以及其中，关于对应节点的信息包括所述链路连接信息。

4.根据权利要求3所述的电子设备，

其中，所述CPU（19a）根据所述属性数据来产生多个专用链路表，其中，每一个专用链路表对应于相应的应用程序，

其中，每一个链路表存储与相应的应用程序对应的在每一个链路中的专用链路属性，其中，所述CPU（19a）从在所述属性数据中的对应链路的属性来获取用于对应应用程序的关于每一个链路的信息，以便产生所述专用链路属性，并且其中，所述CPU（19a）将所述多个专用链路表和所述多个专用节点表作为经发展的地图数据写入所述工作存储器（19c）内。

5.根据权利要求4所述的电子设备，

其中，每一个应用程序包括任务，

其中，所述CPU（19a）响应于来自在一个应用程序中的任务的请求，来产生与所述一个应用程序对应的一个专用链路表和对应的专用节点表。

6.根据权利要求1或2所述的电子设备，

其中，所述处理包括多个应用程序，

其中，所述CPU（19a）基于在所述工作存储器（19c）中的经发展的地图数据来执行每一个应用程序，其中，所述节点表包括公共节点表和多个专用节点表，其中，所述公共节点表包括共用于所述多个应用程序的信息，其中，每一个专用节点表对应于相应的应用程序，

其中，所述CPU（19a）产生作为经发展的地图数据的一部分的所述公共节点表和所述多个专用节点表的每一个，并且将所述公共节点表和所述多个专用节点表的每一个写入所述工作存储器（19c）中，其中，所述公共节点表包括对于所述多个应用程序可共用的关于每一个节点的信息，其中，在所述公共节点表中的关于对应节点的信息包括所述链路连接信息，并且其中，每一个专用节点表包括对于对应应用程序可用的关于每一个节点的信息，而非在所述公共节点表中的关于对应节点的信息。

7.根据权利要求6所述的电子设备，

其中，所述CPU（19a）根据所述属性数据来产生多个专用链路表，其中，每一个专用链路表对应于相应的应用程序，

其中，每一个链路表存储与相应的应用程序对应的在每一个链路中的专用链路属性，其中，所述CPU（19a）从在所述属性数据中的对应链路的属性来获取用于对应应用程序的关于每一个链路的信息，从而产生所述专用链路属性，以及其中，所述CPU（19a）将作为经发展的地图数据的所述多个专用链路表、所述公共节点表和所述多个专用节点表写入所述工作存储器（19c）内。

8.根据权利要求7所述的电子设备，

其中，每一个应用程序包括任务，

其中，所述CPU（19a）响应于来自在一个应用程序中的任务的请求，来产生与所述一个应用程序对应的一个专用链路表和对应的专用节点表。

说明书

用于基于地图数据来执行处理的电子设备

技术领域

[0001] 本发明涉及用于基于地图数据来执行处理的电子设备。

背景技术

[0002] 传统上，用于基于地图数据来执行处理的电子设备例如是在对应于US2008/0243368的JP-A-2008-241659中公开的车载设备，诸如导航设备。车载设备在显示设备上显示地图图像，搜索到目的地的引导路线，并且引导该路线或引导在车辆的当前位置周围的道路。地图数据的格式例如是在下文中公开的KIWI格式：“Map data format KIWI for a vehicle navigation system,”in DENSO Technical Review,2001,on Volume6,Part1,pages29-34。在使用这种格式的情况下，道路数据被示出为链路和节点。在地图数据中存储了每一个链路的链路数据，用于表示链路属性，诸如链路的形状和街道地址。

[0003] 在传统的地图数据中，在每一个链路中分配唯一的链路ID。链路ID用于将与链路ID对应的链路数据与其他数据链接。例如，链路ID用于表示链路的连接关系，在传统的地图数据中，例如，多个链路数据被整合为链路序列数据。链路序列数据包括节点数据，用于使用链路ID示出链路的连接关系。节点数据涉及用于连接链路的节点。此外，在节点数据中存储与在对应于节点的交叉位置处的交通信号的存在以及诸如右转和/或左转禁止的交通规则相关的信息。

[0004] 在此，传统的地图数据包括与链路相关的链路数据和与节点相关的节点数据，因此，传统的地图数据包括关于成双地在地图数据中保存的链路数据和节点数据的坐标的信息。因此，本发明人认为作为节点数据存储的信息可以被分布和存储在链路数据中，从而可以删除节点数据。

[0005] 然而，在地图数据中，当删除节点数据，并且先前作为节点数据存储的关于链路的连接关系的信息被分布到链路数据并且被存储为链路数据的时候，需要参考多个链路数据，从而获得诸如链路连接关系的、与节点相关的信息。

[0006] 因此，当地图数据不包括节点数据时，用于检测诸如在节点的链路连接关系的节点条件的处理的负荷增大。

发明内容

[0007] 根据上述问题，本公开的目的是提供一种用于基于地图数据来执行处理的电子设备。在地图数据中，关于节点的信息被分布和存储在链路数据中，并且用于基于地图数据来处理与节点相关的信息的负荷减少。

[0008] 根据本公开的一个方面，一种用于基于地图数据来执行处理的电子设备包括：地图数据存储器，用于存储所述地图数据，其中，所述地图数据不包括描述道路网络的节点的节点数据；工作存储器；以及CPU，用于从所述地图数据存储器读出所述地图数据，并且用于将所述地图数据发展到所述工作存储器内作为经发展的地图数据。所述CPU基于在所述工作存储器中的经发展的地图数据来执行所述处理。在所述地图数据存储器中的所述地图数据提供了道路网络，所述道路网络是通过多个单元链路和多个链路连接关系来定义的。每一个链路表示道路的一部分。每一个链路连接关系表示在连接点处的链路之间的连接。
所述地图数据包括在每一个链路中的属性数据。所述属性数据提供了对应链路的属性和所述对应链路的端部的属性。所述端部的属性包括在所述端部的所述对应链路的连接关系信息。所述CPU根据来自不包括节点数据的所述地图数据的所述属性数据来产生节点表。所述节点表存储在作为与多个链路耦合的连接点的每一个节点中的链路连接信息。所述链路连接信息提供了在对应节点处彼此耦合的所述多个链路的标识。所述CPU将作为经发展的地图数据的所述节点表写入所述工作存储器内。

[0009] 在上面的设备中，当在所述工作存储器中发展所述地图数据时，所述CPU产生用于示出在对应节点处的所述链路连接关系的链路连接信息，并且产生用于存储所述链路连接信息的所述节点表。因此，即使所述地图数据不包括所述节点数据，并且在每一个链路的所述属性数据中分布和描述所述链路连接信息，所述CPU也可以根据所述节点表来指定在每一个节点处的所述链路连接关系。因此，因为所述CPU参考所述节点表，所以用于所述节点的处理负荷被限制。因此，即使当所述地图数据被紧凑化时，也提高了与所述节点相关的处理性能。

附图说明

[0010] 通过下面参考附图进行的详细描述，本发明的上述和其他目的、特征和优点将变得更清楚。在附图中：

[0011] 图1是示出地图数据的结构的图；

[0012] 图2是示出用于提供基本数据或扩展数据的整合文件的结构的图；

[0013] 图3是示出在道路数据中的网格单元数据的结构的图；

[0014] 图4A是示出道路数据的链路记录的结构的图，并且图4B是示出道路数据的坐标记录的结构的图；

[0015] 图5A和5B是示出在道路数据管理记录、链路记录和坐标记录之间的关系的图；

[0016] 图6A和6B是示出被示出为链路记录的链路的连接关系的图；

[0017] 图7A和7B是示出被示出为链路记录的链路的连接关系的图；

[0018] 图8是示出在道路数据中的组合链路控制记录的结构的图；

[0019] 图9A和9B是示出限速数据的图；

[0020] 图10是示出导航设备的框图；

[0021] 图11是示出用于使用控制电路19来发展地图数据的方法的图；

[0022] 图12A和12B是示出链路表和节点表的结构的图；

[0023] 图13是示出由控制电路执行的表建立处理的流程图；

[0024] 图14是示出由控制电路执行的链路起点的数据登记处理的流程图；

[0025] 图15是示出根据示例性实施例的修改的用于使用控制电路来发展地图数据的方法的图；

[0026] 图16A至16C是示出根据示例性实施例的修改的节点表的结构的图；以及[0027] 图17是示出根据示例性实施例的修改的由控制电路执行的链路起点的数据登记处理的流程图。

具体实施方式

[0028] 在图10中示出根据一个示例性实施例的导航设备10。地图数据被存储在导航设备10中，并且具有特定特征。首先说明地图数据结构。然后，说明导航设备10的结构和操作。

[0029] （地图数据的结构）

[0030] 在车辆上安装的导航设备中使用根据本实施例的地图数据。如图1中所示，地图数据包括元数据、基本数据组、扩展数据组和其他数据组。

[0031] 元数据表示关于地图数据的结构的控制信息。基本数据组表示地图的基本信息，该地图的基本信息是地图数据的数据组之一。基本数据组包括在二维地图上的与道路的信息相关的道路数据和与背景的信息相关的背景数据。

[0032] 在地图数据中适当地增加扩展数据。在地图数据结构中，可以根据在地图数据中的扩展数据组的类型来建立多个地图数据。扩展数据组例如包括限速数据。其他组可以包括用于显示地图的图像数据组和图标数据组。

[0033] 诸如道路数据的在基本数据组中的每一个基本数据和诸如限速数据的在扩展数据组中的每一个扩展数据被划分为多个网格单元数据，通过分割在地图数据中包括的地图的整个区域来获得该多个网格单元数据，如图1中所示。在基本数据和扩展数据的每一个中，将多个网格单元数据的组整合到整合网格数据内。在此，整合网格数据不组合与地图数据的整个区域对应的所有网格单元数据，但是，整合网格数据组合了多个网格单元数据。因此，多个整合网格数据对应于地图数据的整个区域。

[0034] 具体地说，基本数据和扩展数据的每一个被分层，即，通过地图的详细程度来分级。因此，基本数据和扩展数据的每一个是整合文件，该整合文件包括与在每层中的地图的整个区域对应的多个整合网格数据，如图2中所示。

[0035] 图1示出被定义为第零级的最低层中的网格单元数据和在被定义为第一级的、比最低层高一层的层中的网格单元数据。第一级中的网格单元数据被划分成在第零级中的多个网格单元数据。具体地说，在图1中，第一级的一个网格单元数据被划分为预定数量的第零级的网格单元数据。在图1中，一个网格单元数据被划分为16个网格单元数据。在此，层被定义为级。

[0036] 因此，当级变高时，在基本数据和扩展数据的每一个中的网格单元数据的区域增加。当级变高时，与网格单元数据对应的地图信息被粗化。在上级中的网格单元数据用于搜索具有长距离的路线，并且用于显示具有宽范围的地图。

[0037] （整合文件的结构）

[0038] 如上所述，诸如道路数据和背景数据的基本数据和诸如限速数据的扩展数据的每一个是整合文件，该整合文件组合在每级中的网格单元数据。具体地说，在图2中示出整合文件。

[0039] 具体地说，整合文件包括：整合网格数据数量列表La1，用于提供在每级中的网格数据数量；整合网格数据偏移列表La2，用于提供在每级中的整合网格数据的偏移；以及整合网格数据列表La3，用于提供在每级中的整合网格数据。在此，整合网格数据的数量A0-AX示出在某级中的整合网格数据的数量。通过固定长度来定义数量A0-X。

[0040] 整合网格数据的偏移示出与对应的整合网格数据的偏移。具体地说，整合网格数据的偏移示出根据参考位置通过字节位置来定义的值，在该字节位置存储该对应的整合网格数据。通过固定长度来定义整合网格数据的偏移。参考位置可以是其中写入偏移的区域的开始位置、整合网格偏移列表La2的开始位置或整合网格数据列表La3的开始位置。当没有对应的整合网格数据时，整合网格数据的偏移被定义为第零值，即“0xFFFFFFFF”。

[0041] 整合网格数据包括网格单元数据偏移列表La4和网格单元数据列表La5。网格单元数据偏移列表La4包括整合网格数据大小、网格的数量M和网格单元数据的偏移1-M的信息。网格单元数据列表La5包括网格单元数据1-M的信息。整合网格数据大小示出整合网格数据的总的大小。通过固定长度来定义整合网格数据大小。网格数量M示出在与整合网格数据对应的地图区域中的网格的数量。也通过固定长度来定义网格数量M。

[0042] 网格单元数据偏移示出对应的网格单元数据的偏移。具体地说，偏移是根据参考位置通过字节位置来定义的值，在该字节位置存储该对应的网格单元数据。通过固定长度来定义偏移。在此，参考位置例如是其中写入偏移的区域的开始位置、网格单元数据偏移列表La4的开始位置或网格单元数据列表La5的开始位置。当没有对应的整合网格数据时，网格单元数据的偏移被定义为第零值，即“0xFFFFFFFF”。

[0043] 网格单元数据1-M包括用于提供基本数据和扩展数据的核心信息的信息。用与基本数据和扩展数据的类型对应的格式来描述网格单元数据1-M。将说明作为典型数据的道路数据的结构和限速数据的结构。下面未作说明的背景数据具有与道路数据类似的结构。背景数据示出在用于提供地图的一种背景特征的记录组和该背景特征的布局位置（即，坐标）的记录组之间的关系。

[0044] （道路数据的网格单元数据）

[0045] 道路数据包括关于道路的信息。如图3中所示，道路数据的网格单元数据包括道路数据管理列表Lb1、链路列表Lb2、坐标列表Lb3、上级链路ID列表Lb4和组合链路列表Lb5。道路数据管理列表Lb1包括头部的信息和一组道路数据管理记录1-B1。链路列表Lb2包括一组链路记录1-B2。坐标列表Lb3包括坐标记录1-B3。上级链路ID列表Lb4包括一组上级链路ID1-B4。组合链路列表Lb5包括一组组合链路控制记录1-B5。

[0046] （头部）

[0047] 通过固定长度来定义在道路数据的网格单元数据中存储的头部。头部包括以下信息：道路数据管理记录的数量B1、链路记录的数量B2、坐标记录的数量B3、上级链路ID的数量B4和组合链路控制记录的数量B5。

[0048] （道路数据管理记录）

[0049] 在每一个记录中通过固定长度来定义道路数据管理记录。道路数据管理记录包括链路的数量的信息。道路数据管理记录控制一系列链路序列，该一系列链路序列提供了同一街道，即同一道路。链路的数量示出在链路序列中的链路的数量，使用道路数据管理记录来控制该数量。具体地说，当建立道路数据的网格单元数据时，在对应的网格中的链路被分离为一个或多个链路序列，其中每一个链路序列提供同一街道。被分类在同一组中的每一个链路序列的道路数据管理记录被存储在道路数据的网格单元数据中。除了链路数量之外，示出街道的特性的其他数据被存储在道路数据管理记录中。

[0050] （链路记录）

[0051] 通过固定长度来定义链路记录。链路记录提供了与在每一个记录中的链路相关的属性信息。与在网格中的链路对应的链路记录被存储在道路数据的网格单元数据中。

[0052] 图4A示出链路记录的结构。如图4A中所示，在链路记录中存储关于链路类型、链路长度和车道的数量的信息。此外，在链路记录中存储关于在对应链路中从起点到终点的坐标点的数量的信息。

[0053] 在地图数据中，节点被排布在链路的各个端上。在此，在图5A中将节点示出为黑圆圈。在两个节点之间排布多个形状内插点。在图5A中将形状内插点示出为白圆圈。形状内插点用于表示可能在链路的两端之间弯曲的链路的形状。通过坐标记录来定义节点和形状内插点的每一个坐标。由链路记录提供的坐标点的数量等于在链路中排布的节点和形状内插点的数量。

[0054] 在链路记录中存储了速度类别的信息和用于确定是否存在限速的信息的标记。速度类别示出在对应链路中设置的、作为法定速度的限速类别。具体地说，当限速的信息被分类为组时，速度类别示出对应链路的限速的一组速度区。

[0055] 用于确定是否存在限速的信息的标记示出在作为扩展数据的限速数据中是否存在与链路对应的限速数据控制记录。限速数据控制记录示出链路的限速（即，法定极限速度）的详细条件，其比速度类别更详尽。

[0056] 在链路记录中存储了链路方向属性。链路方向属性示出车辆可以行驶的链路方向。具体地说，链路方向属性包括“可以向前”属性、“可以向后”属性、“双向可行”属性和“道路不通”属性。“可以向前”属性示出车辆仅能够沿着从链路的起点到链路的终点的方向行驶。从起点到终点的方向提供了向前的方向。“可以向后”属性示出车辆仅能够沿着从链路的终点到链路的起点的方向行驶。从终点到起点的方向提供了反向。“双向可行”属性示出车辆能够沿着前向和反向的每一个行驶。“道路不通”属性示出车辆不能沿着前向和反向两者行驶。

[0057] 此外，链路记录包括：用于示出关于在起点侧的组合链路控制信息的存在的标记；用于示出关于终点侧的组合链路控制信息的存在的标记；用于示出在链路的起点节点处的交通信号的存在的标记；用于示出在链路的终点节点处的交通信号的存在的标记；用于示出在上级网格单元数据中的、与链路的起点节点对应的节点的存在的标记；以及用于示出在上级网格单元数据中的、与链路的终点节点对应的节点的存在的标记。用于示出关于在起点侧的组合链路控制信息的存在的标记表示在组合链路控制列表Lb5中是否存在组合链路控制记录。组合链路控制记录示出从主题链路的起点到目标链路的交通规则，诸如禁止右转或左转。用于示出关于终点侧的组合链路控制信息的存在的标记表示在组合链路控制列表Lb5中是否存在组合链路控制记录。组合链路控制记录示出从主题链路的终点到目标链路的交通规则。

[0058] 此外，链路记录包括连接到主题链路的起点的目标链路的信息和连接到主题链路的终点的目标链路的信息。具体地说，在链路记录中存储的“连接到主题链路的起点的目标链路的信息”包括连接到起点的目标链路的编号和起点的连接属性。连接到起点的目标链路的编号示出连接到主题链路的起点的目标链路的链路编号。在此，“链路编号”被定义为链路记录从链路列表Lb2的顶部起的排布编号。具体地说，从链路列表Lb2的顶部开始计数的第N个链路记录表示链路编号N的链路记录。具有链路编号N的链路是与从链路列表Lb2的顶部起的第N个链路记录对应的链路。在根据本实施例的地图数据中，使用链路编号，而不是在传统地图数据中使用的链路ID。在传统地图数据中，在每一个链路中定义绝对链路ID。因此，在根据本实施例的地图数据中，在每一个链路中未定义绝对链路ID。

[0059] 链路记录根据预定规则来存储在其他多个链路中的仅一个链路的链路编号，该仅一个链路连接到主题链路的起点，并且所存储的链路编号提供了连接到主题链路的起点的目标链路的链路编号。后文将说明链路的连接关系。

[0060] 在链路记录中，与连接到主题链路的起点的目标链路的链路编号一起描述的起点的连接属性示出主题链路的起点是否连接到目标链路的起点或终点，所述目标链路与连接到主题链路的起点的目标链路的链路编号相对应。具体地说，通过“起点”或“终点”来定义起点的连接属性。例如，当起点的连接属性示出“起点”时，与连接到主题链路的起点的目标链路的链路编号对应的目标链路的“起点”连接到与链路记录对应的主题链路的起点，在该链路记录中存储了连接到主题链路的起点的目标链路的链路编号。当在同一网格中没有连接到主题链路的起点的目标链路时，连接到主题链路的起点的目标链路的链路编号被定义为主题链路的链路编号。在该情况下，起点的连接属性示出主题链路的“起点”。在同一网格中没有连接到主题链路的起点的目标链路的情况的示例是道路到尽头的情况，或主题链路的起点是这样的节点情况：即该节点布置在相邻网格的边界处并且仅连接到在相邻网格中布置的链路。布置在相邻网格的边界处的节点被定义为边界节点。在本实施例中，因为网格单元数据是闭合数据，所以包括布置在相邻网格的边界处的边界节点的链路的连接关系仅描述了在主题网格中链路的连接关系。

[0061] 类似地，“连接到主题链路的终点的目标链路的信息”包括连接到终点的目标链路的链路编号和终点的连接属性。连接到终点的目标链路的链路编号示出连接到主题链路的终点的目标链路的链路编号。链路记录根据预定规则存储在其他多个目标链路中的仅一个目标链路的链路编号，该仅一个目标链路连接到主题链路的终点，并且所存储的链路编号提供了连接到主题链路的终点的目标链路的链路编号。与连接到主题链路的终点的目标链路的链路编号一起描述的终点的连接属性示出主题链路的终点是否连接目标链路的起点或终点，所述目标链路与连接到主题链路的终点的目标链路的链路编号相对应。当在同一网格中没有连接到主题链路的终点的目标链路时，连接到主题链路的终点的目标链路的链路编号被定义为主题链路的链路编号。在该情况下，终点的连接属性示出主题链路的“终点”。

[0062] 链路记录主要存储链路的属性信息。

[0063] （坐标记录）

[0064] 在道路数据的网格单元数据中，包括坐标记录1-B3的坐标列表Lb3描述了节点和形状内插点的每一个的坐标（即，纬度和经度）被定义在节点和形状内插点的每一个中，所述节点和形状内插点被设置在链路列表Lb2中登记的每一个链路中。具体地说，坐标记录1-B3示出对应节点或对应的形状内插点的坐标。

[0065] 图4B示出坐标记录的结构。通过固定长度来定义坐标记录。坐标记录包括关于坐标类型的信息、作为经度坐标的X坐标和作为纬度坐标的Y坐标。坐标的类型示出关于对应点是否是边界节点、不同于边界节点的节点、虚节点（dummy node）或形状内插点的信息。

[0066] 坐标记录存储边界节点所连接到的相邻网格的标识信息。仅当在坐标记录中的坐标的类型是“边界节点”时，该标识信息示出有效值。当坐标的类型是不同于边界节点的节点时，标识信息示出无效值。边界节点被布置在相邻网格的边界处。通过边界节点是否被布置在与网格单元数据对应的网格的四条边的一边上或四个角的一角上的信息来定义“连接到边界节点的相邻网格的标识信息”。在此，网格具有矩形，如图1中所示。

[0067] （数据排布）

[0068] 将参考图5A和5B来说明在道路数据控制列表Lb1中的道路数据控制记录1-B1的排布、在链路列表Lb2中的链路记录1-B2的排布和在坐标列表Lb3中的坐标记录1-B3的排布。

[0069] 道路数据控制记录用于控制链路序列。链路记录包括链路的属性信息。坐标记录包括在链路中设置的每一个点（即，节点和形状内插点的每一个）的坐标信息。因此，坐标记录与链路记录相关。链路记录与道路数据控制记录相关。

[0070] 在本实施例中，通过对齐在列表中的排布顺序来执行在道路数据控制列表Lb1、链路列表Lb2和坐标列表Lb3之间的记录关联。图5B示出在从图5A中所示的地图获得的道路数据控制列表Lb1、链路列表Lb2和坐标列表Lb3之间的关系，该地图包括街道、链路、节点和形状内插点。在图5A中，开圆表示节点，而闭圆表示形状内插点。

[0071] 在本实施例中，如图5B中所示，在链路列表Lb2的顶部排布了与道路数据控制记录1对应链路记录组，该道路数据控制记录1提供了在道路数据控制列表Lb1中的排布编号1。紧挨着与道路数据控制记录1对应的链路序列的链路记录组排布了与道路数据控制记录2对应的链路序列的链路记录组，所述道路数据控制记录1具有在道路数据控制列表Lb1中的排布编号1，所述道路数据控制记录2具有在道路数据控制列表Lb1中的排布编号2。因此，在道路数据控制列表Lb1中的街道的排布顺序与在链路列表Lb2中的链路序列的排布顺序相同。根据这一点，道路数据控制列表Lb1和链路列表Lb2被产生为使得关于街道的多个属性彼此相关联。

[0072] 在本实施例中，与在道路数据控制列表Lb1中的道路数据控制记录1-B1对应的街道的排布对齐于与在链路列表Lb2中的链路记录1-B2对应的街道的排布，即等同为相同顺序。因此，道路数据控制列表Lb1和链路列表Lb2彼此相关联。

[0073] 在此，道路数据控制记录存储链路数量的信息。因此，即使当多个链路记录仅与一个道路数据控制记录相关联时，道路数据控制列表Lb1的顶部和链路列表Lb2的顶部也被读出和参考，使得在道路数据控制列表Lb1和链路列表Lb2的顶部之间的关系被指定。

[0074] 在链路列表Lb2中登记的链路记录是属性数据，用于示出链路的第一属性，即道路链路的特性。与这个链路对应的坐标记录是示出链路的第二属性的属性数据。在本实施例中，如图5B中所示，从坐标列表Lb3的尖端起排布在与链路记录1对应的链路中设置的点的坐标记录组，所述链路记录1在链路列表Lb2中具有排布编号1。紧挨着与在链路列表Lb2中的链路记录1对应的坐标记录组排布的是在与链路记录2对应的链路中设置的点的坐标记录组，所述链路记录2在链路列表Lb2中具有排布编号2。因此，链路列表Lb2和坐标列表Lb3被产生为等同在链路列表Lb2和坐标列表Lb3之间的链路的排布顺序。

[0075] 在本实施例中，与在坐标列表Lb3中的坐标记录1-B3对应的链路的排布被对齐为具有与链路列表Lb2相同的顺序。因此，链路列表Lb2和坐标列表Lb3彼此相关联。在此，因为链路记录存储了坐标点的数量的信息，所以即使当多个坐标记录仅与一个链路记录相关联时，也通过从链路列表Lb2的顶部和坐标列表Lb3的顶部进行参考和读出来指定在链路记录1-B2和坐标记录1-B3之间的关系。在此，以从链路的起点到终点的顺序来在坐标列表Lb3中排布与仅一个链路记录对应的坐标记录组。因为链路的终点的坐标记录示出与相邻链路的起点的坐标记录相同的坐标，所以可以跳过该坐标记录的登记。

[0076] （链路的连接关系）

[0077] 将说明链路的连接关系的定义方法。在本实施例中，链路记录存储关于连接到主题链路的起点和/或终点的仅一个目标链路的信息。具体地说，链路记录仅存储“连接到主题链路的起点的目标链路的信息”和“连接到主题链路的终点的目标链路的信息”。这些特征与传统地图数据不同，传统地图数据描述了关于连接到主题链路的所有链路的信息。

[0078] 具体地说，在本实施例中，描述了连接到同一节点的多个链路的连接关系，使得在连接到同一节点的每一个链路的链路记录中的相邻链路的链路编号被定义为顺时针方式的连接链路编号。在此，连接链路编号包括起点连接链路编号和终点连接链路编号。具体地说，在本实施例中，连接到节点的链路的连接关系不被描述为在现有技术中的一批节点数据。然而，根据本实施例的连接到节点的链路的连接关系以连接到同一节点的每一个链路的链路记录而被描述为散布表达（dispersed expression）。当使用该地图数据时，围绕节点以顺时针方式来参考这些链路记录，从而指定连接到同一节点的链路。

[0079] 图6A示出连接链路编号的描述方向以及链路的连接关系的示例。具体地说，在作为主题链路的显著链路（notable link）L0的起点和终点处的、作为目标链路的其他链路的连接关系被描述如下。图6B示出在图6A中的显著链路L0的链路记录中描述的起点连接链路编号和终点连接链路编号。在图6A和6B中，连接到显著链路L0的起点的目标链路是链路L1至链路L3。在目标链路L1-L3中以顺时针方式从显著链路L0测量的、与显著链路L0相邻的链路是链路L1。因此，在显著链路L0的链路记录中的起点连接链路编号是链路L1的链路编号。

[0080] 连接到显著链路L0（即值得注意的链路）的终点的其他链路是链路R1和链路R2。在目标链路R1-R2中以顺时针方式从显著链路L0测量的、与显著链路L0相邻的链路是链路R1。因此，在显著链路L0的链路记录中的终点连接链路编号是链路R1的链路编号。

[0081] 接下来，图7A示出在图6A和6B中的链路L1-L3的链路记录中描述的连接链路编号。

[0082] 如图7A中所示，以顺时针方式在显著链路L0的起点周围测量的与链路L1相邻的链路是链路L2。因此，将链路L2的链路编号描述为在链路L1的链路记录中的链路L1的起点或终点连接链路编号（即，起点连接链路编号或终点连接链路编号），链路L1在显著链路L0的起点与显著链路L0重叠。以顺时针方式测量的与链路L2相邻的链路是链路L3。因此，将链路L3的链路编号描述为在链路L2的链路记录中的链路L2的起点或终点连接链路编号，链路L2在显著链路L0的起点与显著链路L0重叠。以顺时针方式测量的与链路L3相邻的链路是链路L0。因此，显著链路L0的链路编号被描述为在链路L3的链路记录中的链路L3的起点或终点连接链路编号，链路L3在显著链路L0的起点与显著链路L0重叠。

[0083] 在本实施例中，以上面的方式来描述了多个链路记录，从而描述了显著链路L0的起点的链路连接关系。

[0084] 图7B示出在链路R1、R2的链路记录中描述的连接链路编号。如图7B中所示，以顺时针方式在显著链路L0的终点周围测量的与链路R1相邻的链路是链路R2。因此，将链路R2的链路编号描述为在链路R1的链路记录中的链路R1的起点或终点连接链路编号（即，起点连接链路编号或终点连接链路编号），链路R1在显著链路L0的起点与显著链路L0重叠。以顺时针方式测量的与链路R2相邻的链路是显著链路L0。因此，将显著链路L0的链路编号描述为链路R2的起点或终点连接链路编号，链路R2在终点与显著链路L0重叠。

[0085] 在本实施例中，使用多个链路记录来描述显著链路L0的终点的链路连接关系。

[0086] 链路连接关系的表达方法如上所述。在本实施例中，因为以上面的方式来定义链路连接关系的表达方法，所以不必在地图数据中增加示出链路连接关系的节点数据，使得地图数据紧凑。

[0087] （高级链路ID）

[0088] 接下来，将说明在图3中所示的上级链路ID。在道路数据的每一个网格单元数据中存储的上级链路ID示出与主题链路对应的上级链路的链路编号。通过固定长度来定义上级链路ID。在此，上级链路的链路编号是从链路列表Lb2的顶部起的上级网格的网格单元数据中的排布编号。上级链路ID用于定义在主题级网格中的链路和上级网格中的链路之间的关系。

[0089] 具体地说，在上级链路ID列表Lb4中，以与在链路列表Lb2中登记的链路记录的每一个链路中的链路列表Lb2的链路排布顺序相同的排布顺序来排布上级链路的上级链路ID ID1-IDB4。因此，在上级链路ID列表Lb4中的排布顺序与在链路列表Lb2中的排布顺序一致，在上级链路ID列表Lb4中的上级链路ID ID1-IDB4与在链路列表Lb2中的链路记录1-B2相关联。

[0090] （组合链路控制记录）

[0091] 将参考图8来说明组合链路控制记录。通过可变长度来定义在道路数据的网格单元数据中存储的组合链路控制记录。组合链路控制记录包括目标链路的链路编号、目的地点的属性、目的地链路的数量C和包括一组目的地链路数据1-C的目的地链路列表Lc。组合链路控制记录表示目的地链路，车辆从与主题链路编号对应的主题链路的起点或终点进入该目的地链路。具体地说，车辆从主题链路出来并进入该目的地链路。

[0092] 具体地说，目的地链路的数量C示出在目的地链路列表Lc中登记的目的地链路数据的数量。在目的地链路列表Lc中提供的目的地链路数据1-C的每一个提供了目的地链路的标识信息，车辆可以从与主题链路编号对应的主题链路的起点或终点去往该目的地链路。目的地点属性提供了“起点”或“终点”的信息。当目的地点属性是“起点”时，组合链路控制记录的目的地链路列表Lc示出从主题链路的起点开始的目的地链路。当目的地点属性是“终点”时，组合链路控制记录的目的地链路列表Lc示出从主题链路的终点开始的目的地链路。

[0093] 每一个目的地链路数据包括目的地链路的标识信息，诸如作为其中存在目的地链路的网格的编号的网格编号和作为目的地链路编号的目的地链路的链路编号。具体地说，目的地链路数据提供了目的地链路的标识信息，用于示出网格编号和目的地链路编号。

[0094] 当使用根据本实施例的地图数据时，基于目的地链路列表Lc和由链路记录组指定的链路的连接关系来指定交通规则，诸如在交叉位置的右转限制或左转限制。

[0095] 例如，链路L0的起点提供了交叉位置，链路L1-L3从该交叉位置延伸，如图8中所示。在该情况下，当相对于与链路L0的起点对应的交叉位置没有交通限制时，在具有主题链路编号L0和目的地点属性“起点”的组合链路控制记录的目的地链路列表Lc中描述了示出目的地链路L1-L3的三个目的地链路数据。在此，在该情况下，假定车辆不进行U形转弯。当禁止从链路L0到链路L3的右转时，在目的地链路列表Lc中仅存储将链路L1示出为目的地链路的目的地链路数据和将链路L2示出为目的地链路的目的地链路数据。在目的地链路列表Lc中未存储将链路L3示出为目的地链路的目的地链路数据。根据本实施例的设备基于在链路连接关系和目的地链路之间的差别信息来指定交通规则，诸如在交叉位置的右转禁止或左转禁止。

[0096] （在限速数据中的网格单元数据）

[0097] 作为扩展数据的限速数据示出在每一个链路中的限速。如图9A中所示，在限速数据中的网格单元数据包括限速数据控制列表Le，该列表提供了头部和限速数据控制记录1-E。图9A示出限速数据的网格单元数据的结构。

[0098] （头部）

[0099] 通过固定长度来定义限速数据的网格单元数据中存储的头部。头部提供了限速数据控制记录的数量E等。

[0100] （限速数据控制记录）

[0101] 在每一个记录中，通过固定长度来定义限速数据控制记录。限速数据控制记录提供了主题链路的前向限速和反向限速。当主题链路中没有限速时，即当链路没有限速时，示出没有限速的值被描述为前向限速或反向限速。当主题链路是单向链路时，与车辆不能行驶的方向对应的前向限速和反向限速之一被定义为不示出数据的空数据。

[0102] 限速数据控制记录的每一个仅对应于一个链路。因此，在限速数据控制列表Le中登记了限速数据控制记录。具体地说，如图9B中所示，在限速数据控制列表Le中，与链路对应的限速数据控制记录1-E以与在链路列表Lb2中的链路的排布相同的排布顺序被排布在与网格对应链路列表Lb2中登记的链路记录的每一个链路中。图9B示出在链路记录1-B2的排布和限速数据控制记录1-E的排布之间的关系。

[0103] 在限速数据控制列表Le中未登记与这样的链路记录对应的限速数据控制记录，在该链路记录中，将限速信息存在标记设置为值“无信息”。具体地说，以与在链路列表Lb2中具有排布编号的链路记录对应的链路的升序来在限速数据控制列表Le中排布对应于链路的限速数据控制记录。当没有与链路记录对应的限速数据控制记录时，与紧挨着对应于无限速数据控制记录的链路记录的链路记录对应的限速数据控制记录填充在其处没有与链路记录对应的限速数据控制记录要被存储的位置。

[0104] 在根据本实施例的地图数据中，在道路数据中的每一个链路记录1-B2与限速数据的对应限速数据控制记录1-E相关联。

[0105] （地图数据概述）

[0106] 因此，说明了地图数据的结构。在本实施例中，将道路示出为链路单元。通过示出链路的连接关系的信息来表示道路网络。

[0107] 当产生地图数据时，通过在每种数据中进行分组，而不是通过在地图的每一个分量中进行分组，来列出与地图的分量相关的多种数据。例如，在每种属性数据中分组与链路相关的多种属性数据，诸如链路记录、坐标记录、限速数据控制记录，以便获得数据列表，诸如链路列表Lb2、坐标列表Lb3和限速数据控制列表Le等。因此，容易改变地图数据的内容。

[0108] 在传统的现有技术中，因为地图数据具有使得多种类型的数据被分组在每一项中的结构，所以即使当更新特定类型的属性数据时也需要更新地图数据的整体。在本实施例中，当更新特定类型的属性数据时，将用于提供该特定类型的属性数据组的数据列表替换为新版本数据列表，使得更新地图数据。因此，根据本实施例的地图数据具有容易更新的结构。

[0109] 在该地图数据结构中，当改变诸如扩展数据的地图数据中的数据列表的组合时，容易改变地图数据的内容。因此，容易形成多种类型的地图数据。例如，容易从地图数据中删除限速数据，从而在地图数据中存储关于限速的信息，或容易向地图数据添加限速数据，从而从地图数据中移除关于限速的信息。结果，提供根据用户的需要的各种类型的地图数据。例如，当单独地销售提供地图数据的数据列表时，用户可以定制地图数据。因此，地图数据是可定制的。

[0110] 在列入数据列表的步骤中，需要关联在每一个数据列表中的与同一链路对应的属性数据（即，记录）。在本实施例中，基于数据列表的排布来执行这个关联。因此，不使用用于关联属性数据的链路ID等，而是根据在数据列表中的排布来关联属性数据。因此，根据本实施例的地图数据被紧凑化。

[0111] 具体地说，当通过固定长度来定义每一个记录时，链路ID和用于表示数据边界的代码不必存储在记录的顶部。此外，不必在主题记录中存储目标记录的地址。因此，根据本实施例的地图数据被最小化。当通过固定长度来定义记录id时，可以通过从数据列表的顶部起的记录的排布编号和记录长度来指定作为要读出的目标的记录的容纳位置。因此，提高了每一个记录的可访问性。

[0112] 此外，在传统地图数据中，在每一个节点中产生用于示出链路的连接关系的节点数据。然而，在本实施例中，关于链路的连接关系的信息被散布，并且在链路记录中存储该信息。因此，不必在地图数据中产生节点数据。因此，不必在链路数据和节点数据中冗余地维护诸如坐标信息的信息。因此，根据本实施例的地图数据紧凑得多。

[0113] 具体地说，在本实施例中，在链路记录中仅存储了作为用于示出链路的连接关系的信息的起点连接链路编号和终点连接链路编号之一。此外，在与多个链路所耦合到的节点（即，链路的起点或终点）对应的记录中仅存储连接目标链路的一个标识信息（即，链路编号）。

[0114] 具体地说，在与同一节点耦合的链路的链路记录中，通过在图6A至7B中所示的方法来存储连接链路编号。因此，在与同一节点耦合的多个链路的链路记录中有效地存储了用于示出链路的连接关系的信息。因此，有效地减少了根据本实施例的地图数据的数据量。

[0115] 在根据本实施例的地图数据结构中，以某种顺序来参考连接链路编号，使得容易参考与同一节点耦合的链路的链路记录。因此，有效地指定与同一节点耦合的链路的连接关系。因此，即使当关于链路的连接关系的信息被分布和存储在链路记录中时，也减少了在诸如导航设备的车载设备中用于指定链路的连接关系的处理负荷。

[0116] 在根据本实施例的地图数据结构中，在链路列表Lb2中的链路排布编号用于描述连接关系。因此，不必设置与每一个链路对应的链路ID。因此，在根据本实施例的地图数据结构中，数据被紧凑地存储。

[0117] （导航设备的结构）

[0118] 将说明其中存储了地图数据的导航设备10。

[0119] （基本结构）

[0120] 在图10中示出设备10。设备10包括位置检测部件11、地图数据输入部件13、操作部件15、音频输出部件16、显示部件17和控制电路19。

[0121] 位置检测部件11检测其上安装了导航设备10的车辆的当前位置。例如，位置检测部件11包括传统的回转仪、距离传感器和GPS接收器等。

[0122] 地图数据输入部件13包括存储介质，诸如硬盘驱动器和DVD，其中存储了地图数据。地图数据输入部件13将在存储介质中存储的地图数据输入到控制电路19内。除了用于存储地图数据的硬盘驱动器之外，输入部件13还可以包括DVD驱动器。在导航设备10中，当输入部件包括DVD驱动器时，可以在硬盘驱动器中装入经由DVD介质获得的地图数据的新数据。导航设备10还可以包括能够与信息中心进行通信的通信部件，所述信息中心分发地图数据。基于经由通信部件从中心接收的数据，设备10更新在地图数据输入部件13中存储的地图数据。

[0123] 操作部件15将来自用户的指令输入到控制电路19中。操作部件15包括在显示部件17上排布的触摸板和在导航设备10的主体表面上和/或在遥控部件中排布的操作开关。使用操作部件15，用户操作导航设备10来改变地图的比例，滚动显示部件17的屏幕和设置目的地等。

[0124] 音频输出部件16包括扬声器等。来自控制电路19的信号被输入到部件16内，使得部件16输出语音引导等。显示部件17能够全色显示。显示部件17根据从地图数据输入部件13输入的地图数据来显示地图图像。此外，显示部件17显示在地图图像上叠加的车辆的当前位置标志和引导路线。车辆的当前位置标志表示由位置检测部件11检测到的当前位置。

[0125] 控制电路19具有与传统的微计算机类似的结构。控制电路19包括CPU19a、ROM19b、RAM19c、I/O部件和用于在这些部件之间进行耦合的总线。CPU19a根据在ROM19b中存储的程序，基于从位置检测部件11、地图数据输入部件13和操作部件15输入的信号（或信息）来执行各种处理。

[0126] 具体地说，当通过CPU19a来执行程序时，控制电路19从地图数据输入部件13读出在每一个网格中的地图数据。然后，将该地图数据发展（即转换和输入）到RAM19c内。基于地图数据，执行地图显示处理、路线搜索处理和路线引导处理等。

[0127] （读出地图数据）

[0128] 将说明用于通过控制电路19来从地图数据输入部件13读出地图数据的步骤和向RAM19c内输入地图数据的步骤。控制电路19从地图数据输入部件13读出在每一个网格中的地图数据，然后向RAM19c内输入地图数据。在该情况下，如图11中所示，在地图数据输入部件13中存储的原始地图数据被转换为与参考地图数据的应用程序对应的专用地图数据MA1-MA3。在每一个应用程序中的专用地图数据MA1-MA3被输入到RAM19c内。然后，RAM19c将专用地图数据MA1-MA3存储为地图数据。

[0129] 这些应用程序包括：绘制应用程序，用于执行在显示部件17的屏幕上绘制地图图像的处理；路线搜索应用程序，用于执行搜索到由用户经由操作部件15输入的目的地的引导路线的处理；以及路线引导应用程序，用于执行引导在车辆正行驶的道路周围的路线的处理，等等。在此，路线引导包括路线的引导、在车辆前方的道路的交通控制的引导和车道的引导。在RAM19c中存储了用于执行各种应用程序的信息和从在地图数据输入部件13中存储的原始地图数据获取和组织的专用地图数据MA1-MA3。

[0130] 被参考来用于绘制应用程序的专用地图数据被定义为绘制地图数据MA1。被参考来用于路线搜索应用程序的专用地图数据被定义为路线搜索地图数据MA3。被参考来用于路线引导应用程序的专用地图数据被定义为路线引导地图数据MA2。

[0131] 除了在ROM19b中存储的绘制应用程序、路线搜索应用程序和路线引导应用程序之外，控制电路19还执行用于从地图数据输入部件13读出地图数据并且向RAM19c内输入地图数据的程序，使得控制电路19提供导航设备10的功能。

[0132] 绘制地图数据MA1提供了用于在显示部件17的屏幕上显示地图图像的足够和必要的信息。路线搜索地图数据MA3提供了用于搜索到目的地的引导路线的足够和必要的信息。路线引导地图数据MA2提供了用于使用显示部件17和音频输出部件16来引导道路的路线的足够和必要的信息。

[0133] 具体地说，与每一个应用程序和每一个网格对应的专用地图数据MA1-MA3包括链路表和节点表。在链路表中排布了与在对应网格中的链路相关的信息。在节点表中排布了与作为链路的连接点的节点相关的信息。

[0134] 每一个链路表TBL11-TBL13包括在网格的每一个链路中的“链路数据”。在该“链路数据”中组织了与一个链路相关的多种数据。每一个节点表TBL21-TBL23包括在网格的每一个节点中的“节点数据”。在该“节点数据”中组织了连接到一个节点的链路的标识信息。

[0135] 具体地说，当在地图数据输入部件13中存储的地图数据被输入到RAM19c内时，形成链路表TBL11-TBL13，使得在每一个链路中组织与链路本身相关的信息，并且形成节点表TBL21-TBL23，使得在每一个节点中组织关于节点的信息（诸如交通信号的存在）和链路的连接关系的信息。在此，在每一个链路中描述在地图数据中的链路的连接关系。

[0136] （链路表和节点表）

[0137] 用于提供路线搜索地图数据MA3的链路表TBL13和节点表TBL23具有例如在图12A中所示的数据结构。

[0138] 链路表TBL11-TBL13包括在网格的每一个链路中的链路数据，并且该链路数据提供链路详细属性信息，其中，描述了链路的链路编号和详细属性。具体地说，如图12A中所示，关于链路编号、链路类型、链路长度、限速和单向规则的信息被描述为在链路数据中的链路属性信息，并且链路数据被登记在路线搜索链路表TBL13中。

[0139] 在链路数据中描述的链路编号示出在链路列表Lb2中登记的对应链路的排布编号。根据在对应链路记录中存储的链路类型得出在链路数据中描述的链路类型。类似地，根据在对应链路记录中存储的链路长度得出在链路数据中描述的链路长度。

[0140] 根据在对应链路记录中的链路方向属性得出在链路数据中描述的单向交通规则的信息。此外，根据在对应链路记录中存储的速度类别或在对应链路的限速数据控制记录中所示的前向限速和反向限速得出在链路数据中描述的限速。通常，将在对应链路的限速数据控制记录中所示的前向限速和反向限速与限速被应用到的车道的方向信息一起被描述为在链路数据中的限速。当没有对应链路的限速数据控制记录时，将基于在速度类别中所示的速度范围的值描述为限速。例如，速度范围的代表值被描述为限速。

[0141] 节点表TBL21-TBL23包括在同一网格的每一个节点中的节点数据。节点数据包括：节点编号；在主题节点处的连接链路的数量；其中排布了连接到主题节点的链路的链路编号的链路连接信息；用于示出主题节点的坐标的节点坐标信息；以及节点详细属性信息，其中描述了不同于坐标和连接关系的节点的详细属性。

[0142] 具体地说，节点编号附着到节点数据，以便以在节点表TBL21-TBL23中的登记顺序来顺序分配节点编号。在节点数据中描述的链路连接的数量对应于链路的数量，该链路的链路编号被登记在链路连接信息中。链路连接信息包括连接到对应节点的每一个主题链路的一组链路编号。在链路连接信息中的链路编号与对应链路的链路列表Lb2的排布编号一致。

[0143] 如图12A中所示，在路线搜索节点表TBL-23中，搜索路线所需的右转/左转交通规则信息被描述为节点详细属性信息。右转/左转交通规则信息包括到达主题节点的链路的链路编号，在该主题节点，车辆被禁止右转和/或左转。此外，右转/左转交通规则信息还包括被禁止的事项，诸如右转禁止、左转禁止以及右转和左转禁止。

[0144] 根据在与主题节点耦合的每一个链路的链路记录中示出的以下项得出用于提供节点数据的链路连接信息：起点连接链路编号、终点连接链路编号、起点连接属性和终点连接属性。根据主题节点的坐标记录得出节点坐标信息。根据连接到主题链路的每一个链路的组合链路数据控制记录得出右转/左转交通规则信息。

[0145] 图12B示出用于提供路线引导地图数据MA2的链路表TBL12和节点表TBL-22的数据结构。如图12B中所示，向路线引导链路表TBL12登记的链路数据包括作为链路详细属性信息的链路类型和车道的数量。根据在对应链路记录中所示的车道的数量得出被描述为链路详细属性信息的车道的数量。在路线引导节点表TBL22中登记节点数据。该节点数据包括作为节点详细属性信息的交通信号信息。交通信号信息用于引导在车辆前方有交通信号。交通信号信息示出作为主题节点的交通灯，即交通信号的存在与否。根据在连接到主题节点的一组链路的每一个链路记录中描述的以下项来得出交通信号信息：用于示出在链路的起点侧的交通信号的存在的标记；以及用于示出在链路的终点侧的交通信号的存在的标记。

[0146] 虽然在附图中未示出，但是绘制地图数据MA1的链路表TBL11可以是仅包括作为链路详细属性信息的链路类型的信息的链路表。此外，绘制地图数据MA1的节点表TBL21可以是与节点表TBL22相同的节点表。

[0147] （表准备处理）

[0148] 将参考图13来说明作为表准备处理的表形成处理。当控制电路19基于地图数据输入部件13的地图数据在每一个网格和每一个应用程序中形成节点表TBL21-TBL23和链路表TBL11-TBL13时，执行表形成处理。图13示出用于示出由控制电路19执行的表形成处理的流程图。当读出地图数据时，控制电路19执行在每一个网格中的表形成处理。因此，在每一个应用程序中形成与主题网格对应的节点表TBL21-TBL23和链路表TBL11-TBL13。

[0149] 当表形成处理开始时，控制电路19通告形成表。在步骤S100中，电路19在RAM19c中形成在对应网格的每一个应用程序中的链路表TBL11-TBL13和节点表TBL21-TBL23，并且链路表TBL11-TBL13和节点表TBL21-TBL23的每一个是空表，以便每一个表TBL11-TBL13和TBL21-TBL23的内容是空的。然后，在步骤S110中，节点编号V被初始化为1，以便在每一个节点数据中的节点编号被分配为从1开始的正整数，并且在节点表TBL21-TBL23中登记节点数据。在步骤S120中，主题链路的链路编号W被初始化为1。在表形成处理中，从链路列表Lb2的顶部依次参考链路记录。主题链路的链路编号W示出从链路列表Lb2的顶部起的链路记录的排布编号。主题链路对应于主题链路编号W的链路记录。

[0150] 在步骤S120后，电路19在步骤S130中将作为地图数据读出目标的网格的链路记录的数量B2设置为可变数N。根据在道路数据的网格单元数据中描述的链路记录编号B2来设置链路记录的数量B2。在此，将置于可变数N上的值定义为值N。

[0151] 在步骤S130后，电路19在步骤S140中确定主题链路编号W是否大于值N。当该电路确定主题链路编号W等于或小于值N时，即当在步骤S140中的确定是“否”时，执行在步骤S150中的链路起点侧数据登记处理和在步骤S160中的链路终点侧数据登记处理。

[0152] 在步骤S150中的链路起点侧数据登记处理中，形成在每一个应用程序中的、布置在主题链路的起点处的节点的节点数据。在每一个应用程序的节点表TBL21-TBL23中登记该节点数据。此外，在每一个应用程序中形成连接到主题节点的每一个链路的链路数据。在每一个应用程序的链路表TBL11-TBL13中登记该链路数据。

[0153] 在步骤S160中的链路终点侧数据登记处理中，形成在每一个应用程序中的、布置在主题链路的终点处的节点的节点数据。在每一个应用程序的节点表TBL21-TBL23中登记该节点数据。此外，在每一个应用程序中形成连接到主题节点的每一个链路的链路数据。在每一个应用程序的链路表TBL11-TBL13中登记该链路数据。

[0154] 因此，完成在步骤S150中的链路起点侧数据登记处理和在步骤S160中的链路终点侧数据登记处理，然后，在步骤S170中，电路19将主题链路编号W加1，即，主题链路编号W被更新为W+1。它返回到步骤S140，然后，基于更新的主题链路编号W来重复步骤S140至S170。在步骤S140中，当主题链路编号W超过值N时，即当步骤S140确定为“是”时，表形成处理结束。

[0155] 将参考图14来说明步骤S150中的链路起点侧数据登记处理。当电路19开始执行链路起点侧数据登记处理时，电路19在步骤S210将布置在主题链路的起点处的节点设置为节点数据的登记的目标节点。在此，在RAM19c的节点坐标信息形成区域中登记布置在主题链路的起点处的节点的节点坐标。节点数据的登记的目标节点被设置为布置在主题链路的起点处的节点。在此，可以基于在与主题链路的链路记录相关联的一组坐标记录的顶部记录中描述的坐标信息来指定节点坐标。

[0156] 在步骤S210后，电路19在步骤S220中确定是否已经在每一个应用程序的节点表TBL21-TBL23中登记了被设置为节点数据登记目标的节点的节点数据。当在节点表TBL21-TBL23中登记了节点数据时，即当步骤S210确定为“是”时，它进行到步骤S330。当在节点表TBL21-TBL23中未登记节点数据时，即当步骤S210确定为“否”时，它进行到步骤S230。

[0157] 在步骤S230中，电路19将参考链路编号Zr设置为主题链路编号W，以便其链路记录被参考的参考链路被设置为主题链路。在根据本实施例的地图数据结构中，为了获得与节点对应的链路的连接关系，需要以顺时针的方式参考连接到同一节点的链路的链路记录。在步骤S230中，当依次参考连接到同一节点的链路的链路记录时，在步骤S230中设置要参考的第一链路记录。

[0158] 在步骤S230中，电路19进行到步骤S240。在步骤S240中，另外在RAM19c的链路连接信息形成区域中登记参考链路编号Zr。因此，连接到节点数据登记目标节点的参考链路的链路编号被登记为链路连接信息。

[0159] 在步骤S240后，电路19在步骤S250中确定是否已经在链路表TBL11-TBL13中登记了在每一个应用程序中与参考链路编号Zr对应的参考链路的链路数据。当电路19确定在链路表TBL11-TBL13中未登记参考链路的链路数据时，即当步骤S250确定为“否”时，它进行到步骤S260，并且在执行步骤S260后，它进行到步骤S270。当电路19确定在链路表TBL11-TBL13中登记了参考链路的链路数据时，即当步骤S250确定为“是”时，它直接进行到步骤S270，而不执行步骤S260。

[0160] 具体地说，在步骤S260中，在链路列表Lb2中参考与参考链路编号Zr对应的链路编号的链路记录。基于所参考的链路记录和诸如限速数据控制记录的相关记录，形成关于该参考链路的在每一个应用程序中的链路数据。具体地说，由参考链路的链路记录提供的信息被组织，使得形成以下项：要在路线搜索链路表TBL13中登记的链路数据、要在路线引导链路表TBL12中登记的链路数据和要在绘制链路表TBL11中登记的链路数据。在图12A和12B等中示出了与每一个链路表TBL11-TBL13对应链路数据。分别在链路表TBL11-TBL13中登记在每一个应用程序中每一个链路数据。

[0161] 在步骤S270中，更新参考链路编号Zr。具体地说，在与当前参考链路编号Zr对应的参考链路的链路记录中描述的起点连接链路编号Qs或终点连接链路编号Qe之一被设置为新的参考链路编号Zr。因此，参考链路编号Zr被更新为起点连接链路编号Qs或终点连接链路编号Qe之一。具体地说，当当前参考链路的起点与在步骤S210中设置的节点数据登记目标节点一致时，参考链路编号Zr被更新为在当前参考链路的链路记录中描述的起点连接链路编号Qs。当当前参考链路的终点与在步骤S210中设置的节点数据登记目标节点一致时，参考链路编号Zr被更新为在当前参考链路的链路记录中描述的终点连接链路编号Qe。在此，当在起点侧数据登记处理中首先执行步骤S270时，参考链路编号Zr被更新为在此时的主题参考链路的链路记录中描述的起点连接链路编号Qs，这是因为在步骤S210中被布置在主题链路的起点处的节点被设置为节点数据登记目标节点。通过比较起点和终点的每一个的坐标来指定参考链路的起点或终点是否是节点数据登记目标节点。

[0162] 在步骤S270后，控制电路19进行到步骤S280。在步骤S280中，确定参考链路编号Zr是否与主题链路编号W一致。在此，当参考链路编号Zr与主题链路编号W一致时，以顺时针的方式来完整参考对应于与节点耦合的链路的链路记录。

[0163] 当确定参考链路编号Zr与主题链路编号W不一致时，即当在步骤S280中确定为“否”时，返回到作为例程循环的顶部的步骤S240。然后，执行关于与更新的参考链路编号Zr对应的参考链路的步骤S240至S280。

[0164] 因此，当重复地执行上面的循环时，在链路连接信息形成区域中依次登记与节点数据登记目标节点耦合的链路的链路编号。最后，完成关于主题节点的链路连接信息。此外，在步骤S280中，当确定参考链路编号Zr与主题链路编号一致时，即当在步骤S280中确定为“是”时，电路19进行到步骤S290。在步骤S290中，基于在链路连接信息形成区域中产生的链路连接信息，形成路线搜索节点数据。然后，在路线搜索节点表TBL23中登记路线搜索节点数据。

[0165] 具体地说，基于在链路连接信息中指定的主题节点的链路连接关系，关于在地图数据输入部件13中存储的地图数据产生在路线搜索节点数据中存储的节点详细属性信息。通过节点数据提供以下项：当前设置的节点编号V、在链路连接信息中登记的链路的数量、在链路连接信息形成区域中完成的链路连接信息、在节点坐标信息形成区域中登记的节点坐标信息和用于路线搜索的节点详细属性信息。然后，向路线搜索节点表TBL23登记节点数据。

[0166] 类似地，在接着步骤S290的步骤S300中，在路线引导节点表TBL22中登记路线引导节点数据。具体地说，基于在链路连接信息中指定的主题节点的链路连接关系，产生要在路线引导节点数据中存储的节点详细属性信息。将节点详细属性信息替换为在路线搜索节点数据中存储的节点详细属性信息，以便形成路线引导节点数据。然后，在路线引导节点表TBL22中登记路线引导节点数据。

[0167] 在接着步骤S300的步骤S310中，在绘制节点表TBL21中登记绘制节点数据。具体地说，基于在链路连接信息中指定的主题节点的链路连接关系，产生要在绘制节点数据中存储的节点详细属性信息。节点详细属性信息被替换为在路线搜索节点数据中存储的节点详细属性信息，以便形成绘制引导节点数据。然后，在绘制节点表TBL21中登记绘制节点数据。

[0168] 在应用程序的各个节点表TBL21-TBL23中登记主题节点的每一个节点数据后，进行到步骤S320。总计节点编号V。然后，进行到步骤S330。

[0169] 在步骤S330中，清理在RAM19c中的用于形成节点数据的信息形成区域，即，链路属性信息形成区域和节点坐标信息形成区域。然后，链路起点侧数据登记处理结束。

[0170] 在步骤S160中执行的链路终点侧数据登记处理类似于链路起点侧数据登记处理。在链路终点侧数据登记处理和链路起点侧数据登记处理之间的差别是节点数据登记目标节点被设置为布置在主题链路的终点处的节点。在本实施例中，在步骤S160执行链路终点侧数据登记处理。在节点表TBL21-TBL23的每一个中登记在主题链路的终点处布置的节点的节点数据。

[0171] 因此，上文说明了导航设备10。在根据本实施例的地图数据结构中，地图数据被紧凑化。此外，在多个链路记录中分布和描述链路连接关系。因此，如果在导航设备侧每次参照地图数据来指定链路连接关系，则用于指定链路连接关系的负荷将比现有技术大。因此，在本实施例中，根据地图数据来形成节点数据，然后在每一个节点表TBL21-TBL23中登记节点数据。因此，减少了在本实施例中的指定链路连接关系的负荷。因此，在导航设备10中，补偿了紧凑地图数据的缺点。

[0172] 在导航设备10中，在从地图数据产生节点表TBL21-TBL23后，设备10访问地图数据，并且在应用程序中执行特定处理。因此，在提供上面的数据结构的设备10中，不必大幅度地修改传统上使用的传统应用程序。

[0173] 此外，因为在每一个应用程序中形成链路表TBL11-TBL13和节点表TBL21-TBL23，所以提高了数据可访问性，并且提高了应用程序的处理性能。

[0174] 在此，通过单个表形成处理串行地形成用于每一个应用程序的链路表TBL11-TBL13和节点表TBL21-TBL23。导航设备10可以彼此并行地执行用于每一个应用程序的表形成处理，使得同时形成用于每一个应用程序的链路表TBL11-TBL13和节点表TBL21-TBL23。

[0175] 例如，对于每一个应用程序执行表形成处理。在应用程序的每一个表形成处理中，在步骤S260中，仅形成对应应用程序的链路表。在步骤S290至S310中，仅执行步骤S290至S310之一，从而形成对应于链路表的节点表。

[0176] 具体地说，根据来自应用程序的请求，具体地说，根据来自用于执行对应于该应用程序的处理的特定任务的请求，执行与输出所述请求的应用程序对应的表形成处理，使得产生用于该应用程序的链路表和节点表。在该情况下，减小了用于链路表和节点表的存储区。因此，提高了导航设备10的方便性。

[0177] 例如，设备10根据来自绘制应用程序的请求来产生绘制链路表TBL11和绘制节点表TBL21。设备10根据来自路线引导应用程序的请求来产生路线引导链路表TBL12和路线引导节点表TBL22。设备10根据来自路线搜索应用程序的请求来产生路线搜索链路表TBL13和路线搜索节点表TBL23。

[0178] 在上面的实施例中，对于每一个应用程序形成链路表TBL11-TBL13和节点表TBL21-TBL23。可替代地，可以对于多个应用程序共同地形成链路表TBL11-TBL13和节点表TBL21-TBL23。在该情况下，减少了链路表和节点表的存储区。

[0179] 可替代地，虽然对于每一个应用程序形成链路表和节点表，但是共用于这些应用程序的信息可以被存储在用于多个应用程序的公共链路表和公共节点表中。在该情况下，在不降低与链路和节点相关的信息的读出效率的情况下，减少了存储器区。

[0180] （修改）

[0181] 将参考图15至17来说明对设备10的修改。导航设备10具有与在图10中的设备相同的硬件结构。由电路19执行的表形成处理的内容的一部分和在表形成处理中形成节点表的一部分不同。

[0182] 导航设备10产生用于存储信息的公共节点表TBL30，它是在节点表TBL21-TBL23中公共的。此外，设备10产生用于应用程序的表TBL31-TBL33。表TBL31-TBL33被准备来使得从节点表TBL21-TBL23中删除不同于节点编号的公共拥有的信息。

[0183] 具体地说，如图15中所示，在根据示例性实施例的修改的导航设备10中的控制电路19当电路19从地图数据输入部件13读出在对应网格中的地图数据并且向RAM19c中输入地图数据时，在应用程序中产生专用地图数据MA1-MA3，该专用地图数据MA1-MA3存储链路表TBL11-TBL13和节点表TBL31-TBL33。此外，电路19产生作为应用程序的公共内容的公共节点表TBL30。

[0184] 图16A示出公共节点表TBL30的数据结构。图16B示出在路线搜索地图数据MA13中存储的节点表TBL33的数据结构。图16C示出在路线引导地图数据MA12中存储的节点表TBL32的数据结构。

[0185] 如图16A中所示，公共节点表TBL30包括在每一个节点中的节点数据。该节点数据具有彼此相关联的以下项：节点数量、在节点处连接的链路的数量、其中排布了连接到节点的链路的链路编号的链路连接信息和示出节点的节点坐标的节点坐标信息。根据图12，在上面的示例性实施例中的节点表TBL21-TBL23中公共地拥有该信息。

[0186] 如图16B和16C中所示，用于每一个应用程序的节点表TBL31-TBL33包括在每一个节点中的节点数据，该节点数据包括与节点编号相关联的节点详细属性信息。节点详细属性信息特定于对应的应用程序。具体地说，与图12作比较，通过删除在节点表TBL21-TBL23中的公共信息来准备用于每一个应用程序的节点表TBL31-TBL33，并且，该公共信息包括连接到节点的链路的数量、链路连接信息和节点坐标信息。在该修改中，仅在节点表中形成公共表。具体地说，不形成公共链路表，以便链路表TBL11-TBL13与在图12A和12B中相同。

[0187] 在表形成处理的步骤S100中，电路19通告形成表，如图13中所示。在RAM19c中形成用于对应网格的每一个应用程序的公共节点表TBL30、链路表TBL11-TBL13和节点表TBL31-TBL33，并且，公共节点表TBL30、链路表TBL11-TBL13和节点表TBL31-TBL33的每一个是空表，以便每一个表TBL30、TBL11-TBL13和TBL21-TBL23的内容是空的。然后，与上面的示例性实施例类似地执行步骤S110-S170。然而，在步骤S150中，取代在图14中的链路起点数据登记处理，执行在图17中的链路起点数据登记处理。在步骤S160中，执行链路终点数据登记处理，使得在用于应用程序的公共节点表TBL30、链路表TBL11-TBL13和节点表TBL31-TBL33中登记节点数据，然后，完成表TBL30、TBL11-TBL13和TBL31-TBL33。

[0188] 具体地说，在图17中的链路起点数据登记处理中，执行步骤S210-S280。然后，进行到步骤S400。在步骤S400中，在节点数据中存储与节点数据登记目标节点对应的节点编号、与节点耦合的链路的数量、链路连接信息和节点坐标信息，然后，在公共节点表TBL30中登记节点数据。

[0189] 基于在节点数据登记目标节点的链路连接信息中指定的主题节点的链路连接关系，根据在地图数据输入部件13中存储的地图数据来产生在路线搜索节点数据中存储的节点详细属性信息。在步骤S410中，在路线搜索节点表TBL33中登记节点数据，该节点数据存储了主题节点的节点编号和节点详细属性信息。

[0190] 此外，基于在节点数据登记目标节点的链路连接信息中指定的主题节点的链路连接关系，根据在地图数据输入部件13中存储的地图数据来产生在路线引导节点数据中存储的节点详细属性信息。在步骤S420中，在路线引导节点表TBL32中登记节点数据，该节点数据存储了主题节点的节点编号和节点详细属性信息。

[0191] 此外，基于在节点数据登记目标节点的链路连接信息中指定的主题节点的链路连接关系，根据在地图数据输入部件13中存储的地图数据来产生在绘制节点数据中存储的节点详细属性信息。在步骤S430中，在绘制节点表TBL31中登记节点数据，该节点数据存储了主题节点的节点编号和节点详细属性信息。

[0192] 因此，在用于对应程序的每一个节点表TBL31-TBL33中登记了节点数据登记目标节点的节点数据后，进行到步骤S320。在步骤S320中，通过按1计数来总计节点编号V。

[0193] 在该修改中，执行上面的链路起点侧数据登记处理。此外，在链路终点侧数据登记处理中，将节点数据登记目标节点设置为在主题链路的终点的节点。与在图17中的链路起点侧数据登记处理类似地执行链路终点侧数据登记处理。因此，在用于应用程序的公共节点表TBL30和节点表TBL31-TBL33中登记在主题链路的终点处布置的节点的节点数据。

[0194] 在该修改中，完成用于应用程序的公共节点表TBL30和节点表TBL31-TBL33。

[0195] 当参考用于每一个程序的节点数据时，参考公共节点表TBL30的节点数据和对应节点表的节点数据，因为公共节点表TBL30的节点数据和对应节点表的节点数据与节点编号相关联。因此，根据节点数据来执行应用程序。

[0196] 在根据示例性实施例的修改的导航设备10中，在公共节点表TBL30中存储与在节点表中的节点相关的信息，该信息共用于应用程序并且包括链路连接信息。具体地说，在公共节点表TBL30中存储了关于与节点耦合的链路的数量的信息、链路连接信息和节点坐标信息。用于程序的节点表TBL31-TBL33存储不同于在公共节点表中的信息的用于应用程序的节点的信息。因此，在该修改中，节点表的数据量减少，使得提高了节点数据的读取效率。此外，用于存储节点表的存储区被有效地减小。虽然在该修改中不产生公共链路表，但是可以通过获取在链路表TBL11-TBL13中公共的信息来产生公共链路表。

[0197] 在上面的实施例中，上面的数据结构可以用于不同于导航设备的设备。具体地说，在诸如蜂窝电话的移动终端中装入的地图数据可以具有上面的数据结构。

[0198] 在上面的实施例中，以顺时针方式与主题链路相邻并且与主题链路耦合的链路的链路编号被描述为起点连接链路编号或终点连接链路编号。可替代地，以逆时针方式与主题链路相邻的链路的链路编号可以被描述为起点连接链路编号或终点连接链路编号。

[0199] 连接链路编号，即起点连接链路编号和终点连接链路编号，可以是以链路编号的降序或升序与同一点耦合的链路的链路编号，从而描述链路连接关系。例如，如图6A中所示，当链路L0-L3的链路编号具有链路编号L2>链路编号L1>链路编号L3>链路编号L0的关系时，在链路L0的链路记录的连接链路编号中描述链路L3的链路编号，在链路L1的链路记录的连接链路编号中描述链路L2的链路编号，并且在链路L2的连接链路编号中描述链路L0的链路编号。

[0200] 利用连接链路编号，当基于连接链路编号来有效地参考与同一节点耦合的多个链路的所有链路记录时，获得主题节点的链路连接关系。具体地说，当以链路编号的降序来描述连接链路编号时，设备10可以以从链路列表Lb2的顶部起的顺序来访问与同一点耦合的链路的链路记录。

[0201] 在本实施例中，在存储介质中存储的地图数据被转换为链路表TBL11-TBL13和节点表TBL21-TBL23（或节点表TBL31-TBL33），然后，所转换的地图数据被写入作为操作存储器的工作存储器中。当读出地图数据时，地图数据输入部件13复制在RAM19c中的存储器介质中存储的地图数据。基于所复制的地图数据，形成链路表TBL11-TBL13和节点表TBL21-TBL23（或节点表TBL31-TBL33）。然后，在应用程序参考的RAM19c的另一个区中存储链路表TBL11-TBL13和节点表TBL21-TBL23（或节点表TBL31-TBL33）。

[0202] 地图数据存储器模块对应于其中存储了地图数据输入部件13的存储介质中存储的地图数据的RAM19c的区域。工作存储器对应于其中存储了链路表和节点表的RAM19c的区域。

[0203] 与链路的属性信息和链路的两端相关的属性数据包括作为诸如链路长度和车道数量的链路的属性的信息。此外，属性数据包括作为链路两端的属性的信息，诸如是包括起点/终点连接链路编号和交通灯的存在的链路记录、限速数据控制记录和组合链路规则记录等。

[0204] 上面的公开具有以下方面。

[0205] 根据本公开的一个方面，一种用于基于地图数据来执行处理的电子设备包括：地图数据存储器，用于存储所述地图数据；工作存储器；以及CPU，用于从所述地图数据存储器读出所述地图数据，并且用于将所述地图数据发展到所述工作存储器内。所述CPU基于在所述工作存储器中经发展的地图数据来执行所述处理。在所述地图数据存储器中的所述地图数据提供了道路网络，所述道路网络是通过多个单元链路和多个链路连接关系来定义的。每一个链路表示道路的一部分。每一个链路连接关系表示在连接点处的链路之间的连接。所述地图数据包括在每一个链路中的属性数据。所述属性数据提供了对应链路的属性和对应链路的端部的属性。所述端部的属性包括在所述端部的所述对应链路的连接关系信息。所述CPU根据所述属性数据来产生节点表。所述节点表存储在作为与多个链路耦合的连接点的每一个节点中的链路连接信息。所述链路连接信息提供了在对应节点处彼此耦合的所述多个链路的标识。所述CPU将作为经发展的地图数据的所述节点表写入所述工作存储器内。

[0206] 在上面的设备中，当在所述工作存储器中发展所述地图数据时，所述CPU产生用于示出在对应节点处的所述链路连接关系的链路连接信息，并且产生用于存储所述链路连接信息的节点表。因此，即使所述地图数据不包括所述节点数据，并且所述链路连接信息被分布和描述在每一个链路的属性数据中，所述CPU也可以根据所述节点表来指定在每一个节点处的链路连接关系。因此，因为所述CPU参考所述节点表，所以限制了用于所述节点的处理负荷。因此，即使当所述地图数据被紧凑化时，也提高了与所述节点相关的处理性能。

[0207] 可替代地，在对应链路的端部的对应链路的连接关系信息仅示出一个链路，所述一个链路作为在与对应链路的端部耦合的一组其他链路中选择的连接目标链路。因此，当在每一个链路的属性数据中存储了链路连接关系信息时，需要参考彼此耦合的每一个链路的属性数据，以获得在该节点处的连接关系。因此，虽然减小了地图数据的数据大小，但是需要用于获得在节点处的连接关系的步骤。因此，当增加用于形成节点表的步骤时，有效地减小了用于获得关于节点的信息的处理负荷。

[0208] 所述导航设备包括多个参考所述地图数据的应用程序。所述应用程序包括：绘制程序，用于在显示设备上绘制地图图像；路线搜索程序，用于搜索到目的地的引导路线；路线引导程序，用于引导道路，诸如引导到所述目的地的路线、引导在所述车辆前方的交通规则（例如，临时停车和右转/左转禁止）以及引导诸如右转车道或左转车道的车道。所述导航设备独立地执行每一个应用程序。因此，当将所述地图数据发展到所述工作存储器中时，所述地图数据被发展（即，转换）为用于每一个应用程序的数据。例如，所述节点表被形成为使得在所述节点表中存储相对于对应应用程序的足够和必要的信息。具体地说，除了所述链路连接关系之外，所述链路的属性和所述链路的端部的属性包括关于道路和交叉位置的信息，诸如交通灯的存在和交通规则等。然而，当执行所述绘制处理时，可以不必提供关于所述交通规则的信息，诸如右转/左转禁止。因此，根据所述应用程序，不从所述地图数据获取不需要的信息，而是从所述地图数据获取必要的信息，以便形成所述节点表。在该情况下，提高了所述应用程序的处理效率。

[0209] 根据上面的这一点，所述处理可以包括多个应用程序。所述CPU基于在所述工作存储器中经发展的地图数据来执行每一个应用程序。所述节点表包括多个专用节点表，其中每一个专用节点表对应于相应的应用程序。所述CPU产生作为经发展的地图数据的一部分的每一个专用节点表，并且将所述专用节点表写入所述工作存储器中。每一个专用节点表包括针对对应应用程序可用的关于每一个节点的信息。关于对应节点的信息包括所述链路连接信息。在该情况下，当在每一个应用程序中形成所述节点表时，在所述应用程序的处理中，获得与所述节点相关的必要信息，从而减小处理负荷。

[0210] 可替代地，所述CPU可以根据所述属性数据来产生多个专用链路表。每一个专用链路表对应于相应的应用程序。每一个链路表存储与相应的应用程序对应的在每一个链路中的专用链路属性。所述CPU从在所述属性数据中的对应链路的属性来获取用于对应应用程序的、关于每一个链路的信息，以便产生所述专用链路属性。所述CPU将多个专用链路表和多个专用节点表作为经发展的地图数据写入所述工作存储器内。在该情况下，因为所述CPU产生用于每一个程序的链路表和节点表，所以在所述应用程序的处理中，有效地获得与链路和节点相关的必要信息。因此，减少了所述CPU的处理负荷。

[0211] 可替代地，每一个应用程序可以包括任务。所述CPU响应于来自在一个应用程序中的任务的请求，来产生与所述一个应用程序对应的一个专用链路表和对应的专用节点表。在该情况下，减少了用于节点表和链路表的在所述工作存储器中的存储区。

[0212] 可替代地，所述处理可以包括多个应用程序。所述CPU基于在所述工作存储器中的经发展的地图数据来执行每一个应用程序。所述节点表包括公共节点表和多个专用节点表。所述公共节点表包括共用于多个应用程序的信息。每一个专用节点表对应于相应的应用程序。所述CPU产生作为经发展的地图数据的一部分的所述公共节点表和所述多个专用节点表的每一个，并且将所述公共节点表和所述多个专用节点表的每一个写入所述工作存储器中。所述公共节点表包括针对多个应用程序可共用的关于每一个节点的信息。在所述公共节点表中的关于对应节点的信息包括链路连接信息。每一个专用节点表包括针对对应应用程序可用的关于每一个节点的信息，该信息不同于在公共节点表中的关于对应节点的信息。在该情况下，减少了用于存储节点表的存储区，因为在所述设备中维护所述公共节点表。

[0213] 可替代地，所述CPU可以根据属性数据来产生多个专用链路表。每一个专用链路表对应于相应的应用程序。每一个链路表存储与相应的应用程序对应的在每一个链路中的专用链路属性。所述CPU从在所述属性数据中的对应链路的属性来获取用于对应应用程序的关于每一个链路的信息，从而产生所述专用链路属性。所述CPU将作为经发展的地图数据的所述多个专用链路表、所述公共节点表和所述多个专用节点表写入所述工作存储器内。

[0214] 此外，每一个应用程序可以包括任务。所述CPU响应于来自在一个应用程序中的任务的请求，来产生与所述一个应用程序对应的一个专用链路表和对应专用节点表。

[0215] 可替代地，在每一个应用程序中不形成所述链路表和所述节点表，而是可以形成公共链路表和公共节点表。在该情况下，在应用程序的整体上减少了用于存储这些表的存储区。

[0216] 虽然已经参考本发明的优选实施例来描述了本发明，但是应当明白，本发明不限于这些优选实施例和结构。本发明意欲涵盖各种修改和等同设置。另外，虽然有优选的各种组合和配置，但是包括更多、更少或仅一个部件的其他组合和配置也在本发明的精神和范围内。