郑振贵，马洪兵，陈从华

(1.清华大学 电子工程系，北京 100084; 2.厦门雅迅网络股份有限公司，福建 厦门 361008)

0 引 言

电子地图(Electronic Map)又称数字地图，通常将地图数据以数字方式存储并通过计算机系统处理后，最终在电子设备屏幕上显示地图数据信息[1]。随着数字空间数据的广泛应用以及计算机技术的不断发展，电子地图也越来越深入普通用户生活中，如今在社会的各个领域几乎都能看到电子地图服务的应用。然而，电子地图应用功能的不断扩展，对电子地图空间数据的组织和利用的要求也就越来越高。特别是以电子地图作为核心的定位服务、智能交通系统，电子地图数据的容量过大、更新不易等问题往往成为在这些应用领域的一个“瓶颈”。因此，如何建立一种高效、优质的电子地图数据结构具有重大的意义[2-5]。

1 地图要素的组织

1.1 多层级的区块划分

由于大容量的电子地图数据不适合一次性读取并进行操作，即使全部读取后往往也不需要全部进行显示，这样大大浪费了电子设备有限的资源。采用区块划分的方式组织地图数据，能明显减少电子地图显示设备的资源消耗，缓解强势数据与弱势资源之间的矛盾[6]。

传统的地图数据格式（KIWI、SDAL等）在进行区块划分时往往采用了集成、分割格网等复杂的逻辑结构，以不规则多边形或者存在重叠的拓扑关系进行组织。这种方式在进行地图数据增量更新和维护时显得过于烦琐复杂，小部分的地图数据改动可能牵扯到大量的逻辑结构调整。针对上述问题，本文采用了一种更为高效且易于维护的多层级区块划分方式。

首先，采用规则矩形格网进行区块划分，即在同一地图显示层级内按照相等的矩形划分出多个区块，区块内的地图要素信息存储在该区块的地图数据中，从而确保每一个地图要素的位置可以被唯一地确定。每一个地图要素必须是完全包含在一个区块或跨多个区块，如图1所示。

图1 地图要素按区块划分Fig.1 Block division of map elements

任何地图要素如果其几何形状延伸超过一个以上的区块，则按区块边界进行修剪并且修整的各个部分被分配到相应的区块内。

其次，为满足用户在不同尺度上观察地图要素的分布及相互关系的需要，采用多个层级尺度的形式来表达地图要素的详细程度。不同层次下区块的大小不同，层级越高区块越大，层级越低区块越小。地图要素在高层级的区块存放的数据比较粗略，而在低层级的块存放的数据比较详细，随着层级由低至高的变化地图要素会被综合，次要的信息将被过滤掉，以满足用户对多层次地图显示详尽不一需求[7]，如图2所示。

图2 地图多层级区块划分Fig.2 Scale level of map elements

电子地图的多层级的表达本质上是满足了用户的视觉认知要求，不同层级的地图展示过程中,用户对于地图要素的认识也得以深化[8]。在最终地图应用上，当地图需要显示更大比例尺的范围，高层级的地图数据便能支持快速显示细节较少的大面积区域。另外，类似长距离路径规划的应用，可以很快地计算和考虑到更重要的道路类型。当地图应用需要显示更小比例尺的地图详情，如街区道路及建筑以及短距离路径规划应用等，低层级的地图数据由于含有更多的地图细节信息便能更好地支持这些场景[9]。

这种地图数据多层级的区块划分方式，由于相同层级下区块间不重叠，不同层级的区块相对独立，不用像传统的地图数据格式那样维护复杂的区块逻辑结构，进行地图的增量更新时也仅仅将对应层级的区块数据替换即可，从而提高了地图更新的效率和稳定性。

1.2 地图要素分类

所有真实世界的对象都可以被电子地图以一个或多个地图要素在不同层级上展现。地图要素按照空间矢量数据组织的基本形式一般分为点、线和面三种要素主类[10]。

点状地图要素一般是不能按比例尺表示，只能按点定位的符号标识，如行政区标识、POI等；线状地图要素主要包括道路、水系和边界等能够在地图上通过多点连线进行展示的地物或符号；面状地图要素一般是具有复杂形状的地物，其形状可近似由一个或多个多边形的组合来展示。每个要素主类又根据地图要素的具体功能划分出多种子类，如图3所示[11-14]。

