（计算机应用技术专业论文）汽车导航引擎技术的研究与实现.pdf

摘要 汽车导航引擎，应实现地图显示、路径规划、语音引导和兴趣点检索等功 能，导航引擎的优劣直接决定整个导航产品性能的好坏。国内汽车导航系统多 基于二次平台开发，通常只能利用二次平台提供的接口或功能，极大影响了开 发的自主性和引擎功能的完善性。针对以上局限性，本文采用独立开发模式实 现引擎模块的核心部分，设计出的导航引擎结构及功能更加合理和完善。 针对道路状况和行车规则的复杂性，本文采用交叉口模型描述实际交叉路 口，根据节点一路段关系，建立基于层次网格索引的路网数据模型。在此基础 上，设计出基于新引擎构架的地图文件格式，加快了地图数据的读取速度。 地图显示速度直接影响用户体验，针对嵌入式设备资源有限，地图显示较 慢等问题，论文提出将地图数据分为背景数据、道路数据和兴趣点数据等部分， 并对其分层分块建索引，不同比例尺地图对应不同地图数据格式文件，能快速 定位到所需的数据。同时，对显示要素划分等级，每次只显示当前比例尺下的 对应级别要素，减少了数据冗余，加快了地图显示速度，增强了用户体验。 路径规划是汽车导航的核心问题。实际导航中，交通转向限制和交叉口延 误等，会造成规划结果的不准确。对此，本文采用对偶图思想建立转向限制关 系表来表达转向限制关系，能更好地配合实际路径规划。针对导航仪规划速度 慢等问题，采用结合分层策略的双向启发式融合算法，同时从起点和终点进行 搜索，并对a 算法结构和节点扩展方式加以改进。系统运行结果表明，采用此 算法，大大减少了参与计算的路段数量，节省了存储空间，提高了路径规划的 效率。 论文最后以武汉市区某范围内的路网数据为研究对象，对论文主要工作进 行实证研究和测试。理论分析和实际运行结果表明，本文所做的主要工作有效 地克服了当前导航引擎开发中的不足，极大地提高了地图显示速度，并能在交 通转向限制情况下提供有效的路径规划。 关键字：汽车导航，导航引擎，地图显示，路径规划，兴趣点 a b s t r a c t a u t o m o b i l en a v i g a t i o ne n g i n e ，s h o u l dr e a l i z et h ef u n c t i o n ss u c ha sm a p d i s p l a v r o u t ep l a n ，v o i c eg u i d a n c ea n dr e t r i e v a l so fp o i n t so fi n t e r e s ta n d s oo n ，t h eq u a l i t yo f n a v i g a t i o ne n g i n ed i r e c t l yd e t e r m i n e st h ew h o l ep e r f o r m a n c eo fn a v i g a t i o np r o d u c t s t h ed e v e l o p m e n to fd o m e s t i ca u t o m o b i l en a v i g a t i o ns y s t e mi s m o s t l yb a s e do nt h e s e c o n dp l a t f o r m ，o n l yt h o s ei n t e r f a c e so rf u n c t i o n sb e l o n gt ot h es e c o n d p l a t f o r mc a n b eu s e d ，t h i sh a sp l a y e dag r e a tr o l eo nt h ea u t o n o m yo ft h e d e v e l o p m e n ta n d i m p r o v e m e n to fe n g i n ef u n c t i o n s i nr e s p o n s et ot h i sl i m i t a t i o n ，t h i sp a p e rs u g g e s t e d r e a l i z et h ec o r ef u n c t i o n so fe n g i n et h r o u g hi n d e p e n d e n td e v e l o p m e n tm o d e t h e s t r u c t u r ea n df u n c t i o n sd e s i g n e db yt h i sw a yt e n dt ob em o r er e a s o n a b l ea n d p e r f e c t c o n s i d e r i n gt h ec o m p l e x i t i e so fr o a dc o n d i t i o n sa n dt r a f f i cr u l e s ，t h i sp a p e ru s e d c r o s sr o a dm o d e lt od e s c r i b et h ea c t u a lc r o s s i n gi n t e r s e c t i o n s ，e s t a b l i s h e dm er o a d n e t w o r kd a t am o d e la c c o r d i n gt on o d e l i n kr e l a t i o nb a s e do nm u l t i l a y e rg r i di n d e x t h ef o r m a to fm a pf i l e sd e s i g n e do nt h eb a s i so fn e w e n g i n ef r a m e w o r km e n t i o n e d a b o v e ，h a sg r e a t l yi m p r o v e dt h es p e e do fm a pd a t ar e a d i n g t h es p e e do fm a pd i s p l a yi n f l u e n c e st h eu s e re x p e r i e n c ed i r e c t l y , i nv i e w0 f p r o b l e m s ，l i k el i m i t e dr e s o u r c e so fe m b e d d e dd e v i c e sa n ds l o ws p e e do fm a p d i s p l a y t h i sp a p e rs u g g e s t e dd i v i d et h ew h o l e m a pd a t ai n t ob a c k g r o u n dd a t a ，r o a dd a t aa n d d a t ao fp o i n t so fi n t e r e s t ，a n dc o n s t r u c ti n d e x e sa c c o r d i n gt oi t sh i e r a r c h i c a lb l o c k ， m a p so fd i f f e r e n ts c a l e sm a t c ha l o n gw i t hd i f f e r e n tm a pd a t af i l e s ，b yt h i sw ec a n q u i c k l yl o c a t et h ed a t an e e d e d a tt h es a m et i m e ，d i v i d e dt h eg e o g r a p h i c a le l e m e n t s i n t od i f f e r e n tl e v e l s ，o n l yd i s p l a y e dt h ec o r r e s p o n d i n gc l a s se l e m e n t si n l i g h to ft h e c u r r e n ts c a l e ，t h i sr e d u c e dd a t ar e d u n d a n c y , s p e e d e du pt h es p e e do ft h em a p d i s p l a y , e n h a n c e du s e re x p e r i e n c e r o u t ep l a ni st h ec o r ei s s u eo fa n t o m o b i l en a v i g a t i o n i na c t u a l n a v i g a t i o n t r a f f i cr e s t r i c t i o n so ft u r n sa n dt h ed e l a y sa tt h ei n t e r s e c t i o n sw i l lm a k et h er e s u i to f r o u t ep l a ni n a c c u r a t eo re v e nw r o n g t h i sp a p e re x p r e s s e dt h et r a f f i cr e d i r e c t i o n r e s t r i c t i o n sb ye s t a b l i s h i n gt h et a b l eo fr e d i r e c t i o nr e s t r i c t i o n sw i t ht h ed u a l g r a p h ， c o u l dm a t c ht h ea c t u a lr o u t ep l a nb e t t e r i nv i e wo ft h es l o ws p e e do fn a v i g a t i o n l l i n s t r u m e n t s ，a d o p t e db i - d i r e c t i o n a lh e u r i s t i cs e a r c ha l g o r i t h mw i t ht h ec o m b i n a t i o no f l a y e r e ds t r a t e g y , s e a r c hf r o mt h es t a r ta n dt h ee n da tt h es a m et i m er e s p e c t i v e l y , a n d i m p r o v e dt h es t r u c t u r eo faa l g o r i t h ma n dt h em e t h o dt oe x p a n dn o d e t h er e s u l t so f a c t u a lr u n ss h o w e dt h a tu s i n gt h i s a l g o r i t h m ，c o u l dg r e a t l yr e d u c et h en u m b e ro f s e c t i o n si n v o l v e di nt h ep a t hc a l c u l a t i o n ，s a v es t o r a g es p a c ea n dr a i s et h ee f f i c i e n c y o fr o u t ep l a n f i n a l l y , t h i sp a p e ru s e dc e r t a i np a r to fw u h a nu r b a nr o a dn e t w o r kd a t aa st h e s t u d yo b j e c ta n dm a k e de m p i r i c a lr e s e a r c ha n dt e s t i n gf o rm a j o rw o r k t h e o r e t i c a l a n a l y s i sa n dt h ea c t u a lo p e r a t i n gr e s u l t ss h o w e dt h a tt h em a j o rw o r kt h i sp a p e rh a d d o n eo v e r c o m e dt h ei n s u f f i c i e n c yd u r i n gc u r r e n td e v e l o p m e n tp r o c e s so fn a v i g a t i o n e n g i n e ，t h u sg r e a t l ye n h a n c e dt h es p e e do fm a pd i s p l a y , a n dp r o v i d e de f f e c t i v er o u t e p l a nu n d e r t h ec i r c u m s t a n c e so ft r a f f i cr e d i r e c t i o nr e s t r i c t i o n s k e yw o r d s ：a u t o m o b i l en a v i g a t i o n ，n a v i g a t i o ne n g i n e ，m a pd i s p l a y , r o u t ep l a n ， p o i n to fi n t e r e s t i i i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书雨使 用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 研究生( 签孙翻堡日期 关于论文使用授权的说明 本人完仝了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部内容，可以采用影 印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 导师( 签名) ： 武汉理t 火学硕士学位论文 1 1 选题背景与意义 第1 章绪论 汽车数量快速增加和道路建设相对滞后，使道路堵塞、交通事故、环境污 染、能源浪费等现象在世界范围内变得越来越严重。仅美国主要城市每年由于 交通拥挤而造成的浪费就已超过4 7 5 亿美元，每年因交通拥挤浪费多达1 4 3 5 亿 升燃料和2 7 亿工作小时，而且这些数字每年以5 1 0 的速度递增。在日本， 交通拥挤程度也日趋严重，东京每年因交通拥挤造成的时间损失折合约1 2 3 0 0 0 亿日元。因此，汽车导航系统的出现，对保障交通疏畅、改善道路安全、减少 交通拥挤和空气污染对生态环境造成的恶劣影响有重大意义1 1 ，2 j 。 汽车导航系统是将全球定位系统( g p s ) 、地理信息系统( g i s ) 和计算机技术结 合在一起的一种智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，i t s ) 。系统集 g p s 定位技术、g i s 地理信息显示技术和计算机技术为一体，系统通过车载导航 设备接收g p s 数据，在电子地图上显示行驶中的车辆位置和到达目的地的方向 与距离等，可在路网范围内定向选择最佳行驶路线，提前为司机提供道路信息( 道 路转弯、交通事故易发区等提示) ，降低交通事故发生率1 3 4 i 。 2 0 0 8 北京奥运会的临近，对汽车导航市场是一个绝佳的发展机遇。据预测， 围绕奥运会的物流市场，将有1 0 0 万辆汽车需要安装导航和安全监测系统，奥 运会释放出的巨大商机，将有力地刺激中国内地汽车导航市场1 5 j 。 我国道路建设日益完善，道路网络日趋复杂，使得车主对汽车导航的需求 日益增大。随着自驾游爱好者日趋增多，能让出行变得更轻松，使寻找目的地 变得更加简单快速的导航产品，正成为越来越多车主不可或缺的选择。国内很 多做中长途运输的载货车对于汽车导航也有明确需求，据悉，全国物流业的运 输车辆将会陆续安装g p s 导航及安全系统。公安部门、急救行业和公交行业等 特殊行业对于汽车导航的需求也是与同剧增i 引。 综上所述，中国汽车市场的不断增长，加快了对汽车导航的需求。而作为 汽车导航系统的核心，导航引擎的研究与实现关系到整个导航产品的实用性， 越来越多的企业和厂商增加了对引擎开发的投入。 武汉理工人学硕士学位论文 1 2 国内外发展状况 在国外，汽车导航系统发展得相当成熟，已成为大众的生活辅助工具乃至 必需品l 引。汽车导航作为i t s 的重要应用之一，西方发达国家对其研究较早，技 术也较先进。特别是日本，自主式导航终端市场化程度相当高，并且建立了以 动态路径诱导系统为核心的u t m s ( 通用交通管理系统) 。汽车导航产业在日本已 经是一个成熟的产业，提供的功能越来越强大，智能化程度也越来越来高。一 些豪华轿车上，导航系统已成为标准而非选装设备。例如，丰田公司的w i n d o m 、 日产公司的c i n a 、本田公司的l e g e n d 等。其中，诱导系统能用语音提示驾驶者 在何处拐弯；声控系统输入全国范围的餐馆名称和地址，系统会为驾驶者规划 到目的地的最佳行车路线，并在地图上显示出束并给出动态道路情况。驾驶者 还可利用放大或缩小功能，将地图拉近或拉远，从不同程度查看目前所在地的 信息吲。 美国福特公司的g p s 系统只有汽车收音机大小，为驾驶者指示方向并进行 语音引导，但不显示地图，通过全球定位卫星的信号来确定车辆位置。德国最 大的出租车公司一西克斯特公司，1 9 9 7 年采购8 0 0 0 辆装有导航系统的奔驰车， 在德国八大机场提供服务。只要驾驶员把乘客要去的地方输入车上的电脑后， 即可算出最短路线，然后在屏幕上用图像和声音引导驾驶员驶向目的地【8 j 。 我国汽车导航系统多以自主式导航为主，市场化程度低，技术与发达国家 也有不小差距【9 1 。中国于9 0 年代中后期开始汽车导航系统的研究，但一直没有 成熟的产品上市。近年来，越来越多的国内厂商意识到汽车导航在我国有着巨 大市场。国内不少厂商已推出车载导航产品，但缺乏相关的标准和通用的平台。 中国的汽车使用量预示我国将是汽车导航的消费大国，随着技术的发展和 更多厂商的介入，汽车导航产品必将更加普及，给人们出行带来真正的便利【1 0 j 。 国内汽车导航系统安装比率较低，特别是一些交通系统非常复杂的大城市，交 通拥堵给驾驶者带来了很大麻烦，对实现车辆行驶信息化和智能化的汽车导航 系统的研究已成为人们关注的焦点。 1 3 本文的主要研究内容 汽车导航引擎，应实现地图显示、路径规划、语音引导和兴趣点检索等功 2 武汉理1 二大学硕士学位论文 能，导航引擎的优劣直接决定整个导航产品性能的好坏。 汽车导航系统是一个复杂的嵌入式系统，不同导航系统不仅功能和用户界 面不同，而且使用的硬件设备、操作系统、地图格式以及路径规划算法等也往 往不同，这进一步增加了引擎的开发难度。针对引擎技术研究与实现过程中存 在的地图数据读取效率低、地图显示及路径规划速度慢等问题，本文所做的主 要工作如下： 1 考虑二次平台开发的局限性，导航引擎核心部分采用独立开发模式，增 强了设计的自主性和灵活性； 2 总结现有导航框架和引擎结构的不足，设计出功能强大、结构清晰的导 航框架方案和引擎结构； 3 建立了基于层次网格索引的路网数据模型，基于引擎构架设计出高效的 电子地图文件格式，有效地提高了对地图数据的读取速度； 4 选取已有的规划算法，进行融合和部分改进，将理论运用到实际系统开 发中，能有效地提高路径规划的速度和准确性； 5 给出了一种p 0 1 分类方法，实现了相应的检索机制，提高了p o i 检索的 速度和准确性。 论文组织框架如下： 图1 1 论文组织框架 3 武汉理工人学硕+ 学位论文 第2 章汽车导航系统框架与引擎结构 2 1 系统层次结构 汽车导航系统是安装在汽车上为驾驶者提供路线规划和语音引导服务的汽 车电子设备。系统一般采用g p s 与航位推算法( 车速传感器+ 电子陀螺仪) 组合方 式实现定位，通过触摸显示屏或者遥控器进行交互操作，能够实现实时定位、 目的地检索、路线规划、画面和语音引导等功能，帮助驾驶者准确、快捷地到 达目的地【1 。导航系统一般层次如下【1 2 l ： 导航功能模块 地图显示模块g p s 定位模块 嵌入式操作系统( w i n c e 、p o c k e t p c 等) 嵌入式硬件设备 图2 - 1 汽车导航系统层次图 2 2 引擎技术开发的不足之处 汽车导航电子地图规范基本依照导航引擎要求而制定，地图显示不仅是导 航系统的重要模块，也是导航引擎的重要组成部分。导航引擎在地图的读取方 式和性能方面，对整个汽车导航系统的开发有着重大影响【1 3 】。 当前汽车导航引擎开发中的主要不足有： ( 1 ) 汽车导航引擎多基于二次平台开发，具有一定的局限性； ( 2 ) 汽车导航系统结构复杂，现有的导航框架和引擎结构不够合理，相应的 各项功能也需要进一步完善； ( 3 ) 地图显示速度慢、等待时间长，地图格式不能充分发挥引擎读取地图数 据的效率； ( 4 ) 路径规划慢、路径选择有时欠合理，对复杂交通限制信息的考虑不够； ( 5 ) 兴趣点( p o i ) 分类缺乏统一标准，p o i 检索速度慢，精确度不高。 4 武汉理t 大学硕士学位论文 2 3 导航框架及引擎结构设计 2 3 1 系统框架 本节在研究现有汽车导航系统框架不足的基础上，给出新的导航系统框架 方案描述。系统总体层次及模块接口设计如下： 二： 、! ： r 一爿导航数据! ok - 一 ii 和c a c h e 策略i； =j口i f 地图v t m ( v i r t u a lif 其它导航数l l t r a f f i cm a p ) 格式i l 据上的操作l 图2 2 导航系统层次及各模块间的联系 ( 1 ) a p 应用层：主要用来处理上层应用逻辑，如用户点击嵌入式设备屏幕触 发的消息响应、导航界面的生成等； ( 2 ) u l 接口：a p 层和导航引擎之间的中间层，应用层( a p ) 通过u i 层使用引 擎模块提供的a p i ； ( 3 ) 导航引擎：负责地图的渲染和显示、路径规划功能的实现和语音引导等； ( 4 ) 导航数据i ，o 模块：用以读取导航用地图数据； ( 5 ) 导航数据上其它操作：交叉口、兴趣点等信息的检索。 由于导航系统的复杂性及包括模块的繁多性( 图2 3 ) ，要求各模块间的时序 调用关系必须清晰，本文采用基于定时器( t i m e r ) 事件触发机制的并发策略，来处 理导航过程中不同操作的同步或异步问题( 图2 4 ) 。 j 图2 - 3 汽车导航系统整体框架 图2 4 基于t i m e r 的并发机制 6 武汉理丁大学硕士学位论文 2 3 2 引擎结构 汽车导航系统三层框架及导航引擎包括的模块如下图所示： 上层逻辑应用 g p s 模块li 地图显示ii 路径规划i i 兴趣点检索ll 时序控制模块( m a i nt i m e r ) l 导航数据( 路网、兴趣点数据等) 图2 - 5 导航系统三层框架 下图为汽车导航系统的模块时序图，其中应用层用来调用引擎部分的功能， 如路径规划和地图显示等。窗口基类由a p 层负责开发，用来管理用户在显示屏 上由于点击操作而产生的不同窗口资源。 r _ _ _ _ - 。1r 。1 f 应出层( 砼ii 面目基娄i t _ 一初始化一t 一 ；i医西司同匝五回： i 陉毪础赳li 盟盟il 显丕地图i -l 一j l ，jl ，j ：基于当前位置的买时路径规如 !j i 卜叫力。1 1 载拓l 扑数据i 广。一，i 目宁拓土k 捌，搬： l ，jj - m “： ： ：l r 一 r 1 i l 获取下一个需要导航的位置p 产生导鼍指令i 1 ，7 q ： ： ：获取下一个需要导航的位置r 。 i | 一 | i根据导航位置信息调整地图显拳 图2 - 6 汽车导航各模块总体时序关系 7 武汉理工大学硕士学位论文 基于m a i nt i m e r 的引擎功能模块调用流程如下图所示： 图2 7 引擎各模块的执行顺序 具体分析如下： ( 1 ) 导航开始时，初始化g p s 模块并接收连续的卫星信号数据，同时启动 一个线程读取这些数据( 坐标、速度、方向等) ； ( 2 ) 地图匹配模块会对读取的数据进行坐标转换，并进行位置矫正； ( 3 ) 若用户已经选取起始点、经由点或目标点，则可进行路径规划，从而得 到起始点到目标点的最优路径； ( 4 ) 路径引导和语音引导模块可帮助驾驶员一步一步驶向终点，而无须经常 看屏幕，因为会有相应的转弯或直行的语音提示； ( 5 ) 兴趣点和地址查询模块，主要负责用户感兴趣的数据信息的检索； ( 6 ) 视图模块用来进行地图和路径的渲染，并显示到屏幕上。 2 4 系统实现软硬件平台 2 4 1 软件平台 整个项目需要在p c ( p e r s o n a lc o m p u t e r ) 机和p d a ( p e r s o n a ld i g i t a la s s i s t a n t ) 上同步调试，涉及到的平台或开发工具如下： ( 1 ) 操作系统：w i n x p 、w i n c e 及p o c k e tp c 2 0 0 3 ( 2 ) 开发工具：v i s u a lc + + 6 0 、v i s u a ls t u d i o2 0 0 5 n e t 、e m b e d e dv c + + 4 0 ( 3 ) 版本控制系统：c l e a r c a s e s u b v e r s i o n ( s v n ) 8 武汉理t 大学硕士学位论文 2 4 2 硬件平台 表2 - 1 中列出了本文汽车导航系统开发的p d a 硬件组成，从中可以了解整 个导航产品的硬件构架。 表2 1 导航系统p d a 硬件组成 处理器3 1 2 m h zi n t e lb u l v e r d e p x a 2 7 2 屏幕 3 5 英寸彩色液晶显示屏l c d ，l e d 背光显示 显示屏规格 分辨率6 5 kc o l o r s ，q v g a3 2 0x2 4 0 触摸板电阻触摸板 输入方式记录笔屏幕键盘厂手写识别 扬声器 内置扬声器1 ( m a x i m u m1w a t t ) 扩音器 内置单声道扩音器x1 s d m m c支持4 位s d ( s e c u r ed i g i t a l ) 卡输入输出，兼容m m c ( m u l t im e d i ac a r d ) u s bu s b l 1 电源o n o f f 按钮开关 四个方向按键和回车确认键 硬件复位开关 系统重启按钮 电池 其它交流一直流适配器 串口数据线g p s 数据接收天线 附加器件 2 5 本章小结 本章简要介绍了汽车导航系统的组成，总结了现有导航引擎开发中的不足， 提出了新的导航框架解决方案，在此基础上设计出新的引擎结构，减少了引擎 各模块间的耦合度，适合自主独立开发模式，各模块的修改和更新更方便。 上述为整个导航引擎的初步设计，关于引擎核心技术的研究与实现的细节， 将在后续章节详细介绍。 9 武汉理工火学硕士学位论文 第3 章汽车导航路网数据组织与地图显示 3 1 道路数据表达方式 3 1 1 交叉口模型 道路交叉v i 指两条或两条以上道路的相交处，是车辆转向、行人汇集和疏 散的必经之地。正确设计道路交叉1 ：3 ，合理组织、管理交叉1 ：3 是提高道路通行 能力和保障交通安全的重要方面。道路数据的空间组织对空间数据的搜索效率 和现实世界的综合描述都有着重大影响。下面给出几种常见交叉路口模型1 4 】： ( 1 ) 无禁则交叉口 没有任何禁则的交叉口见图3 - 1 ，允许车辆直行、右转、左转和调头。 i i j fl nq 卜 图3 - 1 无禁则交叉路口【1 4 】 ( 2 ) 双线交叉口模型 双线模型中，所有道路均设二条相向的右侧行车线，在交叉路口再加结点 和辅助线表示。有禁则的交叉口，可分为禁直行、禁右、禁左和禁调头中的一 种或几种。对路口任何一条道路禁止( 直行、右转、左转或调头) ，都不会影响其 它道路正常通行。 ：形多 对一一 盗： r 彩 【卜二 釜 一一 一f 弋? ?膨一 。、 r _ 乡“ 2 ) ， 重复第一次划分操作，将剩余满足条件的空间实体放入相应小网格； 武汉理工大学硕士学位论文 依此类推，最后l x l 划分为第n 层。最多划分层数为n = 【l o g km a x ( m 。，n ，) j + 1 。对各层次划分得到的小网格依次编号，所有完全落入 同一小网格的空间实体拥有相同的编号( 即索引号) ，索引号和小网格一一对应。 1 1 第1 层 啊i ： ； 髫 ； i 蔓ji i 第2 层第n 层 图3 8 层次网格空间划分 经过以上划分，零维空间实体落入第一层某个小网格中，而一维、二维等 更复杂的空间实体则需要根据其外包矩形来确定网格层数及索引号。每个空间 实体都唯一属于某个小网格( 越往后划分，网格的长、宽就越大，总能找到一个 完全包含该空间实体的小网格) ，故不存在重复的索引信息，从而节省了索引存 储空间和查询时去除重复空间实体的时间开销，提高了空间查询的效率1 2 4 】。 ( 2 ) 区域查询 利用已建好的层次网格空间索引查询空间实体时，采取的步骤为： 按第1 层到第n 层的顺序，通过计算得到包含于该查询区域内的和与该 区域有交集的所有小网格( 包括划分的不同层次小网格) ； 查询所有这些小网格，对于每一个小网格，得到其空间实体标识号i d ： 若为低层次划分索引项，返回该小网格所指向的空间实体标识号i d ： 若为高层次划分的索引项，检验该空间实体外包矩形m b r ，判断是否与 查询区域有交集，有则得到相应空间实体i d 。可根据层次网格划分法，得到一 个临界划分层次，在这个层次之上划分的所有小网格所指向的空间实体需要检 验其外包矩形m b r 是否与查询区域相交。 划分层次网格时，为提高索引效率应满足以下条件i 矧： 将每一层的每个小网格中的空间实体数目控制在一个理想的水平； 应保证高层小网格中的空间实体数较少； 应尽量使得每一层的每个小网格中空间实体数量均衡。 ( 3 ) 网格单元大小 网格索引是一种多对多关系，即一个网格单元可包含多个空间要素，一个 1 6 武汉理丁大学硕十学位论文 空间要素可跨越多个网格单元。这种多对多关系下，网格大小是影响索引效率 的最主要因素。与空间要素的外包矩形大小相比： 网格单元太大，每个网格单元内会包含很多空间要素。区域查询时初选 网格虽少，但接下来要处理大量网格内的空间要素边界比较，潜在地增加了查 询时间； 网格单元太小，小于空间要素外包矩形的平均大小，会导致空间索引表 产生大量网格单元，很多网格单元都索引出相同的空间要素。当大量的空间要 素外包矩形被网格单元切割时，空间索引表变大，增加了查询网格单元的时间。 若用户经常对图层执行相同的查询，根据以往的经验数据，网格大小为查 寻空间范围的1 5 倍时，效率较高。网格单元大小取空间要素外包矩形平均大小 的3 倍时，能极大地减少每个网格单元包含多个空间要素外包矩形的可能性， 可获得较高的查询效率。本文将采用这样的标准来确定单元网格大小。 3 4 路网( n e t ) 数据结构 3 4 1 路网表达形式 ( 1 ) 路网组成【2 6 】 路网道路一般用线段表示。节点( n o d e ) o - - i 是一条道路的交叉点或端点，表 示道路交叉路口或终点，通常用经纬度表示，线段( l i n k ) 是两节点间的一段道路。 形状点( v e r t e x ) 是点的有序集，它将给定线段( 不包含端点) 的弯曲部分映射到一系 列相邻的直线段( 形状段) 。 5 图3 - 9 路网基本元素和拓扑关系 上图中，1 7 为道路节点，为路段。名称相同、相互连接的若干条路 段称为一条道路，路段形状用形状点( v e r t e x ) 描述。 1 7 武汉理工大学硕士学位论文 ( 2 ) 路网分层 路网中不同道路等级不同( 高速公路等级最高) ，本文采用的路网层次结构： 第一层包括路网所有道路及相关属性信息，属于最底层； 第二层包括小路( 乡道) 、干道( 县道、省道) 、高等级公路( 国道、高速路) 及 相关属性信息； 第三层包括主干道、主要省道、高等级公路及相关属性信息【2 7 1 。 路网分层数据模型( 图3 1 0 以两层为例) ，图a 为未分层原始路网数据模型， 图b 和图c 为分层后的路网数据模型，其中图b 为低层路网数据模型，图c 为高 层路网数据模型。将同时位于低层路网和高层路网的节点同时划分到低层路网 和高层路网中( 节点4 ，5 ，6 ) ，以利于路径规划中进行分层搜索时的高、低层路网 转换【2 8 , 4 0 。 l i卜 4 3 r 2 6 1 i- 。一 一3 1 i1 6 5 4 i ) 6 a b 图3 1 0 路网分层数据模型 ( 3 ) 路网表达及存储结构应满足的要求： 能准确表达路网要素及拓扑关系； 占用存储空间小； 能表达各种特殊结构( 如环岛、立交桥等) ； 便于路径规划计算； 。 能有效表示转向限制等交通信息。 按此要求设计的n o d e 及l i n k 数据结构将在下面两小节中详细描述。 1 8 武汉理工人学硕士学位论文 3 4 2 结点( n o d e ) 数据结构 图3 1 1n o d e 数据结构 具体数据结构设计如下： s t r u c tt n e t s p o i n t w o r dx ； w o r d y ； ) ； s t r u c tt n e t n o d e l n f o w o r d t y p e ：4 ； w o r d f l a g _ a ：1 ； w o r d l i n k c o u n t ：4 ； w o r d f l a g v n o d e ：1 ； w o r d g r i d _ l e v e l ，g l i d _ i d ； ) ； s t r u c tt n e t n o d e r e c t n e t s p o i n t p o s ； t n c t n o d c l n f o i n f o ； w o r d a d j i d x ； d w o r d c l i n k _ i d x ； w o r d v i r _ n o d e _ i d x ； ) ； 结点空间位置 路网结点信息 ，结点类型：交叉口、反向转弯点等 是否存在邻接结点标记 与该结点相连的l i n k 数目 路径规划的虚拟结点( v n o d e ) 标志 结点所在网格层次及i d 结点外包矩形定义 邻接点索引 l i n ki d 索弓 v n o d c 索引 1 9 武汉理工大学硕十学位论文 3 4 3 路段( l i n k ) 数据结构 图3 1 2u 1 1 l 【数据结构 具体数据结构设计如下： s t r u c tb m b r 【 用于路径计算的l i n k 最小外包矩形 b y t em i n x ,m i n y ； b y t em a x x ， m a x y ； ，； s t r u c tt n e t r o t a t e i n f o 正北方向和由起、终点确定l i n k 间的夹角 d w o r d a n g _ s ：8 ，a n g _ e ：8 ； d w o r d s i n 0 ：1 ，s _ i n l ：1 ，s i n 7 ：1 ； d w o r d e i n 0 ：l ，e i n l ：1 ，e i n 7 ：1 ； ) ； s t r u c tt n e t c o n n e c t l n f o 起、终点连接信息描述( 八个比特方向) w o r d s o ：1 ，s l ：1 ，s 7 ：1 ； w o r d e 0 ：1 ，e l ：1 ，e 7 ：1 ； ； s t r u c tt n e t l i n k l n f o l i n k 基本属性 d w o r d f l a g _ c a r ：l ； 导航车辆类型 d w o r d r o a d _ t y p e ：4 ； 道路类型 d w o r dl i n kf a c i l ：3 ； 该l i n k 上设施类型 d w o r d s p e e d ：4 ； 速度设限 ) ； s t r u c tt n e t v t 【允许通行的不同车辆行驶方向 w o r dc a rd i r e c t ：4 ： 武汉理t 大学硕士学位论文 w o r dm o t o r c y c l e d i r e c t ：4 ； w o r d b i c y c l e d i r e c t ：4 ； w o r dt r u c kd i r e c t ：4 ； ) ； s t r u c tt n e t l i n k r e c l i n k 外包矩形区域 w o r ds n o d ci d x ，e n o d ei d x ；起、终点索引 w o r dv e r t e x 形状点数目_ c n t ； w o r d d i s t ； i j i l l 【长度 b m b r m b r ； 最小外包矩形 w o r d g r i d _ l e v e l ，g r i d i d ； 外包矩形所在网格层次及i d d w o r d v e r t e x _ p t r ； 形状点位置指针 w o r d r n a m e _ p t r ； 道路名称信息位置指针 w o r d m r o t _ p t r ； l i n k 与正北方向夹角信息指针 t n e t c o n n e c t l n f o c o n ； t n e t r o t a t e l n f o r o t ； t n e t l i n k l n f o i n f o ； t n e t v t v t ； ； 3 5 基于引擎框架的地图文件格式设计 3 5 1 地图屏幕坐标转换 地图坐标转换是地图数据处理的关键，地图坐标转换涉及地图( m a p ) 坐标 ( 经、纬度) 、屏幕坐标( s c r e e n 虚拟坐标) 之间的转换。 2 1 图3 1 3 m a p s c r e e n 坐标转换 上图中m v i e ws c r e e n 用以封装m a p 到s c r e e n 坐标转换时的相关参数及 中间结果，部分属性见表3 3 。m a p 表示真实地物坐标系统，s c r e e n 则表示 逻辑坐标系统( 即屏幕坐标系统) 。 表3 3m v i e ws c r e e n 类部分属性 字段描述 z f a c t o r 4缩放因子 r o t a n g l e 逆时针汽车与正北方向夹角 r o t s i n ，r o t c o s 汽车角度正、余弦 d r a w m b r m a p 坐标系中需渲染的地图区域 r s i nz f a c tm u l r c o s _ z f a c t m u ls c r - m a p ，屏幕到地图坐标转换时使用 r s i n _ z f a c t _ d i v r c o s _ z f a c td i vm a p s r c ，地图到屏幕坐标转换时使用 b a s e m o d e 地图、屏幕坐标基准点的选取 屏幕、地图信息结构体 s t r u c ts c r r e c t l o n g l o n g s c r e e n 结构 r c ； 屏幕矩形范围( o ，0 ，3 2 0 ，2 4 0 ) c x ，c y ；屏幕宽、高( 3 2 0 x 2 4 0 ) b a s e x ，b a s e y ；屏幕基准点( 1 6 0 x1 2 0 ) 武汉理一f 大学硕士学位论文 i b o u n d ) ； s t r u c tm a p i b o u n d l o n g c l i p m b r ； m b r ； b a s e x ，b a s e y ； ) ； 3 5 2 地图显示文件格式 屏幕剪裁区域( - 1 0 ，一1 0 ，3 3 0 ，2 5 0 ) m a p 结构 整个地图矩形范围 m a p 基准点( 拖动地图时改变) ( 1 ) 作用 主要用于地图背景显示( 文字、线条、区域等) 。包括背景区域背景