嵌入式电子地图数据分块组织研究

摘要：文章研究了基于嵌入式地图数据分块组织。嵌入式设备相对于PC机，CPU运算速度较慢，内存较小；而嵌入式设备处理大量的数据时，CPU和内存资源相对来说比较紧张。实现基于嵌入式电子地图的功能，数据存取策略比较重要。本文提出了一种电子地图数据分块组织的方法，并且使用双缓冲技术在QT／Embcdded平台上实现了嵌入式地图在设备上的漫游，放缩等功能。
关键词：嵌入式地图；数据分块组织；QT／Embedded

0 引言
近年来，嵌入式Linux得到了快速发展，它被广泛应用在移动电话、个人数字助理(PDA)、媒体播放器、消费性电子产品以及航空航天等领域中。车辆导航系统是空间信息产业中卫星导航产业的一个重要的发展领域。导航电子地图数据是导航系统的基础，其存储和组织策略是嵌入式导航系统中最基本和重要的一部分。导航是集GIS、GPS、通信、嵌入式软硬件技术为一体的高度综合性的高技术产品。在导航系统中电子地图数据量比较大，而嵌入式设备资源比较有限，所以电子地图数据组织的好坏，决定了导航系统本身的成败。

1 数据的分块的边界问题
嵌入式设备的LCD一般都比较小，本文使用的LCD大小是480×272。嵌入式设备内存也较小，不能一次把所有电子地图数据读入内存，即使能够把全部数据读入到内存，在LCD屏幕上也不能完全显示，这样大大浪费了有限的内存资源。把嵌入式电子地图数据分块组织，节省了嵌入式设备的CPU和内存资源。数据地图数据分块后，原来数据的拓扑关系被破坏，数据块的边界可能出现问题。比如一条线从一数据块中射出，因为数据块的不同，跨越多个数据块的线会出现线的断点情况，此时需要重新求得数据块边界与线的交点，重建拓扑。再者，地图中的线并不是规则的折线，可能从一个数据块中射出，而后经过弯转重新进入该数据块，数据分块的时候不考虑这个问题，就会出现拓扑错误。
本文提出了一种数据分块组织方法。即把一幅地图按照行列分成行×列个规则矩形网格(Grid)。为了便于数据的读取，给格网的每个网格进行编码。如图1所示把几条线路分割成4×5个网格。

地图分割成一定数量的规则网格后，为便于读取格网数据，需要对不同的网格编码组织。规则格网是一种普遍应用的分块方法，只需指定在行、列方向上的分块数m、n，就可以按照相等的间隔把图像区域分为m×n个子块。假如地图被分割成i×j个网格的格网，格网中的网格用“mn”、“m，n”或Grid(m,n)表示，其中m表示网格行号，n表示网格列号。简单按照行列进行编码，比较方便数据组织。如上图：从左上角开始，第一行的网格编码为00、01、02、03。这种简单的网格编码，可以很容易找到其相邻的网格，如用m表示网格的行号，用n表示网
格的列号，则编码为Grid(m,n)的网格，其左边的网格编码为Grid(m，n-1)，右边相邻的网格编码为Grid(m,n+1)，如果找其上方下方的网格，只需行号保持不变列号加1或者减1即可。如果一节点x在网格mn中，则点x属于网格mn，即x∈Grid(m，n)；如果一条线L在网格mn中，则线L属于网格mn，即L∈Grid(m，n)。
规则的格网是按照一定的长宽划分的，假如每个网格的长为272、宽为480，一个长为816宽为960的地图，就被分成3×2个规则网格。
电子地图数据包括很多元素，其中包括点、线、区域等。对于地图上的点来说，可以很容易判断其属于哪个网格。比如点p(242,400)，网格的长如果为272，宽为480，则点p属于第一个网格，其编码为00。线或区域分布在很多网格里面，这样就会与不同的网格边界有交点，实际上这个交点不一定存在。比如一条线Line，由4个节点P1、P2、P3、P4组成。Line分布在三个网格中，如图2所示。

读取格网数据时，如果没有读取到网格10和11的数据，只显示网格00的数据，那么Line会出现断点，如图3所示：

可以看出，P2和P3的点之间的连线消失了。因为，在网格00的数据里并没有P3点的信息，Line在网格00中显示的只是P1到P2的连接线。同样，如果显示网格10的数据，而不显示网格00的数据和网格11的数据，在网格10中，Line只有一个点P3，而P3到P2、P4的连接线消失了。此时需要添加节点并且断开原来的线段重建拓扑来处理连接线消失的情况。断开线段p2p3，并求得p2p3与网格00、网格10边界的交点p，此时p2p属于网格00中，pp3属于网格10。如图4所示。实际上，路段是不规则的，可能出现如图5所示的情况。

从图5可以看出，一条线从网格射出后，然后再次穿过该网格。并与网格有4个交点。在重建拓扑关系的时候，两次穿过格网中的线要被