图3 地图要素的分类Fig.3 Classification of map elements

同个区块下的相同种类的要素数据存储在同一个集合当中，并且通过各自的要素子类来区分具体的地图要素类型。

在传统的电子地图数据格式中，为了提高计算的效率引入了许多复杂的抽象要素类型，从而导致要素结构庞大，要素的信息过于分散。相比之下，本文提出的地图要素模型结构更为简洁、要素间的关系更清晰，而且同类地图要素的数据结构上一致，集中存储对于地图数据的操作以及更新也更加容易。

1.3 地图要素索引

为了在地图数据中识别和查找不同的地图要素，通过要素所在的区域索引、区域内要素类的索引以及该类要素中的偏移索引来标识一个地图要素数据[15-16]。各类型的索引功能见表1。

表1 地图要素的索引类型及用途Tab.1 Index type and use of map elements

查找处于不同区块的地图要素时，先通过要素的区块索引确定对方属于哪一个区块，再根据要素类索引确定要素属于该区块下的哪一个要素类集合中，最后根据偏移索引定位到要素类集合中的指定要素，索引过程如图4所示。

图4 地图要素的索引过程Fig.4 Index process of map elements

这种采用区块、要素类、偏移三个索引来标识一个地图要素的方式，相对别的电子地图要素索引方式具有更好的灵活性，使用时也更加直观，方便上层应用进行分析和管理，提高数据操作的效率。

2 要素属性的组织

2.1 固定属性与可选属性

地图要素的属性描述了要素附带的不同功能的细节，随着电子地图功能的不断扩展，地图要素附带的信息也越来越丰富，要素属性也就越来越复杂。地图要素属性组织是否高效灵活，将影响电子地图数据的质量及功能的扩展。

传统的电子地图格式中（如SHP、TAB格式等），地图要素数据及其附带的属性数据通常具有较强的耦合程度，并且在存储上将同一要素的属性数据集中在同一数据结构之中。这样的属性数据组织方式，在地图要素的新增时往往改动及影响较大，不利于地图功能的扩展。

为了更好地组织要素属性数据，根据属性特征将其分为：固定属性、可选属性两种类型进行组织。其中，固定属性描述了地图要素的不可缺的基本特征，其与地图要素存储在同一块数据结构上，常见的固定属性如道路的类型、POI的名称等。可选属性作为描述地图要素的扩展和补充，因此不一定所有的地图要素都拥有，并且各可选属性集中存储在数据结构上与地图要素分开，常见的可选属性如道路的限速等。可选属性与地图要素通过要素索引进行关联，即每一个可选属性集数据中都会含有各可选属性关联的地图要素索引。

区分固定属性和可选属性的数据组织方式，一方面使得要素固定属性的读取和操作更为便捷；另一方面减少了可选属性与地图要素间的耦合程度，使得可选属性的扩展更为方便和灵活。

2.2 可选属性组合

在地图要素中存在关联关系的多个可选的属性可以合并成一个属性组合，组合中的属性又分为主属性和次要属性两种类型：主要属性定义了该属性组合描述的主要规则，可与一个或多个次要属性进行组合，但不能与另一个主属性同主；次要属性定义了规则适用的条件。

这种属性组合提供了对真实世界情况更加柔性的建模，如一个地图道理的要素中，包含一个限速的属性组合，该组合中主属性为行驶速度上限值，而次要属性为限速针对的特定车辆类型，或者限速的时间段等。

3 地图要素与属性的关联

3.1 属性映射的结构

地图要素的可选属性按照其属性类型被单独存储在一起，这样的好处是可以减少数据存放的冗余，也方便针对属性进行增量更新。由于可选数据和地图要素不在一起，因此地图要素和属性需要通过属性映射进行关联。属性映射中包含要素属性值和相应的地图要素的索引。在地图区块数据中，属性类型和地图要素类型的每个组合都必须设置独立的属性映射。如果一个属性映射包含多个属性类型，则表示该映射中含有属性组合，如图5所示。

图5 单类型和多类型属性映射Fig.5 Single and mulitple type attributes mapping

3.2 属性映射的类型

属性映射的类型，分为一对一映射和一对多映射两种，一对一映射即该属性映射中的属性或属性组合只属于一个地图要素，而一对多的映射类型可以将属性或属性组合引用给多个地图要素。这样具有相同属性的多个地图要素只要在对应属性映射中添加该地图要素的索引即可，如图6所示。

