嵌入式GIS中矢量数据的快速显示方法研究

黄雁，冯艳杰，孟庆祥

(1.武汉市测绘研究院，湖北武汉 430022； 2.深圳供电规划设计院有限公司，广东深圳 518054；3.武汉大学，湖北武汉 430079)

嵌入式GIS中矢量数据的快速显示方法研究

黄雁1∗，冯艳杰2，孟庆祥3

(1.武汉市测绘研究院，湖北武汉 430022； 2.深圳供电规划设计院有限公司，广东深圳 518054；3.武汉大学，湖北武汉 430079)

嵌入式GIS是近年来一个蓬勃兴起的领域，由于嵌入式设备内存小，外设容量小，CPU的运算能力较弱，致使电子地图显示时常出现延迟和抖动的现象。本文针对嵌入式GIS海量矢量数据，提出了一种改进的多层网格索引技术对矢量数据进行检索，在矢量数据的显示方面，本文采用了双缓存显示机制代替了系统默认的显示机制，主缓存用于数据的显示，备用缓存用于组织下一个画面的数据，如此提高显示效率。

嵌入式GIS；矢量数据；网格索引

1 引 言

嵌入式地理信息系统(Embedded Geographic Information System，嵌入式GIS)是新一代地理信息系统发展的代表方向之一，它是运行在嵌入式设备(PDA、掌上电脑、智能手机)上的高度浓缩、高度精简的GIS软件系统。就目前而言，嵌入式GIS已经在城市智能交通系统(ITS)、物流配送系统、车辆导航系统和信息化武器装备中等得到广泛应用，取得了巨大的经济效益。

当前，“纵向分层，横向分幅”和基于扩展关系数据库技术管理矢量地图数据在硬件资源丰富的桌面GIS系统中相对成熟，但由于嵌入式设备具有存储空间小、内存小、存取速度慢，随机访问的速度远低于顺序访问的速度等缺点，使得桌面GIS系统中成熟技术无法很好地应用在资源受限的嵌入式GIS系统中，特别是海量矢量空间数据的嵌入式存储、访问、调度和显示等，因此需要对其进行深入的研究。为提高地图操作速度，嵌入式GIS平台上管理矢量地图数据可以采用数据分块和分级的策略，减少人机交互时地图数据读取量，从而改善系统响应性能。

同时，加速矢量数据在嵌入式GIS中的快速显示，主要从矢量数据的预处理和显示机制这两个方面着手，此外还可以通过选择合适的嵌入式空间索引技术、采用缓存机制等方法加速矢量数据的显示与响应。本文就是在充分研究嵌入式海量矢量数据的存储、调度和显示机制的基础上提出快速显示方法的。

2 矢量数据网格索引

2.1 多层网格索引

网格索引是一种常用的空间索引技术，其算法较为简单，便于实现。网格索引的基本思想是将一幅地图数据的地理范围划分成m行、n列，得到m×n个小矩形网格，每个网格代表一个索引项，并分配动态存储区，记录该网格中的地理要素的概要信息，包括要素标识、存储地址和外接矩形等。通过对地图数据进行网格划分，为网格内多个地理要素建立索引，检索时检索区域仅为原来的1/(m×n)，从而提高了数据访问速度。

图1 网格索引示意图

图1为网格索引图，空间要素可能在某一个网格内，也可能同时跨越多个网格。在建立网格索引时，先将空间要素抽象成点、线、面三种类型，并按照点、线、面分别存入其相应的索引数组。

网格索引具有的优点包括:速度快、可以调整、算法简单、查询方式多样等。但也存在各种不足，如网格索引对点要素索引时较为有效，每个点都会唯一地落入某个网格中。而对于线要素、面要素，则有可能落入多个网格之中，特别是其几何形状很大时，会有许多索引项中记录了该要素的索引信息，从而造成重复存储；网格索引适应性差；对划分后的网格作进一步划分时，存在不一致性的情况，这会影响对地理要素的查找效率等。

针对网格空间索引的优点和不足，本文引入了多层网格索引。多层网格索引是对网格索引改进，它在充分利用和发挥网格索引简单、高效、易实现等优势的基础上，弥补了网格索引所存在的不足，从而更有效率地实现空间检索。

