|
|
|
|
嵌入式电子地图数据分块组织研究 |
|
|
|
近年来，嵌入式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分布在三个网格中
读取格网数据时，如果没有读取到网格10和11的数据，只显示网格00的数据，那么Line会出现断点
可以看出，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上的所有点处理判断完毕
推荐阅读：http://www.hyedu.com/oblog/u/68544/archives/2015/43334.html |
|
|
|
 相关技术论坛： |
|
| 相关技术论文： |
|
|