图6 一对多属性映射Fig.6 One to many attributes mapping

一对多属性映射，由于一个属性可以映射给多个地图要素，因此，在数据存储空间上可以减少很大的冗余，另外，对于地图数据的更新也将更加方便[13]。

3.3 属性映射的快速查找

当电子地图的应用程序通过直接解析属性映射数据来获取所需的地图要素属性时，解析过程中就会遇到其他不需要属性类型，这样要素属性查找效率就会受到影响。为了提高对地图要素指定类型的属性查找效率，在建立属性映射数据的同时，生成一份针对属性映射数据的属性类型索引列表，用来快速定位指定属性类型的属性映射，进而找到指定的属性值。每一个属性类型索引数据包含属性类型值、属性映射的偏移两个部分：其中属性类型值与该索引指向的属性映射中的属性类型值一致；属性映射的偏移即该索引指向的属性映射在属性映射集合中的位置。属性类型索引与属性映射的匹配过程如图7所示。

图7 属性类型索引与属性映射的匹配Fig.7 Matching the attributes type index with attributes mapping

4 数据模型的应用实验

实验利用本文中提到的电子地图数据模型，呈现一个简单的电子地图区域，并以一个具体的数据更新实例，验证该数据模型增量更新的效果。

需要呈现的地图区域包含高低两个层次，其中高层次包含4个区块，低层次则对应的有16个区块。该地图区域包含的地图要素见表2。

表2 实验中包含的地图要素Tab.2 Map elements in the experiment

实验中对地图数据读取和操作流程主要有以下几个步骤：

1）读取地图显示范围所在的区块数据；

2）按照地图要素分类解析要素集合；

3）解析地图要素的可选属性集合；

4）解析具体地图要素的固定属性；

5）查找并解析具体地图要素的可选属性；

6）通过可选属性识别各地图要素的关联关系及具体功能；

7）根据显示顺序将解析完成的地图要素进行绘制。

地图的呈现利用Open GL在PC上进行地图符号的绘制，其呈现效果如图8所示。

图8 应用实验的地图呈现效果Fig.8 Map rendering experiment

图8 中，左边的效果图为该实验的高层次地图数据，并且将其包含的4个区块边界用红线标识，可见各区块彼此之间没有重叠，且各地图要素按照区块划分；右边的效果图为对应左图中第一个区块使用低层次地图数据时的呈现，其又被划分为更小的4个区块，且相比高层次地图数据，其数据内容更加丰富多样，呈现的效果也更加详细。

实验通过新增一条道路数据来验证电子地图的增量更新效果，具体情况如图9所示。

图9 电子地图增量更新前Fig.9 Before the electronic map updated

新增的道路数据涉及图9示意的区块3，因此，更新操作将针对区块3中道路类数据集合及其相关属性集合进行，更新后的地图数据变更如图10所示。

图10 电子地图增量更新后Fig.10 After the electronic map updated

由此可见，本文提出的电子地图数据模型在进行增量更新操作时，只要编辑增量数据所属的区块中的特点要素类集合或属性集合相关记录即可，如果在实际应用中地图数据使用类似SQLite等数据库进行存储，则具体的更新操作表现在对发生更新的数据库表中的一行进行新增或替换操作，其优势将更为明显高效。增量更新前后地图呈现的效果如图11所示。

图11 电子地图增量更新呈现效果Fig.11 Incremental updating experiment of electronic map

5 结束语

随着各种电子地图的位置服务应用需求的不断增加，空间地理数据的内容也越来越丰富、复杂，对电子地图数据的组织效率、合理性、扩展性的要求也越来越高。在这种应用背景下，本文提出了一种高效、易于操作和扩展的地图数据组织模型：通过对电子地图进行多层级的区块划分、地图要素分类管理存储以及建立统一的索引机制，提高了地图数据的读取和查找效率；将地图要素属性分为固定和可选两种性质类型区分管理，可选属性又能通过组合的方式关联一个或多个地图要素，这种要素属性的组织方式提高了地图数据的利用率和扩展性，减少了数据冗余程度；采用属性映射作为地图要素与要素属性的索引媒介，使得两者的关联更加方便。