多层网格索引的基本思想是将一个图层规则地划分h次:将第一次划分作为第一层，将图层划分成m1×n1大小相等的网格，每个网格的长宽分别为l1和w1，为每个网格分配一个动态存储区，将完全落入该网格的地理要素的外接矩形MBR及标识号ID存入动态存储区，若地理要素的外接矩形与网格重合或者在网格的边界上，则认为该地理要素没有完全包含在这个网格中；第二次划分图层时，选取l2和w2为网格的长宽(其中l2和w2分别比l1和w1大，一般选择K＝l2:l1＝w2:w1＞2)，重复第一次划分时的操作，将满足条件的要素放入相应的网格中；依此循环往复，最后一次的1 ×1划分为第h层。分析可知，多层网格索引最多需划分层数h＝logKMax(m1，n1)＋1。然后开始对各层划分得到的小网格进行统一的编号，从0开始，每个编号对应一个小网格，落入同一个小网格内的地理要素有着相同的编号，即网格索引号。

这样，每一个地理要素都属于某一层某个特定的小网格，不存在索引信息重复存储的情况，这样节省了索引的存储空间，减少了做重复运算的时间开销。因此，多层网格索引技术不仅可以提高矢量数据的存取访问效率，而且可以提高空间查询、空间分析等操作的效率。

2.2 改进的多层网格索引

多层网格索引实现过程中最关键的两个问题是划分步长K的确定和第一层网格数m1×n1的确定。但要确定这几个参数，要考虑的因素也很多，包括系统内存大小、内存页面大小等系统因素以及要素类型、要素外接矩形MBR的长度比例分布、图层的空间范围、要素的平均占用空间、要素的分布情况等GIS相关因素，这些因素都会对多层网格索引的效率产生影响。本节将围绕这两个问题，对多层网格空间索引技术进行改进。改进过程中，本文暂不考虑硬件因素，仅考虑GIS相关因素的影响。

在实际建立海量矢量数据多层网格索引时，首先考虑的是网格索引参数的调配。尽管可以在多层网格索引中允许用户自行设置空间索引参数(K和m1×n1)，用户可以选取不同的值，并从中选择效率较高的参数，来提高空间索引的效率，但这也给用户造成了很大的困难。因此，一种理想的方法是，系统能够根据图层的特点与查询的效率，自动给出合适的空间索引参数，从而得到高效的网格划分。

其次是对完全包含要素的重定义。多层网格空间索引中，地理要素的网格索引号按以下规则分配:先检查要素的外接矩形是否完全落入第一次划分的某个小网格中，如不在，则看它是否落在第二次划分的某个小网格中，一直查找，直到找到一个完全包含它的小网格。常用的网格索引是如果地理要素的外接矩形与网格重合或在网格边界线上，则认为该要素不在该网格中，即没有完全包含。在改进的多层网格索引中，为了检索方便，重新定义了这个概念，将要素外接矩形与网格分界线重合的情况也归入了完全包含，这使得落入高层网格的要素数目减少。

再次是多层网格索引的编码。网格索引本身有自己的编码方式，而改进的多层网格索引显然不能采用原有的编码方式了，本文采用一种螺旋编码方式，离坐标原点越近，标识号越小，反之标识号越大，如图2所示。编码的算法如下，其中row、col、level、mi、ni、start分别表示网格划分后得到的小网格的行号、列号、当前网格层次数、第i层网格行数、列数、低层网格中行列数中较大值的平方和。

图2 多层网格索引的编码示意图

多层网格空间索引是针对线状、面状要素等具有空间范围的地理要素提出来的，主要是为了解决地理要素占用多个网格导致索引信息存储重复的问题。用户可以很容易通过设置不同的行列数，选出较好的网格划分方法，从而建立索引效率较高的索引结构，提高检索访问效率。

3 基于改进索引的矢量数据快速显示

