（车辆工程专业论文）基于车载电子地图的目的地查询和路径优化.pdf

镦i 论文基于车载电子地蹬的嗣舱地查询和路径恍他 摘要 y 6 2 4 5 9 8 本文在v i s u a lc + + 和m a p l n f o 软释的基础上，对m a p l n f o 软件进行了二次 ”发，实现了车辆定位、圈的地查询以及到达目的地的最短长度路径和最短时 | 拄i 路径等多静功能。针对德一种功能，本文首先分柝了实现该功能的基本原理， 并在诧基礁上穗密了实臻这耱功麓多耱方案，然后放遴论上对器稀方案静键浚 点进行了分析和对比，从而确定正确的实现方案。针对每一种正确的实现方案， 本文分析了实现这个方案需要考虑的各种因素，对每一种因素应做的处理，从 嚣对该方案编霉密歪确戆实现钱鹞。稷黪代码豹实联结栗表明，零文为实现每 种功能而采取的方案以及为实现这些方案而编写的程序代码都完全正确。 关键字：车载电子地图算法定位焱询路径 塑：兰望奎堇量至塞整至堡鋈塑鎏墼塑墼塑篓整堡笾堡 a b s t r a c t an e w d i g i t a lm a p w a sd e v e l o p e di nv i s u a lc 十十a n dm a p l n f oe n v i r o n m e n ti n t h i sp a p e r , t h el o c a t i o no f v e h i c l e 、t h e9 1 a c et h a ty o uw a n tt og o 、t h e s h o r t e s t - l e n g t h r o u t eo rt h em i n i m u mt i m e c o n s u m e dr o u t eb e t w e e nt w op o i n t sc a nb ek n o w ni nt h i s m a p a c c o r d i n g t ot h er e a l i z a t i o no fe a c hf u n c t i o n ，m a n ys c h e m e sw e r ep r o v i d e d ，a n d t 晒v i r t u ea n di n a d e q u a c yo f e a c hs c h e m ew e r ea l s oa n a l y z e d 。b yc o m p a r i s o n ，ar i g h t s c h e m ew a ss e l e c t e d 。a n dm a n yq u e s t i o n sw e r es o l v e dt or e a l i z ee a c hs c h e m e ，t h e r e s u l t sh a v ep r o v e dt h a tt h es c h e m es e l e c t e da n dt h es o l u t i o nt oe a c hs c h e m ei s a c c u r a t e k e y w o r d ：d i g i t a lm a pa l g o r i t h ml o c a t i n g r o u t e q u e r y 顽十论文基于车载电子地图的目的地奁询和路授优化 1 绪论 嚆1 进瑾俊意系统( g l s ) 篱会 地理信息系统简称g i s ”3 。关于g i s 网内外有许多定义，不同的应用领域，不 猫的专堑，对它鹣理解是不一榉豹，鑫蘩还没有被营遮接渡豹定义。骞入莰荛g i s 避管理和分析空间数据的计算机系统，在计算机软硬件支持下，对空间数据按地 理坐标和空间位置进行各种处理，完成数据输入、存储、处理、管理、分析、输 嬲等功能，对数据实行有效管理，研究器辨空闻实体及糖互关系，邋过对多因素 传患的综合分街，可鞋茯逮恐获取满髭馥爱嚣要赞薅惠，并能戳鞘彩、数据、文 字等形式表示处理结果“1 。有人认为g i s 是一种特定而义十分重要的空间信息系 统，它以采集、存储、管瓒、分析和描述整个或部分地球( 包括大气层在内) 空 瓣耪逮理分东骞关戆数攥瓣窆阕售塞系缓”。应该毒焚，上述定义翅魄较秘学撼耀 明了g i s 的对象、功能和特点。从上面的些定义中w 以看出，空间数据分析怒 地理信息系统中的核心部分，也是地理信息系统有别于计算机辅助设计( c a d ) 靛关键所在。程地理售息系统基础上发燧起来的电予媲圈，它不仅蛰重提高缝图 的表现力，两盥强调遣圈鼹分析和应用功能。空闯数攒分析是指魏壤信息系统麓 用户提供的解决问题的方法。 车载电予地图中的交通网络具有很强的空间特铽，而g i s 技术具有强大的空 | 1 | i l 数据攥终、管理与分撰凌耱，这瑗它与车载毫子戆鞠戆结舍戒菇登然。g t s 不 但用来管理交通网络的空间数据，还必颁为外部的交通网络分析横凝提供分析工 具、参与分析过程、显示和输出分析的结果等。这使得车载电子地图功能的实现 裁够借助予g i s 分辑手段聪变褥更加方便。 1 2 电子地圈的简介 电子蘧强不佼翼毒逡灏戆内涵，露曩篷遣理空阕数攥或蒸数字羹羹溪爱主要戆 一种可视化衮达形式，它以地图数据麾为基础，以数字形式存储予计算机外存储 器上，以只读光盘、网络等形式传播，以桌面计算机成触摸屏计算机等形式提供 夫众镬弱。 电子遗图与数字地图的送澍：数字魄图是指用数字形式描述缝闰要素的属 性、定位和关系信息的数据集合是存储在计算机中可以识别的媒体上的一组描 述地理实体的坐标和属性标识的离散数撼的集合。丽电子地图是数字地图在电予 硕士论文基于车载电子地图的目的地查询和路径忧化 群幕上的祷母位显示”1 。 1 3 电子地豳的研究逻状和意义 随着社会经济的发展，电子地图已缀深入到社会的各个角落并发挥着巨大的 作用。在国内，电子地图越步1 9 8 1 年到1 9 8 5 年，此时电子地图的些规范开始 测定出来。1 9 8 6 年至g 现在。泡子建强豹麟究被到入我阉“七五”泼关课题，势 慧作为全国棼妻的研究领域，已逐步和国民经济建设藕结合起来，并澈得了重要滚 腥和实际应用效益。此后率载电子地图才作为一个独藏的分支快速发展起来，并 广泛应用于擎辆与交通领域m ， 国际上黛产电子螗强鹣公司骞穰多，骞静戳就麓囊娃， l 较萋袭懿毫子堍圈 数据生产厂商有：a m e r i c a nd i g i t a lc o r p o r a t i o n ，c h a l kb u t t e ，e r d a s m e r i d i a ns y s t e m so y ，s p a c ei m a g ee o s a t ，s p o ti m a g e c o r p o r a t i o f f ，w o r l d r e s o u r c e si n s t i t u t e 等”1 。在我国，笼蒺是进入w t o 叛嚣，簸事3 s 枣场并发、 经营领域的单位数量如雨詹春笋般迅速增长，这些单能都壹接或间接地制作和使 用电子地图。但是，由于豳家对地图的编制、出版有潜较为严格的规定，对地图 数据开放程度捐对国外保守，所以在国内合法的研发魄子地图的单使相对较少， 瓣藏还没奏骚鼗俸为皎入繁建豹强。 随着人民生活水平地掇高人们对以电子地图为核心的汽车导航系统地要求 越来越高，人们开始把汽辩导航系统性熊的好坏作为自己是否购买的标准之一。 瓣邀子遣圈对予汽车导藏系统豹准礁撵震秘导靛系绞提供绘乘客蘩惠量豹多少 越着决定作用，提高车栽电予地图的功徽将直接导致汽车在市场的竞争力，这对 于提高我国的综合国力和人民的生活水平有着极其重凝的作用。 1 4 漂曩麓研究詈的爱主要内赛 本项目的主要内容是针对当今电予地图某些不究普的地方进杼改进，如车 键定整、基鹃逡套淘功载及爱捷终径戆遮择。针对蠛蠢豹车载毫予缝圈遂豢没 霄提供车辆定位的功靛，在我们所研究的车载电予地图添加这一功能；针对现 存的车载电子地图所提供的查询类型单，在我们所研究的车载电子地图将夜 这上面进行究善，使它更符合人们的鬻簧；针对现存的车载电子她图都是以最 簸豹薅径当露最饶路径，繇不是禳舞黎客靛吴俸要求来鬣定最俊辫径，本课繇 研制的电子地图将会包括刹达目的地的最短长度路径和最短时间路径，这样可 以使用户选择自己感兴趣的最优路径，从而使车载电子地图更好地为乘客服务。 硕， ：论文基于筚载电子地图的圈的地查询和路径优化 2 。1 概述 2 车载电子地图的数据库设计 在对车载电子地图中的数据库进行设计时，首先蒙考虑设计数撰库主要目 的，以及为了达到这个磐的在设计数据库废该选取的数据模型。我们所研究鲍车 载魄子地燃主要功能霄：( 1 ) 车辆定谴，( 2 ) 翻的地黉询，( 3 ) 到达髫鹣地 的激短长度路径鞠簸短拜重黼路径。我稻在设计数攒瘁的鞠标就是傺诞邋些功辘侠 速、准确、可靠地实现。 2 2 车载魑予地燕拳数据库的獗究肉客 建立筚载电予地图数据麾 i 寸，主要考虑汽车所逡行韵交道网络的袋达。交通 特缎是交遥网绣掰其育的属性，在客观世界申可以被难一标识姻要索“”。通常， 交邋特征霹黻分为0 维、1 缝、2 维鹣。箕泽0 维与l 缭特征楚擒成交遴瓣络酶 基础，2 维特征程交道鼢络中或者用0 维表达，或者通谶0 维与l 维特征复合表 达“3 。在我们掰设计的率载电子地图墅，主溪采用的是0 维与1 维相结合的方法 袋菠达。 为了实现率载电子地图功熊，曾先要对各种交通要索倍崽进行综念分析，崔 交通潮络模型中肖4 个基本娶索，分别为交通区域、交通特征、事件与事件点“。 事件包攒交通特授粒壤性、耪遴特性获发生在交通特征上的偶然现象、突发拳彳牛 等。属往主要包撬类蘩、速度黻锈、名称、檬谈等入为逡义的特征僖慧及交通流 量等可能舆有时杰分布特征的专题信息“。物理特性包括道路铺设材料、倍弩灯 等客观存在的特征要素。事件w 分为点事 牛和线事件。将交通特征纳入攀件范畴， 可淡方镬臻述蕊瞧麓发生麓分毅变纯，稻分致羰遮等。8 2 3 车载毫予地豳的数括模型分析 弼弼谈车载电子迪图中的数瓣痒髓够绦证箕渤熊俊遴、醺礁、霹靠魂实现， 我们在设计数搬痒对，定骚做好数据建模工作，而建模工作的关键就是数据 模型的确定。数据模型必须支持举载电予地图中所商功能的实现，它是牙发育 效数瑟簿藏羯静最羹癸任务。程革羧电予逑霆中建立羧爨瘁孵，爨露用豹数撼 模型就蹙平谣数撼模型和菲平面数据模型。 硕十论文基于乍载电子地图的目的地查洵和路径优化 2 3 1 车载电子地图中平面数据模型分析 平面数据模型在交通网络中的应用十分普及。它的优势就是简单和普及，在 平面数据模型中，弧段与节点之间的关系在概念是一致的。也就是说，交叉弧段 始终产生一个交叉节点。虽然平面数据模型简单和普及，但它也有许多局限性， 下面我们对它局限性进行分析。 首先，平面数据模型的全连通性阻碍了车载电子地图的许多功能的实现。比 如洗，在线特征的任何交叉无论是物理意义上的交叉点或者是统计意义上的 交叉点，平面数据模型的全连通特征总要在交叉处产生一个节点，标志为路段的 起点和终点，这使得在现实中可能连续的特征被分割成许多小的、完全独立的分 段”1 。比如，在道路转弯处，实际上在整个转弯处的线特征相同，而通过平面数 据模型就把这个线特征相同连线分成几个独立的路段。 其次，平面数据模型在描述存在具有转向限制的交叉点处，平面数据模型要 通过额外的表来存储转向信息”1 。而这一切使得平面数据模型在弧段一节点拓扑 关系的一致性、拓扑自动化及网络分析中的优势被完全放弃了。为了把一个十字 路口的所有转向描述清楚，转向表至少要包括表2 3 1 1 中的字段 表2 3 1 1 转向表结构 在表2 3 1 ，1 中，a r c l # 与a r c 2 # 分别为起始弧段与目标弧段，i m p e d a n c e 为转向 阻抗系数。每个节点处的方向变化数等于该节点所连接的弧段数的平方，这样， 一个普通的十字路可能有1 6 种转向方式。在实际中，交通网络中的交叉点成千 上万，而为了表达清楚所有的转向，就必须建立成千上万个转向表，而且这些表 之间没有什么联系。在数据库中如何对这些毫无联系的表进行操作、管理、和维 护也是让我们极其头痛。 再次，平面数据模型在描述存在高度差的两条道路时，必须通过额外表来存 储高度差信息。因为在平面数据模型中，道路之间的拓扑关系( 连通关系) 是 通过弧段一节点拓扑属性表来隐式表达，由于平面强化的限制，交叉的道路在交 叉处分享节点，使得在现实中并无交叉的位置可能产生非拓扑节点。为了准确地 表达实际情况( 如：立交桥等具有高度差的道路交汇处) ，需要在交叉点处另增 存储高度差的信息表，这样使得数据库的操作和维护变得极其复杂。 2 3 2 车载电子地图中非平面数据模型的分析 从上面的分析中可以看出平面数据模型虽然简单，但在描述交叉点的转向限 硕： 呛文基于乍载电子地图的目的地商向和路径优化 制和具有高度差的道路交汇处具有严重的不足。非平而数摒模型是一种与平而数 据模型相刈的另+ 科r 数据模型，下面将围绕非平面数据模型如何表达交通特征来 进行分析。 ( 1 ) 车道属性数据表达 在车载电子地图中，交通特征的变化往往是和车道密切相关的“”1 。首先，同 。条道路的不同方向车道往往具有不同的交通特征，如在上下班的高峰期，进出 城区的同一条道路的不同方向车道具有显著不同的车流量。其次，同一条街道不 同方向车道与邻街车道往往有不同的拓扑关系”。我们在为车载电子地图建立数 据库时，是以车道为基本建模目标。车道属性表可以记录车道的平均交通流量、 路面等级等描述性信息。在我们所研究的车载电子地图中，主要是把上面的所有 因素考虑进去，使它们对同一辆车的平均车速影响等同于路阻系数对该车平均车 速的影呐。这样在建模和后面的分析时，只需考虑车道路阻系数，而不需更多地 去考虑其它的车道属性，这也为后面的最短时问路径算法分析带来了极大的方 便。 ( 2 ) 车道时态数据表达 我们建模时，是以车道作为基本建模目标。在车载r 乜了地图所基于的城h 交 通网络中，车道交通量具有明显的时态特征，一条车道在一天f r j 不同时段交通流 量可能存在显著差异，此外交通网络中某些车道还具有分时段禁行的特征”。交 通流量的变化明显地影响了车辆的平均车速，而这又影响了到达目的地最短时问 路径。对于上面的问题可以采取两种不同方案：第一种方案是每一条道路行车速 度可以用对应的速度概率分布来表示，这在实际应用中很不方便：第二种方案， 对每条车道分段保留一个时态属性集，在时态属性集中，对应工作日的不同时段， 有着不同的车速。通过交叉路口的行车时间也不是一成不变的，在不同的时段， 由于交通量的变化，通过同一交叉口可能需要耗费不同的时间。在我们所研究的 车载电子地图中，由于只研究车载电子地图的基本功能的实现问题，比如况，到 达目的地的最短长度路径算法和到达目的地的最短时间路径算法，所以我们在数 据库建模时，只选择了一个时段各个不同车道的路阻系数，以反映车辆在不同道 路上的平均车速。对于在某些车道禁行信息也必须在数据库中得到反映，我们通 过把路阻系数设为o o ( 无穷大) 。当然我们可以随时改变某条车道上的路阻系数， 随后我们会发现到达目的地的最短时间路径也随着路阻系数的改变而不停地改 变。 ( 3 ) 车道转向关系表达 从卜节的描述可以看出，平面数据模型在描述交叉点的转向关系时存在严 重不足。在非平面数据模型描述交叉点的转向关系时，主要是描述在交叉点处车 硕士论文 基于车载电子地图的目的地奁询和路径优化 道之间的拓扑关系，即各车道之间客观存在的交叉点处的转向关系，转向关系可 以通过表2 3 2 1 来表达”。 表2 3 2 1 转向表结构 在表2 3 2 1 中，l a n e i d 是网络中标识车道的唯一代码。t u r n _ i d 是同一 车道上标识各转向的唯一代码，o f f s e t 为转向起始车道位置。t o l a n e 为位于另 一条道路或街道上的目标车道，与车道属性数据表中的i d 值对应。 t o f o r w a r d o f f s e t 为在目标车道上相对转向的下一个转向点位置，i m p e d a n c e 为阻抗系数。 下面介绍非平面数据模型是如何描述交叉点和道路交汇处的转向关系。在平 面数据模型 图2 3 2 1 立交桥示意图 中，为了清楚地说明图2 3 2 i 中的转向关系，必须在交叉点处存储一个转向表 和一个高度差表，但这样将会给后面的数据库操作和维护带来极大的不便。通过 非平面数据模型，可以简单、快速、准确地表达图2 3 2 1 中的转向关系。为了 更清楚地说明问题，可以把立交桥的模型进行抽象成图2 5 中的形式，同时作些 并不影响说明问题实质的假设，如o f f s e t = 0 2 k m ，t o _ f o r w a r d o f f s e t = 0 2 k m ，t u r ni d = l 。图中线段上的l 、2 、3 、4 为l a n e i d 的值。 2 1 3 图2 3 2 2 立交桥的几何模型图 这样就可以用表2 3 2 1 所示的表结构来描述立交桥上的所有转向。因为图 2 3 2 1 中所描述的转向关系实际上只有l a n e j d = 1 到l a n e i d = 4 的转向和 l a n e i d = 2 到l a n e i d = 3 的转向，所以图2 3 2 1 的转向关系可以用表2 3 2 2 清楚、正确地表达出来： 硕士论文基于车载电子地图的目的地查询和路径优化 表2 3 2 2立交桥的转向表 11o 240 21 2 22o 23o 21 2 从表2 3 2 2 中可以看出，采用非平面数据模型，使得不允许的转向方式 在拓扑关系表中不予表达( 在平面数据模型中，每一个交叉点或者道路交汇处都 包含固定的1 6 条记录) ，这样不仅节省了存储空间，而且加快网络搜索过程。 在我们所研究的车载电子地图中，其电子地图数据库的设计充分运用了非平 面数据模型的思想。即在十字路口处，不再把十字路口的交叉点看作车道的起点 和终点，以避免在该交叉点建立多余转向表和对该表实施多余的遍历( 因为每一 个交叉点对应了1 6 条记录，即使某些转向不存在，也要对它进行遍历，判断它 是否存在) 。根据非平面数据模型的思想，在十字路口处不设节点，而是像图 2 3 2 3 中描述的一样，弧段直接从一条车道进入另一条车道。这样建立起来的 弧段与其它弧段没有什么区别，在计算到达目的地的最短长度和最短时间路径 中，就可以很容易地处理十字路口处交叉点的问题。 图2 3 2 3 车道弧段 在图2 3 2 3 中，细线表示街道或道路上的车道，粗线表示我们建模时所用的车 道弧段。从图中可以清楚地看出车道弧段的起点和终点都不是十字路口的交叉 点。它是从街道或道路上的某一点开始，也是从街道或道路上的某一点结束。这 种建模时所采用的车道弧段也避免了在十字路口之问道路存在高度差所带来的 转向限制，如立交桥等。 2 4 车载电子地图中数据库的建立 2 4 1 基于实现查询功能的数据库建立 车载电子地图中数据库是其查询功能的基础，数据库的好坏直接影响查询功 能的实现与否。在我们所研究的车载电子地图，其查询主要分为类型查询和具体 查询( 类型查询就是当你选择一种感兴趣的类型时，车载电子地图将告诉你这一 类型的点或区域在地图中的具体位置，具体查询就是当你在类型查询的结果中选 择一具体点或区域时，车载电子地图显示该具体点或区域在地图上的位置) 。为 硕士论文基于车载电子地图的目的地查询和路径优化 了实现查询功能而建立的数据库比较简单，在数据建模时，根本就不用考虑是采 取乎垂数摆模型还是袋取萋乎瑟数爨模型，对予黉鍪奎诲有薅耱方法：蒡一耱方 法就是把所有类型的点成区域放在一个表中，然厝选出该类型的点或区域；第二 种方法就烧把每一种类型的点或区域建成同一个数据库表，当淼询某一类型的点 或区域时，打开该类型熊表就可以实现类型查询。对于具体点域区域的查谗，我 们不翊专门的建立数瓣簿表，只要邋过简单的数据露操作就可戳选出该具髂悫或 区域。 2 4 2 基于实瑗最短长度嚣最短时阕路径功能的数据瘁建立 为了实现到达目的地的最短长度和最短时间路径，在数据建模时，必须考虑 到不同的道路属性、在j 筵路交叉口处的问题处理方式、以及点釉道路之间关系建 立方式等颡素。 为了能够顺利地实现两点问最艇长度和最短时问路径，在建立车载电子地图 数据库时，结合了平面数据模型和非平面数据模型的优点。平筒数据模型最大的 毯势裁楚麓单窝普及，棼乎瑟数据羧霆的霞势是功麓强大，姆鞠是在卡字爨嗣豹 交叉点处和存在高度麓的道路交汇处。为了利用节点一弧段数掰模型的简单，在 数据建模时，首先考虑到采取节点弧段这种数据类型，而在实际中，道路或街 道上不同方向上的车道屣性不一定宪金裰同，所以应该采取分剐对待的方式，戬 使我们在建立电子逢圈新采取的数撂模垄更符合实舔情况。考虑实际情况，必须 对节点一弧段这种平面数据模型加以改进，使得猩平面数据模烈中没有方向的一 条弧段变成方向相反的两条弧段，在这罩把节点一弧段这种平馘数据模型和非平 瑟数据埃麓中车道愚憋结合莛亲( 在这里霰设了不弱方淘豹车邋弧段终秀令点豹 位置相同，即该弧段的起点与相反方向弧段的终点相同，该弧段的终点与相反方 向弧段的起点相同，这种假设完全不影响到达目的地的最短长殿和最短时叫路径 鲍实现) + 波2 ，4 2 1 爰是通过以上懋怒形成的。 袁2 4 2 。l 车遁弧段表结构 在表2 4 2 1 中f r o m p o i n t t d 是车遂弧袋静起点，t o p o i n t l d 燕莩道弧毅戆终点， s e c t i o n i d 标识车道弧段的唯一代码，l e n g t h 为车道弧段的长度，i m p e d a n c e 为 车道弧段的路阻系数。通过表2 4 2 1 可以清楚看出同一条弧段在不同方向上的 不同属陵。鲡强2 。4 。2 。1 ，嚣个瑞点数标号分别为p o i n t i d = l 鄹p o i t i t i d = 2 ， 假如该弧段的s e c t i o n l d = l ，l e n g t h = i 5 k m ， 硕士论文基于车载电子地图的目的地查询和路径优化 o o 图2 4 2 1 两点涮的路段 i m p e d a n c e = 1 ，那么就可以用表2 4 2 2 来对图2 4 2 1 进行描述 表2 4 2 2 车道弧段表 1211 5l | 2ll o2 52 从表2 4 2 2 中可以清楚地看出同一条弧段在不同车道上所表现出来的不同属 性。首先是起点和终点的对换。其次，在不同车道上同一弧段的路阻系数不同， 这完全符合实际情况。 对于十字路口的交叉点处和具有高度差的道路交汇处，我们将发挥非平面数 据模型的优点。也就是像上面描述的一样，首先，不把车道路段的起点和终点设 在十字路口的交叉点处及具有高度差的道路交汇处。这样就跟上面说的一样，避 免了为交叉点专门建立转向表，避免了不必要的搜索，节省了存储空间。再次， 对于在十字路口的交叉点和存在高度差的道路交汇处的所有转向限制，我们可以 只列出具有转向的路段，这样就可以清楚地看出在交叉点和交汇处的所有转向限 制。另外，在交叉点和交汇处所列出的转向车道弧段路段可以像其它的路段那样 进行处理，这样大大方便了车载电子地图的各种功能的实现。 为了在最短长度路径算法和最短时间路径算法中更好地操作路段表和点表， 同时为了使路段表和点表更好地关联起来。可以对非空间数据模型的路段表进行 改进。在未改进之前道路交叉处的表结构如下： 表2 4 2 3 车道弧段表结构 在表2 4 2 3 中，l a n e i d 是网络中标识车道的唯一代码，t u r n i d 是同一 车道上标识各转向的唯- - 4 4 码，o f f s e t 为转向起始车道位置，t o l a n e 为位于另 一条道路或街道上的目标车道，与车道属性数据表中的i d 值对应， t of o r w a r do f f s e t 为在目标车道上相对转向的下一个转向点位置，i m p e d a n c e 为阻抗系数。从该表的结构中可以清楚地看出各个车道的转向关系，但用陔结构 建立起来的表无法与点表建立联系，这给实现到达目的地的最短长度和最短时问 路径带来不便，因此必须对该表结构进行修改，在我们所研究的车载电子地图中 是用f r o m p o i n t i d 和t o p o i n t i d 两个字段来取代o f f s e t 字段和 t o f o r w a r d o f f s e r 字段。改进过后道路交叉处的表结构如下： 表2 4 2 4 改进过后车道弧段结构 硕士论文基于率藏电子地圈的弱躲地套灞萃【 潞髓谯 七 在表2 4 2 4 中f r o m p o i n t i d 怒车道弧段的怒点，t o p o i n t i d 是车道弧段的 终点，s e c t i o n i d 橡谈车遥弧段懿礁一代码，l e n g t h 为车邋弧羧翳长度， i m p e d a n c e 为车道弧段豹路阻系数。这样傲的好缝有；第一，腭o f f s e t 嚣l t o f o r w a r d o f f s e t 来描述车道的起点和终点没有用f r o m p o i n t i d 和t o p o i n t i d 瓣起来直淡；麓二，修改过螽的表终梭与非道路交叉处娓表结梭稳阔，从藤馒搽 佟表缝稳懿佘令交褥筒攀裰统一；麓三，修改过后熬波缝梅更容赫与点表据美暇， 从而使路段浅釉点表能够裔机地结合淼起，这为实现到达目的地的最短长度路 径和最短时间路径提供了极大的方便。 2 5 本意小节 本章蓠先分耩了在车载电子地鼹中建立数据艨驻装考虑数主簧内容，然屠 觚车载电予蟪阁要实瑷鼹功戆密发，分撰了为了实瑷这些动能在建立数撵簿救注 意的问题一数据模型。本牵分析了在建立数据库时常采用的两摹申数攒模型平磷 数据模型和非平面数据模溅。然后分柝了在车载电子地图中实现车辆定位、蟊的 怒套询和戮达瓣豹地鲍黢艇长度鼹经鞠黢短时闻黪较等功髓，建立数摄疼眩霈黉 考虑鲶嗣豢，以及如傍缝合磷萃孛数攒模瀵懿优点米解汝这些润戆，疆詹建立了掰 需要的数攒瘁。 硕士论文基于车载电子地图的目的地查询和路径优化 3 车辆定位模块的设计 3 1 车辆定位模块的工作原理 计算机表达图形最大的困难是图形系统包含了一系列元素的内在空间关系 “3 。在描述图形相互关系的表格中，如果想把各种关系都描述清楚将会导致表格 极其复杂。因此，必须建立一个详细的规则来描述这种关系，使计算机能够清楚 地“认识”这些点、线、区域、所代表的对象，并知道对象的确切位置及与其他 对象的相对几何位置。 表达地理空间有两种常用方法：第一种是矢量数据结构，它能够精确定位空 间位置，它假设地理空间是连续的，而不是量化为相互独立的小栅格。在矢量数 据结构中，点用独立的空间坐标对表示，线用一系列的坐标对表示，面是由首尾 相连的线构成的多边形：第二种表达地理空间的方法是量化空间，也就是把南京 市的地图分割成一系列单元，每个单元代表有限的地理空间，单元可以是任何几 何形状，只要所有的单元能够组合成南京市地图即可”1 。为了简便起见。很多软 件都采取了正方形作为网格单元。 由于地图被分割成很多的离散网格，当网格化分得足够小的时候，栅格数据 结构就能提供接近与正确的地理位置”1 。一个点用一个网格单元表示，而不是用 其绝对位置表示，这是用二维数据表示0 维对象的变通方法。同样，线段或一维 对象用一系列相互连接的网格单元表示，这也改变了维数用二维数据表示一 维对象。线段上的每一个点用一个网格单元表示，即线段上的每一点都必须落在 其中的某个网格单元中。显然这种数据结构表示很不规则的直线时，会出现不连 续性，用网格表示区域时，也是不连续的，一系列邻近的直线围成一个区域，区 域中所有点肯定落在其中的某些网格单元中，这些网格单元就成了区域的一部 分。区域的形状越不规则，边界就越不连续。 在基于格网和栅格的系统中，有两种方法可以赋予实体( 对象) 属性数据： 第一种方法是为每一个单元赋予一个数值代表属性( 如行政区域) ，这样根据属 性值的分布就可咀表示实体的位置，每个单元在所给的地图中只有一个属性值； 另一种方法，其实是第一种方法的扩展，它把网格单元和数据库管理系统联系在 一起，一个单元可以有多种属性，它的使用可以减少必须存储的数据量，而且也 可以很容易地同其他数据结构建立关联，在数据库管理系统下进行数据的存储、 查询与处理。”1 在我们建立南京市车载电子地图所用的软件平台正是采取后者， 这样就可以把空间地图对象的直接表现能力和数据库的高效管理和分析能力有 效的结合在一起，使车载电子地图中的定位、搜索、最短时问路径和最短长度路 硕士论文基予车载电子遗强弱嚣酶遣查询鞘鼹径缆纯 径等功能的实现成为可能。 掇榜数据结构不麓准确定位，只麓是近戗子璇确选定位，这是由于援格攀元 只具有稳对位置。线表现为接线特，鬣鞠连接的一缀两格单元，酝域剩表现蠢= 维 形状特征相连接的一组网格单元。 在栅格数据结构中，网格单元尤其是正方形网格单元组合在一起形 或一个区域，兹提是嚣竣瑟是乎遂戆，| 舞渡在我销掰采露茨较锈中采曩豹楚繁卡 儿坐标系，那么网格单元的位置就爨接近空间位徽，因为笛卡儿坐标系采用的地 图投影可以近似地表示三维地球表面。 3 2 车辆定位模块斡实现 3 2 1 车辆定位模块的实现方法 在我们所研究的举躐电子地图中，车辆定位采取了抽象方法，那就是把现实 中的车抽象成地图中的点，一辆车对应地图中的个点。这样就可以轻松地实现 车辆定位。因羹我 f 】熊铁g p s 接收仪中报轻松裁 ! 鼯到车辆戆经发帮纬度，擞掇经 度值和纬度值，使用软件就可以在城图找到与该赢坐标值最鞠澈栅格单元，在该 单元处用一定的程序代码画出汽车符号，这样就可以很清楚地橱出汽车在地豳上 所处的位鼹。因为网格蹲元画得足够小，所以汽车在地图上显示的位置与真灾情 况箱差不戮0 1 米，这究全麓够满愁实际需要。 在上丽的阐述中，并没有提到连续定位问题。连续定位问题就是进行多次定 位后再进行一次定位所出现的问题。当运用南京市车载电子地网进行了第一次定 位时，软 拳会雳一令渣楚的图标显示事辍在遗图上戆位霉。当遴嚣第二次定位瓣， 如果对第一次所画出豹汽车符号不做处理，将会得到这样的结粜，第三次定位时， 车载电子地图将会在邋当的位置画出第三个汽车符号，紧接着第四个汽车符号， 第五纛至很多很多的汽车符号，以至驾驶员部分不清哪一个是网i 才一次定位 所产生静符号，这裁产生连续定霞鞫题。 解决上面问题的关键就是在产擞第二个汽车符号时如何对第一个汽车符号 进行处理。有两种处理方法，第种方法那就是把汽车抽象成个移动的嫩标。 蔽车辍定搜模涣戆王露琢理可噬蓍蠢；当撂翘汽车在建国土数懋搽蘧( 经魔镶帮 纬度值) 时，软件就可以找到与该坐标值最相近的栅格单元，通过编程在该她画 出汽车符母，这样就轻易地实现了率辆定位。把汽车当作移动的坐标时，进行第 二次定位时，它不再是创建第二个汽车符号，丽怒把汽车符号从第一次定位的地 方移动强第二次定位静髓方。它的缺点就是关麓车载电子遗圈时，没有及辩渍除 硕士论文夔于擎载电子她豳的爨的地蠢谗和路授优纯 掉定位所用的定位符号，这使得每次刚汗始使用车载电子地图时，总是保昭了上 一次定位衙蘩下鲢汽车褥峰。 第二秘方法就是在产囊第二令汽车符号露联去第一个汽车籀譬。它数饯点藏 是能避免第一种方法所带来的缺陷，并且实现越来也非常方便，所以我们在车辆 定位对取繁二秘方法。 3 2 。2 车辘定位模浃的实税进程 上瑟瑟缀详细魏讨论了如秘鲡道自己楚在溅蒂的位萋，遁遥什么方法采实凌 这一过程。上露戆两孽孛方法款悬爨都笼怒汽车撼象戏谬动静蹩拣，第一零孛方法裁 是直接把汽车符号从一个攫标移到另一坐标处；第二= 种方法就是首先把汽车符号 从第一个坐标处清除，然艨在第二个坐标靛位爨萋谶汽车镑号( 霹以看 乍阀接壹| 廷 移动汽车符弩) 。上丽已缀讨论过了采用第二种方法的应用，观夜讨论在第= 种 方法静黎疆上鲡褥实现汽攀靛连续定位淘题。 上节融经阐述了实现在车载电子地图上连续斑位的思路和方法，这一节将 摄舞上一节掰描述静思路讨论车辆定位瀚实现j 篷程，实现过程熟潮3 。2 2 i 。 圈3 ，2 2 。l 实现车辆定位的流程图 在流程豳中，可以看出实现车辆定位的赘个过稔，英步骤为：( 1 ) 辩交鲞邀行一 系列黔窃始纯， | 冀螯蠖彦焱矗瑟袋褥它们，缤鬈糕黪蓠先登矮簧考感囊这点。 硕士论文簇予车栽逛子地圈的舅驹地查询释路经忧他 ( 2 ) 编写对话框，在对话框中有接受坐标值的编辑椴，以便接受从g p s 定位仪 那里传黉毛的缀发僮和纬度使。( 3 ) 在接受耨坐标值之前，为了避免涟续定穰阀戆， 必须对上一次定垃嫒疆下戆定疰符号谶嚣娃理，在遮罴我霞袋弱戆方法是赢接秘 除上一次定位所留下的定能符号。( 4 ) 搬接受到的坐标值传给程序处理模块。( 4 ) 程序处壤攘块壤摆传入戆经度篷秘纬痰疆在蟪阁上找到与该坐拣篷最接运的酃 个栅格单元。( 5 ) 在栅格单元处绘制汽车定位符号。 以后每一次车辆定位，程 序都敲第三步开始到第五步结束，第三步到第嚣步怒程序中的循环俸，每一次怒 使都将执行它。 3 2 。3 车辆定位模块缒实现结果 为了孬渣楚车辆定位模块整个王 乍过程，本节将按照上巍斡懋鼹一步一步地 进行操作，瀛到最后结果韵输出。 第一步，为了建褥车载邂子遣穗能按照我们翡婺求送行车辆定位，奁避纾懿 体地定位之前蒙做一犊准备工作。准备结束后，得到图3 2 3 1 。 爨3 ，2 ，3 1定镪墩备图 第二步，根据汽率6 p s 接收系统得绷的坐标值进行输入。在我们所臻究的车 裁电子地图中，由于没有做把g p s 接收系统的数据读入到计算机内存中去的模 块，所以直接避行坚标值输入。为了熊够使输入酶数据及时愁传至g 程序处理穰块 孛，必缀霄一个燮撼壤攘载图，它必簇熬有妇下功戆：( 1 ) 後蹲我们够方蠖蟪 进行坐标值输入：( 2 ) 能够把接收到的数据及时传给程序处理模块。图3 2 3 2 是裁够实臻以上嚣耪功戆瓣怼话疆，它淡霹鞋方便数撰竣入，又黢及时建糍数据 传给程廖处联模块。 颂士论文蒸于窜鼗电子地鲻的鳗的遣查询积路径俊化 瞬3 ，2 。3 。2 坐标值的接收鼹 在图3 2 3 2 中，可以褥出在编辑稽中已经商默认酾经度德和纬度值，这是牢刃 始化的结果。由于没有傲把g p s 接收系统的数据读入到计算机内存中去的模块， 所班只好假定已经知道了g p s 接收系统提供的坐貅值，然掰把嫩标值输入到编 辑捱，誊较深按锈辩，藤3 。2 2 2 将会荛璧拣蕊臻绘程黪楚簿模头，阉瓣激 活程序处理模块，糨序处理模块将会根据传入的坐标值在地图上查找与该坐标 蕊最袋近戆嚣令撵楱攀元，并在该褥貉擎元载中夹缝绘裁汽车寇经餐号，遮榉 将在地图二漫示汽车现强腰处的位置。经过上蕊熬搡作，可以搿剽图3 ，2 3 。3 所示结果。 霆3 2 。3 3 汽车定位鬻 在溪3 。2 ，3 3 中，霹以渍楚楚瓣出摄辗输入魏懋撂氇进行定经熬结栗，毽遗 并不能装明已经避免丁连续定位所出现的问题。为了验证是否会出现连续定位问 题，必须在第一次进行定憾震紧接麓进行第二次定俊。第二次定位魄步骡跟第一 次定位的步骤一样，荫先怒坐标豹输入i 违程，圈3 2 + 3 4 给擦了坐标值的接收髑 硕士论文基于车载电子地图的目的地查询和路径优化 图3 2 3 4 第2 次坐标接收图 从图3 2 2 4 中可以看出，经度值和纬度值比图3 3 中的数据分别多了0 0 1 ， 从理论上讲，汽车符号要在地图上向上和向右移动经度值和纬度值相差0 0 1 的 距离。根据以上分析，为了避免连续定位问题，在进行第二次定位时，将会清除 第一次定位时产生的定位符号，同时产生第二次定位符号。所以当按下o k 按钮 时，经过程序处理模块处理后，将会得到图3 2 3 5 所示结果。 图3 2 3 5 第2 次定位图 从图3 2 3 5 中看出汽车定位符号的移动完全跟理论分析结果相同，而且进 行第二次定位时对第一次定位所产生的汽车符号处理也非常干净利落。 3 3 本章小结 本章主要分析了在地图上进行车辆定位的工作原理，分析了实现定位所采取 的方案，分析了在实现方案过程中所出现的各种问题，以及在编写程序的过程中 如何处理这些问题，并以实际结果验证了方案和问题处理的f 确性。 硕士论文基于车载电子地图的目的地查询和路径优化 4 目的地查询模块 4 1 实现目的地查询的工作原理 在我们所研究的车载电子地图中所提供的查询服务主要是目的地查询和路 径查询，其中目的地查询包括类型查询和具体点查询。在这里，类型查询就是查 找具有同一种类型的点或区域的集合，具体查询就是查找具体的点或区域，如司 机想知道某个具体学校在城市中所处的位置时，只要在查询类型中输入学校( 或 医院、风景点、政府机关、等) 时，立即会在地图上显示所有的学校，这就是类 型查询，然后就可以在学校这个下拉列表中选择具体的学校，这时该学校的位置 就会在地图的正中央显示，这就是具体查询。下面将详细地讨论实现这些功能的 工作原理。 在电子地图中，主要通过数据模型中的图形元素和数据库系统结合起来，利 用两者的优点，实现目的地查询功能。很明显图形数据结构和模型足以处理实体 数据，但不能进行复杂运算，例如查询运算：数据库系统虽能进行复杂运算，例 如查询、更新、删除等操作，但不能进行图形实体操作，这需要两者结合起来。 为了实现这一想法，可以把图形的坐标和形状数据存放在独立的存储文件中，把 属性表图形实体的属性数据独立地存放在现有的商业数据库系统中，连 接主要通过相应软件实现，连接方式主要是在属性数据库中存储一系列的标识 码。 4 2 实现目的地查询的方法分析 为了实现查询，要把所要查询的数据建成数据库。在我们研究的车载电子地 图中，数据被组织为描述地图上图形对象的记录，相关的一些记录组合成一个数 据库表。所有的数据库表组合成一个数据库。数据库不同于一般的平面文件，它 既包括数据也包括元数据，元数据主要是由每条记录中的字段( 诸如类型、名称、 长度等属性) 、在每个表中的记录位置、用于查找表中记录的索引等构成。通 过对这些元数据进行操作就能实现查找。 实现目的地查询有两种方法：第一种方法就是把所有类型的点、线、和区域 的信息放在一个数据库表中，一个数据库表组成数据库，然后运用结构化查询语 言对数据库进行操作，以得到自己想要查询的结果：第二种方法就是把同种类型 的点、线、或区域的信息放在一个数据库表中，也就是把同种类型的信息做成一 个图层，多个图层进行叠加就形成一个包含所有信息的数据库，然后在层的基础 硕士论文基于车载电子地图的目的地查询和路径优化 上运用结构化查询语言对已知数据库进行操作，从而得到想要的结果。 运用第一种方法进行查询分析时，优点是数据库容易维护，且查询操作简单。 缺点就是不能屏蔽其它类型的信息，如你想知道南京市里各个学校的具体位置， 图4 2 1 给出了该查询的程序代码。 s e l e c t ( 其中的 代表所选择的表中的所有列) f r o m p o i n t ( 包含各个实体的表) w h e r e 类型= “学校” 图4 2 1第一种方法的类型查询 当执行完图4 2 1 所示程序代码后，只是用特殊符号地标出类型为学校的点，它 不可能屏蔽其它类型的信息。因为在我们所工作的软件环境里，只有首先打开包 含用户感兴趣点信息的表，然后才能在该表上进行s e l e c t 操作，而打开包含该 表时，该表的所有信息一定会在车载电子地图中显示。s e l e c t 操作只是用而基 于图层的类型查询却能有效地屏蔽其它类型信息使得用户可以轻松地查看自己 所需的信息。 第二种查询方法实际就是基于图层的查询方法。这种查询方法的优点是能屏 蔽无用信息，只显示有用信息。如在车载电子地图中查找学校这一类型信息，就 可以知道所有的学校在地图上的位置，而医院、车站、风景点等无用信息将不会 显示。第二种查询方法的缺点是地图的图层化过程复杂。 地图的图层化过程也就是把整个的南京市地图中的各种类型分离开来，然后 对每一种类型分别进行数字化，如在车载电子地图中建立学校图层，首先建立一 个新图层，取名为“学校”，这时数据库会自动建立表名为学校的表：然后在给 出的基图中绘出该校的具体几何位置，同时输入每一个学校的所有属性，这样就 完成了一个学校的数字化过程，而m a p l n f o 软件会把地图上具体学校的位置和表 中该校的记录建立一一对应关系当完成所有学校的数字化时，一个学校图层就 形成了。因为地图由一级道路、二级道路、三级道路、政区区域、山峰、河流、 医院、学校、商店、车站等类型所组成，所以图层化过程非常复杂。 在我们研究的车载电子地图中，所用的查询方法是第二种查询方法。 硕士论文基于车载电子地图的目的地查询和路径优化 4 3 实现目的地查询的程序代码分析 4 3 i 实现某一类型的查询分析 上面已经分析了实现目的地查询的方法和途径，本节将讨论如何实现这种思路和 想法。在图层的基础上实现查询分析主要有三种方法：第一种方法就是使用g i s 软件本身的二次开发语言进行开发，第二种方法就是在v c + + 环境里进行集成开 发，第三种方法就是用v c + + 加控件的方法。第一种方法和第二种方法过分依赖 于g i s 软件本身功能，第三种方法则相对独立于g i s 软件，这非常有利于电子地 图功能的扩展。在我们研究的车载电子地图中，是采用第三种方法实现目的地查 询。为了在图层的基础上进行查询分析，在数字化南京市地图的过程中，要注意 把不同类型的点或区域做成单一的表，只有在这个前提下，才能在图层的基础上 实现目的地查询。 首先打开一些辅助图层，以便让感兴趣的图层能够更清楚地显示，图 4 3 1 1 说明了添加辅助图层的部分程序代码： v o i dc s e l e