基于嵌入式地图数据分块组织研究

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

    近年来，嵌入式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个交点。在重建拓扑关系的时候，两次穿过格网中的线要被分成两部分重新建立拓扑，因为线是由按照一定顺序的节点以及节点之间的连线组成。当一条线从一网格射出时，如果不断开该线重建拓扑，则会出现如图6所示的情况，出现了拓扑错误。图6中的线段pp1实际上是不存在的。

    2 拓扑重构算法

    有时路网结构很复杂，一条线可能多次穿过同一网格，即一条线与网格的交点可能不只4个，如果不重建拓扑，可能会造成电子地图画面更加混乱。所以在每次求得线与网格边界交点的时候，判断该线是否从网格中射出，如果线从网格中射出则断开该线，并求得交点后重新建立拓扑关系。求得线与网格边界交点的算法如下：

    (1)假设当前网格的编码为mn。

    (2)如果线L上的一个节点P1属于当前网格mn，判断线L上p1的前一个节点P0是否属于当前网格mn，如果p1不属于当前网格mn则转到(3)；如果p0属于当前网格mn，则转到(4)：如节点p0不属于当前网格mn，如果p1在格网边界转到(4)；如果p1不在网格边界上则求P0和p1的连线与网格边界的交点p，并把p的信息保存到网格mn中，转到(4)。此时p节点属于网格mn。

    (3)如果线L上的一个节点P1不属于当前网格，判断p1在线L上的前一个点P0是否属于网格mn，如果p0不属于网格mn，则转到(4)。如果节点p0属于当前网格mn，此时线L从网格mn射出，如果p0在网格边界，转到(4)；如果p0不在网格边界则求P0和P1的连线与网格mn边界的交点p，把线L断开重建拓扑关系。并把p的信息保存到网格mn中，转到(4)。此时节点p属于网格mn。

    (4)如果线L上的点处理完毕则返回，否则继续(2)，直到线L上的所有点处理判断完毕。

    流程图如图7所示。

        3 数据分级组织

    导航系统在使用过程中，用户的兴趣点不同，会放大电子地图查看某个区域更详细的信息。把电子地图数据分级适合地图缩放功能的实现。假如电子地图最初显示的地图为x级，放大一次就是显示x+1级地图，缩小一次就显示x-1级地图。

    如图8所示，浏览x级地图，假设x级地图显示m(m=4)块格网的数据；此时地图放大一级变成x+1级地图，如果地图放大了s倍(s=2)，此时重新读取地图数据，只需读取m／s2块网格即可。相反，如果地图缩小一级，x-1级地图需读取的网格数为m×s2(16块)。

    
    不同级别的地图数据显示的内容不同。在缩放最小一级地图时，只显示地图的区界和背景。假如把地图放大到某一级别，此时电子地图显示地区名称、高速公路以及名称、铁路等地图信息；再次把该电子地图放大一级则显示当前城市的主要地区名称和主要路段。放缩的级别划分根据不同的地理情况处理。可以认为，高级别的地图是对低级别地图的补充。

    电子地图数据包括地物点、线、区域等。地图的属性分为地区名称、学校名称、公司名称等，线又分层划分为一级道路、二级道路、三级道路、水系等。基于上述电子地图数据的特点，根据中国行政单位的划分，把电子地图数据分层。电子地图数据分层可以加快数据的读取，也方便电子地图数据的存储。

    4 嵌入式电子地图实现

    本文使用的嵌入式开发平台为：cpu s3c2440，64M nandflash，64M ram，1Gsd卡，480*272 LCD。本文选择QT／Embedded作为图形界面，并结合双缓冲机制QT／Embedded实现了嵌入式电子地图。

    使用双缓冲画图，是避免地图在漫游、放缩的时候产生屏幕闪烁比较常见的方法。主要过程如下：

    (1)把需要显示的网格，画在OPximap上。

    (2)通过bitblt()函数把QPximap上的图像拷贝到显示组件。

    根据LCD的尺寸划分网格大小，即网格的宽为480，长为272。某一级别的电子地图每次读取9个网格数据，此时LCD屏幕的大小和格网的大小一样，每次读取9个网格数据，其中一个网格数据显示在LCD屏幕上，其它8个网格的数据为预取数据。如图9所示，网格22部分是LCD屏幕：

    如图10所示，图像拖至左边边界。程序每次读取9个网格数据，LCD屏幕尺寸和一个网格一样大。根据LCD屏幕大小规定边界，比如图像向x轴正方向移动480像素时，即到了图像左边边界。每次拖动图像至边界，然后读取相邻网格数据，重新绘制地图，这样处理节省了系统开销，而且不需每次拖动图像的时候都要重新绘制地图而造成屏幕抖动或闪烁。

    图像向x轴正向拖动至边界如图10所示，网格21为LCD屏幕。在拖动到边界后，再次拖动地图，根据网格的编码读取其相邻的网格数据。拖动后的图像如图11所示，格网21区域是LCD屏幕。

    地图放缩时，根据放缩级别，读取相应级别的格网数据，重新绘制图像并把图像拷贝到屏幕相应位置。在本文中，电子地图数据放在sd卡来读取。

    5 结论

    依据本文的数据组织策略，不同级别的电子地图在嵌入式设备上漫游时，图像都可以平滑移动，时间延迟可以忽略，达到了嵌入式地图漫游的要求。而且依据本文的数据组织策略，建立一个合适的格网索引机制，在搜索地图和路径规划时，结合搜索算法，以网格为单位索引，也可以加快数据搜索速度。图12是地图数据测试界面。