针对海量矢量数据的快速显示，本文将从矢量数据的预处理和显示两个方面进行实现。在预处理方面，本文采用要素分级显示的方法，并建立一种改进的多层网格空间索引对矢量数据进行检索；在矢量数据显示方面，本文采用双缓存技术。

3.1 矢量数据分级显示

在GIS的常用矢量文件中，空间数据是根据要素的不同几何形状分层存储的，如包括点层、线层和面层。嵌入式电子地图绘制时，由于屏幕大小有限，如果把所有的地理要素全部绘制在屏幕上，则会造成屏幕上的要素拥挤，影响显示效果。而且该方法需把所有数据加载到内存中，而嵌入式设备的内存有限，海量矢量数据的实时显示就会很难实现。为了解决这个问题，本文引入LOD技术。

LOD(Levels of Detail)意为多细节层次，最初主要用于复杂的3D场景快速绘制、3D动画等领域，是根据物体模型的节点在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重要物体的面数和细节度，从而获得高效率的渲染运算。根据这一思想，在进行二维矢量地图的绘制过程中，地图缩小时，根据比例系数的缩小，减少无关的地理要素的显示，从而显示轮廓信息；地图放大时，根据放大的比例系数，加载必要的地理要素，从而显示更多细节的要素。这样不仅减少了内存的负担，也达到了一种“越近内容看得越多、细节情况越清楚，越远则轮廓看得越清楚”的视觉效果。如图3为使用和未使用数据分级技术的实验数据的显示效果图。

图3 使用和未使用数据分级技术的显示效果图

具体对要素进行分级时，先要参考地图要素的分级规范，根据要素的重要程度，将不同的要素划分为不同的显示等级，简单地说，即为矢量地图中的每种要素设置一个LOD参数。这个LOD参数记录了要素的显示级别，根据显示级别可以决定地图在放大或缩小到多大比例尺时才显示相应的要素。通过这种方法，在地图显示时，可以根据当前的显示比例，只显示特定的要素类。当比例尺放大或缩小时，就可以根据变化的比例尺重新确定需要显示的要素。使用这种方法，则嵌入式设备的内存中不需要载入所有图层的要素，只需要保存当前显示级别要求加载的图层。这样采用LOD技术进行要素分级，减少了内存开销，提高了系统的显示性能。

表1列出了地图分层的显示顺序及LOD参数作为参考，表中的LOD系数表示仅当显示区域的范围小于或等于“LOD系数×地图全图范围”时才显示该图层，其中LOD参数可以根据实际情况进行相应的修改。在实际操作过程中，根据ESRI Shapefile文件格式的分层存储情况，为每个Shapefile文件设定相应的名字，并设置其显示顺序，然后在不同的地图比较例尺下调试程序，通过调试确定每个图层的LOD系数，最后建立各个图层文件名、显示顺序、LOD系数、最大显示比例尺的一一对应关系。

矢量地图分级显示顺序及其LOD参数 表1

在地图绘制时，根据当前地图的比例尺，计算出要显示的图层，然后根据要显示的图层从索引中查找相应的地理要素，最后把这些要素绘制出来。在实际操作的时候，用户可以根据实际情况自己设定每个图层的LOD参数，以增加系统的灵活性。

3.2 双缓存显示机制

通过对矢量数据建立索引和分级，可以实现对数据的快速访问和调用，但是，要满足矢量数据的实时和快速显示，还需要对显示过程进行研究。在地图浏览过程中，漫游响应速度是衡量系统实时性能的一项重要指标。

“双缓存”是在原有的缓存基础上又增加了一个用于提前组织待显示的数据的缓存，它的目的是将数据处理过程隐藏起来，在处理器空闲时进行，避免数据更新过程可见导致漫游停顿现象。双缓存包括前主缓存和备用缓存，其原理图如图4所示，其运行机制如下:主缓存数据用于显示当前画面，备用缓存组织屏幕下一画面需要的数据，绘制完毕后，备用缓存通过拷贝技术将后台缓存画面显示在屏幕上，而前台刚好相反，此时又组织下一个画面的数据。这样一直循环往复，屏幕上总是显示已经绘好的画面。由于在嵌入式GIS中，两次人机交互操作的间隔时间比较长，而在这段时间内系统后台通过一定的数据调度方式存取和处理数据，预先完成了人机交互时大量的数据读写和运算操作，于是用户从屏幕上看起来系统的响应速度会得到提高。而且显示的时候是将数据一次性的拷贝到屏幕，这样可以解决屏幕闪烁的问题。

