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

分成两部分重新建立拓扑，因为线是由按照一定顺序的节点以及节点之间的连线组成。当一条线从一网格射出时，如果不断开该线重建拓扑，则会出现如图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是地图数据测试界面。