图4 双缓存原理图

图5 双缓存内存分配示意图

使用双缓存技术的内存空间分配如图所5示，首先在系统的内存中申请两块大小相同的缓存空间，把其中用于组织地图数据的显存空间作为取图虚拟屏幕，也称为主缓存；其中用来组织并绘制下一漫游画面的显存空间作为绘图虚拟屏幕，也称为备用缓存，则当前显示屏幕可以看做是游动于虚拟屏幕当中的一个显示窗口。与两个虚拟屏幕对应，需要另外开设两个数据缓存A和B，用于存储地图显示过程中所访问的数据。双缓存的代码实现主要通过Mouse Down()函数、Mouse Move()函数、Mouse Up()函数和重写On Paint ()函数实现。当鼠标点击、移动的时候，在内存中开辟一块空间用来组织数据，并绘制在虚拟屏幕上，当放开鼠标时，将该虚拟屏幕拷贝至显示窗口上，另一虚拟屏幕则等待下一次操作时使用，如此循环往复。

双缓存是嵌入式GIS中实现地图平滑的一种比较实用的方法，但该方法是以牺牲系统内存为代价提高地图的显示速度，以空间换取时间，所以采用这种方法必须有足够的内存和显示缓存，才能达到比较理想的状态。

4 结 语

本文针对嵌入式GIS系统中矢量数据的海量特点，在分析了网格索引和多层网格索引的基础上，提出了一种改进的多层网格索引方法，改进方法在保持了多层网格索引技术的优势的同时，还提高了自身的自适应能力；在矢量数据显示方面，本文参考了LOD思想对矢量数据进行了分级，根据屏幕显示比例尺的大小，加载不同的要素层，同时提出了采用双缓存显示机制，从而使用户感觉浏览起来更加流畅。

[1] 文江，朱宝山，蔡文涛，李韶芳.基于PDA的矢量图形的快速显示[J].嵌入式软件应用，2007，02(2)75～77

[2] 杨小伟，郭福生，冯军营.嵌入式GIS矢量数据存储技术研究[J].科技信息，2009(7):454～455

[3] 张丽芬，王晓华，胡景松.基于网格划分的几种空间索引[J].北京理工大学学报，2004，24(2):140～144

[4] 张丽芬，王晓华，胡景松等.基于网格划分的几种空间索引[J].北京理工大学学报，2004，24(2):139～144

[5] 梁浩，吴敏君.两类典型GIS空间索引技术的分析与评价[J].安阳工学院学报，2006，2(20):51～55

[6] 马文帅.嵌入式GIS开发方法的研究与实现[D].中国海洋大学硕士学位论文，2008

Study on Fast Displaying Vector Data in Embedded GIS

Huang Yan1，Feng Yanjie2，Meng Qingxiang3
(1.Wuhan Geomatic Institute，Wuhan 430022，China；2.Shenzhen Power Supply Planning Design Institute Co.，Ltd.Shenzhen 518054，China；3.Wuhan University，Wuhan 430079，China)

Embedded Geographic Information System(EGIS)is a new rising and flourishing domain.Because the memory of EGIS is low and small，CPU’s computing capability is weak，and the display screen is small，it would cause delay and jitter when the vector map was displaying.This paper would solve the problem of delay of vector data and present a kind of improved multi－level grid index technology to retrieve vector data.In the respect of data displaying，this paper adopts double buffer display mechanism instead of the default display mechanism of the system，the main buffer is used to display the vector map，while the auxiliary buffer is used to organize the data which would show later，and so on to increase desplaying efficiency.

Embedded GIS；Spatial Vector Data；Grid Index

2011—07—04

黄雁(1977—)，女，工程师，主要从事GIS应用研究工作。

国家自然科学基金青年基金(40801152)

1672－8262(2012)01－20－04

P208.1

A