地图linux桌面

挥登仁吃岛贤杉邮文档下载免费文档下载http://www.
1mpi.
com/本文档下载自文档下载网,内容可能不完整,您可以点击以下网址继续阅读或下载:http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c基于QTE的嵌入式GPS_GIS车载导航系统设计与实现基于QTE的嵌入式GPS_GIS车载导航系统设计与实现洳专:j、硕士学位论文丫浙江大学硕士毕业论文摘要摘要本文研究和设计的基于QTE的嵌入式GPS/GIS车载导航系统利用全球定位系统实现对车辆的实时自主定位功能,同时与地理信息系统相结合,配合城市电子地图,实时为车辆提供导航信息.
针对市场上车载导航系统价格昂贵的特点,本嵌入式车载导航系统核心硬件采用高性价比的ARM9$3C2410A芯片,设计软件采用开源Linux系统和QT/EmbeddedGUI,并且专门为嵌入式导航系统设计了一种MiniGIS地理信息系统,旨在提供一种廉价、实用的车载导航系统.

论文首先介绍了车载导航的背景,以及目前国内外的发展状况,并对导航系统所采用的软硬件平台进行了分析和选择.
论文的重点内容是基于Linux操作系统和QT/Embedded的导航系统应用软件设计.
从分析整个软件的功能框架入手,根据这个框架,应用软件需要解决三大方面难题,即MiniGIS系统开发、最短路径算法设计以及图形用户界面设计.

对于小型嵌入式GIS系统开发,本文首先介绍了基于GDAL!
OGR的地图数据库访问工具类设计,然后在讨论了矢量电子地图格式和投影坐标变换的基础上,详细地阐述了矢量电子地图的绘制方法,最后设计和实现了MinjGIs系统的缩放、漫游和测距等基本功能;最短路径算法部分,首先重点解决了城市道路网的矢量地图表达、网络拓扑结构的提取和构建等关键问题,然后在分析经典的Dijkstra最短路算法原理及优缺点基础上,提出了一种使用二叉堆优化的启发式搜索算法,最后对它进行了设计和实现,经过实际电子地图和简单网络测试,该算法的速度和效率比Dijkstra最短路径算法都有明显的提高:图形用户界面编程也是非常重要的一部分,本文详细介绍了整个设计过程,从开发环境的建立、编程到用户界面的设计实现.

最后,文章对嵌入式车载导航系统的改进与升级做了展望.
关键字:GPS、GIS,QT,车载导航,最短路径算法,电子地图Inthisthesis,theGPS/GISVehicleNavigationGUImakesSystem(VNS)basedontheQT/EmbeddedmoftheGlobePhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cositionSystem(oPS)forautomaticvehiclepositioning.
ThethecityelectronicsystemcombinedwiththeGeographyInformationSystem(GIS)andmap,c姐providetheVehiclewiththeReal-ThneNavigationinformatiorLToreducetlIeIlighpriceofthcopensourceVNSproduct,acoreprocessor$3C2410AwithhighqualityandlowoperationsystemLinuxprice,mand孤opensouiv:eGUIQT/Embeddedareadoptedinthissystem.
Meanwhile,aminiembeddedGISsystemisdesignedspeciallyfortheembeddedVNSwiththeaimtoprovidealowpriceandhi曲practicalttyVNSproductAfterin臼oducingtheresearchbackgroundandstaPdsquoofVNS,thisthesisputsforwardthewayofchoosingonandanaIIyzmgsoftwareandhardwareplatform船tbeVNS.
which锄phasizestl砖designoftheapplicationsoftwareoftheVNS呻theandLinuxOSmadflameofthethreeQT/EmbeddedGUI.
Andbasingupontheanalysis011thesoftwarefunctionembeddedNS,wedrewtheconclusionthat,tomeettherequirementofthefrslne,theremainproblemstobesolved:thedesignofMiniGlSsystem,thedesignhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cshortestroadalgorithmarerealizationoftheandtheuserGUIdesign.
operatetheForofMiniembeddedGISsystem,thedesignofthetoolClassesusedtoelecCmmieMapdatabasewasintroducedfirstly.
Thenafterdiscussingtheformatofelectronicmapandthecoordinatetransformationofprojection,themethodoutofdrawingtheelectronicmapisdiscussedindetail.
Andfinallythethesiscarriesdistancemeasuring,etc.
Assol,,illgtheexpressionseve糟lfunctionssuchaszoom,drag,andoftheshortestroadalgorithm,afI目for恤designandrealizationandthepick-upandbuildingofthenetworksmlcUneoftheelectronicalgorithm,athe瑚"basingontheanalysisoftheprincipleandcharacteristicoftheclassicDijkaraheuristicpathfindingalgorhinnisbroughtup,andfinallythealgorithmisbinaryheapsandcarried砸inthisthesis.
Aftertc她by0plti|删usingtherealelearonicmapandsimplenenvork,weconcludethattheefficiencyofthisalgorithmisimprovedgreatlycomparedtotheD自ks扫aalgorithm.
11leGUIprogramminghttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cdoeswealsoplayanimportantroleinapplicationsottwaredesign,soexpoundherethewholedesignprocessincludingthefoundationofthedevelopmentenvironmentandtherealizationofthecodewriting.
Attheend,wedrawaconclusionfor01.
1rstudy,anddiscussseveralpotentialmethodstoimproveandupdatetheembeddedvehiclenavigationsystem.

Keywolr'dk:GPS,GIS,QT,VehicleNavigation,ShortestRoadAlgorithm,ElectricMap—n一第一章绪论第一章绪论【摘要】本章主要介绍了车载导航系统研究意义、发展历程以及国内外发展状况.
最后给出了课题的主要研究内容以及论文章节安排.
1.
1引言自上世纪六十年代开始,许多国家就开始了对导航和定位技术的研究.
开始初期,这些研究主要用于军事目的,如GPS导航系统就是冷战时期的产物.
但是随着现代技术的不断发展,定位导航系统开始向小型化、低廉化方向发展,同时也开始由原来的军用逐步转化成民用.
从最初简单的定位设备,到现在车载导航定位系统,导航定位技术已经越来越成熟.
车辆导航定位也由原来简单的航位推算系统、惯性导航系统转化成现在应用广泛的GPS导航系统.
自从t994年由美国国防部发布GPS系统以来,GPS导航技术在民用市场的发展速度远远超出了系统设计者的想象,尤其是近些年,随着微电子技术的迅速发展和GPS的芯片制造成本迅速下降,GPS导航技术的应用己经扩展到各个领域.
随着地理信息系统、信息技术和通信技术的发展,以GPS导航和地图数据匹配技术为基础的汽车导航产品开始进入市场,并高速增长,目前己成为GPS最大的消费市场.
随着俄罗斯的GLONAS系统和欧盟伽利略系统的不断开发和完善,加上中国自己的北斗定位系统开发,导航产品http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c的成本也必将越来越低,市场也将越来越广泛Il】o1.
2国内外研究现状嵌入式车载导航系统是集卫星定位技术(GPs)、她理信息系统(GIS)、嵌入式技术、通信技术等为一体的综合应用系统.
该系统以GPS接收机为地面接收系统,城市电子地图为基础数据库,以实时操作系统、可视化开发语言、GIS软件为开发平台,并通过GPRS或者CDMA无线通信模块来获得实时路况信息,只需司机给出一些简单的指令,就可通过系统的协同工作来显示城市电子地图和车辆所在位置,并且可以实时地规划出一条最佳旅行代价路线12].

车载导航系统一经问世,即显示出强大的生命力和广阔的应用前景,并产生了巨大的社会和经济效益.
由于巨大的市场潜力和不可估量的发展前景,日本几乎所有的汽车生产厂家都参加了这一高科技角逐.
GPS车辆导航系统最早是在日丫浙江大学硕士毕业论文第一章绪论本独树一帜地发展起来的,接着欧洲也开始大规模地出现爆发性的增长,来势比日本启动时还猛,而且北美又紧追其后,很快出现了产业化发展势头.
而更值得人们一提的是出现了一种新产品:车辆信息系统,它实际上把车辆的导航和监控功能合二为一,最简捷的方法是利用PDA、GSM(或CDMA)和GPS相结合,既利用车载电子地图进行自主导航,也能利用无线移动通信系统与控制中心或其它信息服务部门实现双向通信.

导航系统的发展经过了一段比较长的时期,从开始的航位推算系统、惯性导航系统到现代化的GPS导航系统,导航功能已经越来越强大,精度也越来越高.
下面简单介绍一下导航系统发展历程中的各种导航系统.

早期船员们常常通过船只的已知航向和速度,然后利用数学公式来推算出自己船只的当前位置,这种技术称为估计推算法(DeducedReckoning),它的现代定义由Cotter提出,称为航位推算(DeadReckoning,DR),是一种非常原始的自主式车辆定位系统.
该系统定义为从一个已知的坐标位置开始根据运动载体在该点的航向航速和航行时间推算下一时刻的坐标位置的导航过程.
通常来说,航位推算系统是利用罗盘仪、速率仪、里程仪等传感器测量运动车辆的行驶距离、速度和方位,然后通过数学计算来获得当前的位置.
它在运行的http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c短时间内精度较高,并且可以实现车辆的自主导航.
但是它需要车辆原始位置的注入,而惯性器件的漂移误差将随着时间的推移逐步累积,随着推算时间的延长推算准确性就会降低.
因此DR系统不能长时间单独使用【8】.

导航系统发展到中期段出现了惯性导航系统(InertialNavigationSystem,INS),它是一种不依赖任何外界信息,不受天然和人为的干扰,完全依靠自身的惯性敏感元器件测量导航系统参数的系统,是一种完全自主式导航系统.
但是它和航位推算系统一样,在长时间工作以后,会产生不同程度的误差累积,因而需要增加其它的辅助定位才能准确完成任务,并且该系统造价比较高,一般不适用于普通的车辆导航系统.

全球定位系统(GlobalPositionSystem,GPS)是美国从上世纪70年代开始研制,历时23年,耗资近200亿美元的第二代卫星导航系统.
其特点是全天候、高精度,是迄今为止最好的导航定位系统[Sl.
该系统具有在海、陆、空进行全方位实时导航与定位的功能,已经发展成为应用最广泛、最实效的全球导航系统{羽.
GPS导航技术使用非常方便,一般只需要一个GPS接收器就能够在汽车、飞机、丫浙江大学硕士毕业论文第一章绪论轮船中使用上GPS导航系统了.
GPS系统起初是由美国海陆空三军共同研制开发的,因此在军用上导航定位精度非常高,而在民用上却受到了非常大的限制.
自从美国自2000年取消了选择可用性(sA)技术之后,目前民用GPS的精度得到了大大的提高,定位精度已经达到lO左右.
但是GPS同样有其自身的缺陷,由于它是一种无线电卫星导航系统,需要至少观测到四颗卫星才能确定车辆的准确位置,也就是说需要车辆本身有对卫星的直接可观测性,因此当汽车行驶在高楼区、涵洞等地方时可能导致GPS信号的暂时中断,从而暂时的失去导航定位能力.

在GPS车辆导航系统中,电子地图是除了车辆定位导航设备之外的最基本和最重要的组成部分,因为车辆导航系统中的绝大部分的功能,例如车辆的位置信息、最优路径信息以及各种查询功能等,都需要在电子地图上加以显示,因此高质量的电子地图以及操作显示电子地图的GIs软件,就成为车辆导航系统成功与否的关键f3】.
GIS条件下的电子地图数据http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c库为车辆导航系统提供了存放和管理导航信息的一个可视化载体.
GIS在车辆导航系统中的应用研究将会成为智能运输系统的发展方向之一.

目前应用车载导航系统大致有三种方案:GPS/电子地图(GPS/MM)、GPs/航位推算(GPS/DR)、GPs/航位推算/电子地图(GPS/DR/MM).
第一种方案系统结构简单只需要GPS接收机和电子地图就可以构成,因此成本较低,但是系统在GPS信号丢失时无法正常工作,使得系统的可靠性降低.
GPS/DR系统可靠性得到提高,但是车辆无法利用电子地图匹配技术对GPS定位信息和航位推算的定位信息作进一步校正和显示,因此一般不采用这种系统.
GPS/DR偶nd系统,不但具有较高的可靠性,而且在使用相对较低成本的基础上能够获得较高的定位与导航精度,因此它是陆地车辆导航采用的一种较佳方案.

但是由于第一种方案比较简便实用,以及GPS抗干扰性能的提高,目前仍是陆地车辆导航采用的主要方案之一.
本文首先设计处理和操作电子地图的MiniGIS系统,然后再结合GPS定位系统,旨在设计一种低成本、高实用性的车辆导航定位系统.
本系统还能够直接接上CDMA模块,通过无线网络从道路监控中心获得实时的路况信息,形成一个智能化GPS车载导航系统.

丫浙江大学硕士毕业论文1.
3嵌入式导航系统基本理论第一章绪论所谓嵌入式系统(EmbeddedSystems)就是以应用为中心,以计算机技术为基础,软硬件可裁剪,适用于系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统,主要由硬件和软件两大部分组成.
硬件部分包括微处理器、存储器及外设器件和YO端12、图形控制器等;软件部分大致包括操作系统软件(一般要求实时和多任务操作)和应用程序编程软件.
在系统设计的时候,设计人员有时会把这两种软件组合在一起嘲.

目前,嵌入式系统的应用领域非常广泛,已经成为当今时代热门技术之一,它的应用涉及到移动计算平台(PDA)、家庭信息环境(数字电视)、通讯计算平台(媒体手机)、车载计算平台(导航仪)、智能商业设备(POS/ATM机)、电子商务平台(智能卡)和信息家电等,还可广泛应用于与hltemet相联接的一切接入设备.
http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c嵌入式操作系统及其应用软件的共同特点是:1)软件要求固化存储在存储器芯片或单片机本身中,而不是存储于磁盘等载体中,近年随着FLASH技术广泛应用和SD卡的普及,嵌入式系统也越来越多的与这些存储设备关联在一起;2)软件代码要求高质量、高可靠性来保证嵌入式设备的正常运转;3)系统软件的高实时性和多任务操作要求.
信息技术日新月异的发展,使嵌入式导航系统研制和应用需要的各种设备和相关技术日渐成熟和完善.
各种掌上电脑产品的推出,实时嵌入式操作RTOS的频频出现,微型嵌入式技术、卫星定位技术、无线通信、卫星通信技术的日趋成熟并进入实用化阶段,使嵌入式GIS的设计与实用化所要求的关键技术已经得到了解决【71.

本文所设计的基于QTE的嵌入式GPS/GIS车载导航系统是将GPS技术、GIS技术、矢量电子地图技术、无线通信技术与嵌入式操作系统结合起来.
在该导航系统中利用了GPS的全天候覆盖连续性、定位高精度性、强抗干扰能力、高保密性等优点,加上由矢量电子地图提供的比较精确的城市交通信息,最终结合Linux操作系统和CDMA无线通信技术等,使得本文所设计出的导航系统具有成本低、体积小、可靠性高等特点,从而充分满足了车载导航环境的要求.
1.
3.
1GPS技术GPS,即全球定位系统(GlobalPositi011System),是美国开发研制的迄今为止最好的应用最广泛的第二代卫星导航系统.
GPS系统实际需要三部分组成,即空间部分、地面监控部分和用户设备部分IS].
空间部分是指GPS工作卫星星座,由24颗卫星组成,其中21颗工作卫星,3颗备用卫星,均匀分布在6个轨道上,并且进行特定的时空配置,最终保证地球上任何地点、任何时刻均能至少观测到4颗卫星,从而满足地面用户实时全天候的精密导航和定位服务.
空间部分主要功能是接收地面指令、给用户发送导航电文和提供精密的时间标准.
地面监控部分由1个主控站、3个注入站、5个监控站组成,主要任务是:给GPS系统提供时间标准、调整轨道卫星偏差、监控系统运行情况并进行调整.
用户设备部分就是GPS接收机,主要功能是接收GPS卫星发射导航电文,经过精密的数据处理和加工实现准确的导航和定位.

自从200http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c0年美国取消了选择可用性(SA)技术之后,目前民用GPS的精度得到了大大的提高,定位精度已经达到10米左右.
近年美国为了开发GPS的商业潜力,又对GPS系统进行了一系列的更新,如:增强民用信号、采用更加稳定的频段和提高抗干扰能力等.
使得GPS的民用市场又得到了大大的拓广,虽然受到来自如欧盟的伽利略系统、俄罗斯的GLONAS系统的冲击,但其垄断地位一时还是难以打破.

1.
3.
2GIS棚-谜GIS,即地理信息系统(GeographicInfo删onSystem),是一种基于计算机的可以对地理信息进行成图和分析的工具.
GIS技术把地图这种独特的视觉化效果、地理分析功能和一般的数据库操作(例如查询和统计分析等)集成在一起.
本文针对电子地图在嵌入式设备中的应用,设计了一种小型的基于Q饥II妇习ded和GDAL/OGR的地理信息系统,本文称为MiniGis系统,它主要实现电子地图的数据读取、描绘、检索、漫游、放大和缩小等基本功能.

地理信息系统外观上,表现为计算机软件系统:其内涵却是由计算机程序和地理数据组织而成的地理空间信息模型,一个逻辑上缩小的、高度信息化的地理系统,从视觉上、计量上和逻辑上对地理信息系统的功能进行模拟,信息的流动及其结果完全由计算机程序的运行和数据的仿真来实现.

1.
3.
3电子地图技术电子地图是将传统的字纸地图进行数字化,可以方便的实现地图的检索、管理、放大缩小等一系列功能,为导航提供了最有力的支持.
电子地图按照数据存储方式,可以分为栅格电子地图、矢量电子地图等.
矢量电子地图是以矢量图形式存储的电子地图,矢量图也叫面向对象绘图,是用数学方式描述的曲线及曲线围成的色块制作的图形,在计算机内部表示成一系列的数值而不是像素点,这些值决定了图形如何在屏幕上显示.
因此矢量电子地图最大的优势在于可以自由地改变对象的位置、形状、大小和颜色嗍.
同时,由于这种保存图形信息的办法与分辨率无关,因此无论放大或缩小多少,都具有相同的平滑边缘、视觉细节和清晰度.
矢量电子地图有非常多的格式,如Maplnfo的TAB、MIF/MID格式、ESRIShapefile的shp/shx/dbf格式、Oraclhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228ceSpatial格式等.
本系统主要使用MapInfo的TAB格式电子地图.

1.
4本文研究主要内容及章节安排基于QTE的嵌入式GPS/GIS车载导航系统旨在满足车载导航定位基本要求的前提下,结合当前的技术水平和研究现状,开发出一种成本较低、实用性强的嵌入式导航系统.
GPS能迅速、准确、全天候地为车辆提供定位导航信息,而电子地图则提供比较精确的城市交通信息,将二者结合起来并采用基于QTE设计的MiniGIS系统将电子地图信息准确呈现给用户,再加上最短路径寻优算法与无线CDMA通信模块,这样系统就能够实时有效地为车辆提供智能化导航定位功能.

开发这样一个实用的导航系统需要大量的工作,首先需要设计一个硬件平台,然后选择合适的操作系统以及GUI开发工具,最后完成导航系统所需的各种算法和软件工作.
本文主要研究内容包括:*MiniOlS实现:主要设计一个Linux下基于QT/Embedded的嵌入式GIS系统.
通过开放的GDAL/OGR库来读取电子地图数据,然后经过一定的封装和处理来提供各种地图浏览和地图信息查询功能.
实现了地图的漫游、放大和缩小、多层图的任意调用、地图信息检索等多种功能,为电子地图在嵌入式Linux中的应用提供了有力的支持.

路径分析功能:由用户通过基于QT的用户界面交互程序,拖动鼠标或指定地名的方法在窗口中指定起点和终点,由计算机软件按照要求自动计算最短行驶路线,并在地图窗口中予以显示.
定航定位功能:利用GPS接收器和电子地图数据实时显示车辆的位置,并丫浙江大学硕士毕业论文能实时跟踪目标移动,保证目标显示在地图的中央.
第一章绪论地图检索与地图匹配:地图检索主要是由用户通过界面交互程序输入感兴趣的关键字,系统就能搜索到相关的地理信息,并由用户进行选择显示.
地图匹配算法主要用来修正GPS接收器位置信息的偏差,从电子地图中选''择最佳道路来与当前位置进行匹配,使得导航定位更加准确.
距离测算与轨迹回放:轨迹回放能够保存车辆运行轨迹,并在用户需要的时候进行回放.
距离测算能够完成任意两http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c点之间的距离计算.
本文各章节主要内容安排如下:第一章主要介绍了车载导航系统的国内外研究现状、基本理论以及本文主要研究内容与章节安排.
第二章简要介绍了基于QTE的嵌入式GPS/GIS车载导航系统软硬件平台,概括的讲述了嵌入式导航系统的应用软件框架.
第三章主要介绍了导航系统的核心基础部分——MiIliGIS系统,并详细的阐述了MiniGIS系统的设计思路和实现方法.
第四章介绍嵌入式车载导航系统图形化用户交互界面的设计与实现.
第五章主要讲述了车载导航系统中的最短路径算法的设计,首先概述了经典的nijkstra算法原理及优缺点,然后设计和实现了基于二又堆优化的A+最短路搜索算法.
第六章主要对课题今后的深入研究方向作了展望,并总结了本文的工作.

丫浙江大学硕士毕业论文第二章嵌入式导航系统简介第二章嵌入式导航系统简介【摘要】本章首先简要介绍了嵌入式导航系统运行时的拓扑结构.
然后分别介绍了导航系统硬件平台、软件平台、以及导航系统应用软件实现架构.
2.
1导航系统简介.
嵌入式车载导航系统采用GPS定位系统来获得车辆的经纬坐标信息,并辅助以电子地图信息来确定车辆的准确道路位置信息.
车载导航系统运行时,首先通过GPS接收机收到导航电文确定经纬坐标,然后通过MiniGIS软件读取电子地图数据,调用地图匹配算法,在地图中搜索出准确的道路与车辆位置匹配,并将此位置在地图中显示给用户.
用户可以通过导航系统用户交互界面输入相关的命令,完成诸如地图信息检索、最优路径分析、距离测算和车辆运行轨迹回放等功能.
导航系统还可以根据用户命令,使用CDMA模块连接无线网络获得最新的路况信息,对最优路径进行调整,及时避开拥挤路段.
同时车辆监控中心也能通过无线网络获得车辆的各种信息,对出行车辆进行监控【4】.
车载导航系统运行时,系统拓扑结构如图2.
1所示.

'器器…器豁车载导航系统车辆监控中心图2—1导航系统拓扑图鉴于嵌入式系统专用性强、可靠性高、软硬件可裁剪、成本低等特点,车载导航系统http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c采用了嵌入式设计方法.
主要由三部分构成:硬件平台部分、软件平台部分和导航应用软件部分.
硬件平台部分主要包括处理器、GPS接收机以及各种1丫浙江大学硕士毕业论文第二章嵌入式导航系统简介外围设备.
软件平台部分主要包括嵌入式实时操作系统、用户图形户界面软件等.
导航应用软件部分是实现导航系统功能的所有软件以及算法.
下面将分节来简要介绍各个部分.

2.
2导航系统硬件平台导航系统在设计时采用了基于舢tM(Adv锄cedRISCMachine)的嵌入式硬件平台,由于系统对核心处理器的性能要求较高,因此本系统采用了高性价比的ARM9芯片$3C2410A.
近些年来,随着计算机技术、微电子技术的快速发展,在8/16位微控制器成熟技术的基础上,为适应一些对性能、存储要求更高的场合,一些大公司开发了32位微处理器.
而ARM微处理器正是其中的佼佼者,由于在32位嵌入式RISC领域内有着广泛的影响,它已成为32位微处理器领域中的首选.
ARM系列微处理器具有较高的性能,主要表现在其体系结构是基于RISC流水线架构,它的指令系统和相关译码机制比那些采用复杂指令系统的计算机(CISC)简单得多【llJ.
这种简化主要有三个优点:提高指令的吞吐率;具有有效的实时中断响应;具有体积小、性价比高的处理器宏单元.
ARM9系列相对于ARM7系列性能又更佳,它提供:5级整数流水线,1.
1MIPS/MHz的哈佛结构,支持32位ARM指令集和16位Thumb指令集,支持32位的高速AMBA总线接口,全性能的MMU,支持W'mdows操作系统'埘.
除此核心处理器外,导航系统硬件平台还包括:GPS接收机、带触摸屏的LCD显示器、存储设备和通信模块等.
系统的硬件架构大致如下图2.
2所示.
CE、Linux、PalmOS等多种主流嵌入式图2-2导航系统硬件平台$3C2410A是韩国SamSung公司的一款基于ARM920T内核的16/32位RISC丫浙江大学硕士毕业论文第二章嵌入式导航系统简介嵌入式微处理器,主要面向手持式设备以及高性价比、低功耗的应用.
$3C2410A集成了丰富的内部控制器和外部接口,为导航系统硬件http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c平台设计带来了极大的便利.
$3C2410A集成了一个LCD控制器(支持STN和TFT带有触摸屏的液晶显示屏)、SDRAM控制器、3个通道的UABT、4个通道的DMA、4个具有PWM功能的计时器和一个内部时钟.
S3C2410A还有很多大量的外部接口,例如触摸屏接口、IIC总线接口、两个USB主机接口、一个USB设备接口、两个SPI接口、SD卡接口等,几乎具备了一台PC机所有的外围接口【9J.

本文中采用的是夏普LQl0D321n可显示屏,在640X480分辨率下可提供16位彩色显示.
$3C2410A通过本身集成的LCD控制器连接LQl0D321显示屏.
对于GPS接收机采用了市场上高精度接收器,通信模块采用了AnyData公司生产的DTU--800CDMA无线通信模块,S3C2410A通过UART接口实现与它们的连接.
同时系统扩展了64M字节的SDRAM内存、2M字节的NORFlash和64M字节的NANDFlash存储,并且系统硬件设计时配备一个标准SD卡接口.
这样硬件平台就充分满足了嵌入式操作系统和车载导航系统软件要求,而且电子地图数据库还能通过SD卡进行大规模的更新或者替换.

2.
3导航系统软件平台既然导航系统采用嵌入式设计,必然需要嵌入式实时操作系统(RTOS)的支持.
同时导航系统具有丰富的图形界面和用户交互界面,因此需要在嵌入式操作系统上移植一个图形界面编写软件(即GUI软件).
这两个同时构成了嵌入式导航系统的应用软件平台.
下面来分别介绍一下RTOS和GUI的选择和使用.
2.
3.
1嵌入式实时操作系统选择随着微处理器的产生,价格低廉、结构小巧的CPU和外设连接提供了稳定可靠的硬件架构.
从20世纪80年代开始,市场上陆续出现了一些针对嵌入式的实时操作系统,比较著名的有uC/OS、Vxwork、PalmOS、Linux和WindowsCE等.
目前嵌入式实时操作系统正处于高速发展阶段,未来几年,这种发展和竞争将愈演愈烈.
嵌入式操作系统、捆绑工具以及相关服务的市场也将越来越大,其中以亚太地区的增长最为迅猛.
这些操作系统都有各自的特点和应用领域,下面简要介绍之.
1)uc/oS:它是一个典型的时实操作系统.
目前流行的是第http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c2个版本,即uC/OS第二章嵌入式导航系统简介II.
它的特点是:源代码公开,代码结构清晰、明了,注释详细,组织有条理,可移植性好,可裁减,可固化.
内核属于抢占式,最多可以管理60个任务.
但是它不支持时间片轮转,不支持优先级继承,不支持大型的MMU,同时由于它可以直接操作底层设备,驱动简单,因此它比较适合于小型的嵌入式应用.

2)Vxworl(:它是WindRiver公司专门为实时嵌入式系统设计开发的操作系统软件,为程序员提供了高效的实时任务调度、中断管理、实时的系统资源以及实时的任务间通信.
系统的可移植性好,并且可以得到该公司的技术支持.
应用程序员可以将尽可能多的精力放在应用程序本身,而不必再去关心系统资源的管理.
这是一个非常优秀的实时操作系统,但它是一个纯粹的商业化产品,面向的也是高端用户,缺点是价格太昂贵.
因此它基本上是大公司开发较大型嵌入式设备的一种选择.

3)PalmOS:它是一种32位的嵌入式操作系统,多用于掌上电脑.
它运行在一个抢占式的多任务内核之上,同~时刻用户界面仅仅允许一个应用程序被打开,与同步HotSync结合可以使掌上电脑与Pc上的信息实现同步,把台式机的功能扩展到手掌上.
与其他嵌入式操作系统相比,Palm具有更大的灵活性和移动性,是一款非常流行的掌上电脑操作系统.

4)WinCE:它是W'mdows家族中最新的成员,专门设计给掌上型电脑所使用的电脑环境.
这样的作业系统可使便携式技术与现有的W'mdows桌面技术完美的整合起来.
它是微软公司为了抢占嵌入式操作系统市场,推出的一款专门应用在嵌入式设备上的小型Windows操作系统.
它从整体上为有限资源的平台设计了多线程、完整优先权、多任务的操作系统.
W'mdowsCE采用模块化设计,并允许它对从掌上电脑到专用的工控电子设备进行定制.
同样,它是市场出现的商业化产品,价格比较昂贵,对于小型用户只能另投它主了.

5)Linux:在所有的嵌入式操作系统中,Linux发展最快、应用最广泛.
它是一个和Unix相似、完全内存保护、多任务多线程的操作系统翻.
嵌入式Linux操作系统的特点如下:://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c开放源码,丰富的软件资源.
系统价格低廉,结构灵活,适用面广.
精简的内核,性能高、稳定性好,真正的多任务操作系统.
同时支持多种体系结构,如X86、ARM等.
提供了完善的嵌入式图形化用户界面,如QT忸mbeded,MiniGUI.
提供强大的语言编译器gcc、g十+等和完整的开发工具及SDK.
支持大量的周边硬件设备.
完善的MMU内存管理机制,安全高效.

嵌入式Linux操作系统以功能强大、价格低廉又易于移植而得到了众多商家和软件开发人员的青睐,纷纷转向了嵌入式Linux方面的开发和研究.
Linux现已成为嵌入式操作系统的理想选择.
免费的Linux无疑是Linux系统发展如此之快的主要原因之一,在激烈的市场竞争中,只拥有先进的技术远远不够,如何减少产品的投入也是需要重点考虑的问题,特别是对于经济实力不强的小公司来说[121.

由上文的介绍可知,嵌入式实时操作系统种类繁多,有些是免费开源的,有些功能齐全但价格昂贵.
本文综合考虑了系统开发成本、可移植性、可利用资源以及系统可定制能力等众多因素之后,决定采用嵌入式Linux操作系统.
因此嵌入式车载导航系统在核心处理器$3C2410A上移植了版本为2.
4.
18的Linux操作系统.

2.
3.
2图形化用户界面选择图形用户接I=I(GraphicalUserInterface,ouD是计算机与使用者之间的交互接口.
通过它使用者可以通过菜单、工具条、鼠标等方便地进行操作,是计算机系统的重要组成部分.
嵌入式系统的代表GUI有QT/Embedded、MiniGUI、以及MicroWindows.
这些GUI系统在体系结构、功能特性等方面存在着很大的差别.

1)MicroWindows:是一个开放源码的项目,目前由美国CenturySoftware公司主持开发.
MicroWindows是一个基于典型客户/服务器体系结构的GUI系统,基本分为三层.
最底层是面向图形输出和键盘、鼠标或触摸屏的驱动程序;中间层提供底层硬件的抽象接口,并进行窗口管理;最高层分别提供兼容于XWindow和Windohttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cwsCE的API.
它的主要特色在于提供了客户机/服务器体系结构和相对完善的图形功能.
但MieroWindows的图形引擎存在一些问题:无任何硬件加速能力;图形引擎中存在许多低效算法,同时未经任何优化;代码质量较差等.
该项目的开发一度非常活跃,但自QT伍mbcdded发布以来,该项目变得不太活跃,并长时间停留在O.
89Pre7版本.

1甲浙江大学硕士毕业论文第二章嵌入式导航系统简介2)MiniGUI:是由北京飞漫软件公司主持,由许多自由软件开发人员支持的一个自由软件项目(遵循LGPL条款发布),其目标是为基于Linux的实时嵌入式系统提供一个轻量级的图形用户界面支持系统.
它是建立在比较成熟的图形引擎之上,其特点是小巧精致.
它尽量保持与Win32的兼容,这样在WinCE应用的场合,也可以使用MiIliGLⅡ.
MiIliGUI的灵活性非常好,可以应用在包括手持设备、机顶盒、游戏终端等等在内的各种高端或者低端的嵌入式系统当中.
但相比较QTE而言,它的功能模块太少.

3)QT/Embedded:是一个专门为嵌入式系统设计图形用户界面的工具包,提供了丰富的窗口小部件,并且还支持窗口部件的定制,因此可以为用户提供漂亮的图形界面,为带有轻量级窗口系统的嵌入式设备提供了标准的API.
Linux桌面系统的KDE就是基于Qt库开发的.
还有许多基于Qt的XW'mdow程序可以非常方便地移植到QT/Embedded版本上.
Qt可以帮助开发者为满足嵌入式系统小而快捷的要求开发稳定的应用程序.

作为嵌入式平台的QT版本,Q1yEmbedded具有一些其它的特点:节省内存,大小可定制.
QT炬mbedded的设计特点保证了它可以高效的利用内存资源.
同时程序员可以根据开发环境的需要和内存资源的大小,对Q陇mbedded库进行裁剪.
支持多种CPU体系结构.
QT/Embedded可以方便地移植到Linux系统支持的多种CPU体系结构平台上.
包括当前主流的嵌入式应用,例如X86、A蒯Ⅵ、M口S以及PowerPC等多种CPU.

优异的屏幕与色彩支持,功能完善的仿真环境.
Q1yEmbeddcd可以支持多种屏幕大http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c小、分辨率和色深.
实际上,QT/Embeddcd是硬件独立的,可以在Linux支持的处理器及图形卡的任意组合上正常工作.
在使用QT/Embcdded开发嵌入式应用时,并不需要将所有的应用程序都下载到目标机才能进行仿真,而可以在宿主机上进行基本的调试.

在综合分析和比较以上各种GUI的特点之后,本文最终采用了QT/Embedded图形化用户赛面软件作为嵌入式车载导航系统的GUI.
在选择了嵌入式车载导航系统的操作系统与图形化用户界面之后,导航系统应用功能的实现主要是基于Linux和QTE上的应用程序和算法开发.
应用程序与操作系统、QTE的基本关系如图2.
3所示.

丫浙江大学硕士毕业论文QT/Embedded的应用程序QWSServer图形事件服务QT/EmbeddedLinux系统底层驱动程序第二章嵌入式导航系统简介图2-3应用程序与操作系统、QT的关系2.
4导航系统应用软件架构嵌入式车载导航系统主要功能由系统应用软件实现,主要包括GPS定位数据获得、电子地图数据读取、电子地图基本操作实现、地图检索,路径寻优和轨迹回放、以及用户交互界面等功能的实现.
导航系统应用层软件的大致结构如图2-4所示.

用户输入信息图2-4应用层软件结构系统启动后呈现给用户整个地图,然后用户可以执行不同的操作来实现不同的功能,如用户可以漫游、放大缩小地图,也可以输入起始地点和目的地来查询最短路径.
系统通过集成的MiBiGIS系统来读取和绘制电子地图.

路径寻优主要通过前面介绍的A算法来实现,同时优化数据结构,使路径寻优计算的时间和内存消耗达到一个较佳值.
MiniGIs系统完成全部电子地图的基本操作,主要包括地图数据的读写、地图绘制、漫游、放大和缩小等基本功能.
地图数据的读取通过GDAL/OGR库来实现,并且每次读取时根据显示区域的大小对地图数据进行过虑,从而避免一次操作的一14—1r浙江大学硕士毕业论文第二章嵌入式导航系统简介数据过http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c多.
但是为了防止MiniGIS系统响应过慢,即防止拖动时系统频繁重新读取地图数据,系统采用了一种折中的办法,即读取几倍于视窗大小的地图数据,这样导航系统漫游时的响应速度将得到大大的加快.

地图的描绘是由MilliGIS系统通过使用GUI(QT/Embe,dded)I具来实现.
在分层读取到地图数据后,配上对应的颜色,分层绘制到设备上去.
地图的搜索即根据输入关键字对地图数据进行匹配,将搜索结果显示给用户.
MiniGIS系统采用了内存绘图的方法,每次都读取了几倍于视窗大小的地图数据,那么用户漫游时只要不达到边界,就可以直接将内存数据绘出,如超出范围则需要重新读取数据.
放大和缩小通过响应鼠标获取比例尺、然后设定中心,读取相应的地图数据后显示给用户.
下面各章节将分别介绍导航系统各功能的具体实现.

丫浙江大学硕士毕业论文第兰章基于QTE的MiniGIS系统实现第三章基于QTE的MiniGIS系统实现【摘要】本章主要介绍了基于QTE的嵌入式MiniGIS系统功能设计及其实现,主要包括Mapinfo矢量电子地图的读写、地图的绘制、地图的漫游、放大缩小、地图信息检索等基本功能的实现.
导航系统的一切其它服务均通过它来访问电子地图数据库.

3.
1传统GIS平台及其优缺点随着计算机技术和信息技术的发展,GIS系统的应用也越来越广泛,发展也越来越快.
在GIS系统的发展过程中出现了大量的专业GIS开发工具,这些专业工具各有特点,也各有适应领域.
从GIS系统的组成结构来看,大致可以分为:大型集成GIS系统、组件式GIS系统和w曲GIS系统.

大型集成GIS系统一般功能非常强大,集成了各种功能模块软件包,如Mapinfo公司推出的MapinfoProfessional、ESRI公司推出的ARC/Info、Genasys公司推出的GenaMap等都是大型的GIS开发工具.
大型集成GIs系统优点就是它的各项功能已经形成一个完整独立的系统,使用方便,功能完善,但缺点是系统复杂、庞大、成本较高,并且难于与其它应用系统进行集成【13l.

组件式GIS系统代表了GIS系统的一个发展方向,它的基本http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c思想是把GIS的各大功能模块划分为几个控件,每个控件完成不同的功能.
各个GIS控件之问,以及GIS控件与其它非GIS控件之间,可以方便地通过可视化的软件开发工具自由、灵活的集成起来,形成最终的GIS应用系统.
控件如同一堆各式各样的积木,它们分别实现不同的功能(包括G/S和非GIS功能),根据需要把实现各种功能的"积木"搭建起来,就构成应用系统.
由Microsoft公司推出的COM(ComponentObjectModel)就是一种组建式GIS平台,基于COM技术,Microsoft推出了AetiveX控件技术,此控件已经成为当今可视化程序设计的标准控件,新一代的组件式GIS平台都是采用了ActiveX技术来实现的.
基于AetiveX的组件式GIS产品代表作首推MapObjects以及MapX等.
其中MapObjects由全球最大的GIS厂商ESRI(美国环境研究所)推出;MapX由著名的桌面GIS厂商美国Maplnfo公司推出.
这类G/S系统提供的是为完成GIS系统而推出的各种标准控件,使得GIS系统开发者不必掌握专门的GIS系统开发语言,只需熟悉基于W'mdows平台的通用集成环境,熟悉组件式GIS各种控件的属性,就可以利用常用的可视化编程语言实现GIS系统.
因此此类GIS系统在使用方便性、系统的无缝集成性、丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现灵活性方面具有较大的优势.
但其缺点就是这类基于控件技术的GIS一般只能支持W'mdows下的应用,而且对系统的资源和性能方面要求较高.

WcbGIS是Intemet技术应用于GIS开发的产物.
GIS通过wWw功能得以扩展,真正成为一种大众使用的工到m.
从WWW的任意一个节点,Internet用户可以浏览WebGIS站点中的空间数据、制作专题图,以及进行各种空间检索和空间分析,从而使GIS进入千家万户.
WebGIS系统具有非常多的特点,如它具有全球化的客户,服务器应用,它具有良好的可扩展性和跨平台性,它是真正的大众化GIS.
WcbGIS可以使用通用浏览器进行浏览、查询,额外的插件(plug-in)、ActiveX控件和JavaA∞plet通常都是免费的,降低了终端用户的经济http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c和技术负担,很大程度上扩大了GIS的潜在用户范围.
而以往的GIS由于成本高和技术难度大,往往成为少数专家拥有的专业工具,很难推广.
其唯一缺点是使用者必须拥有高速的网络,不然就无法获得这样强大的服务.

上述这些专业GIS平台虽然功能强大,可靠性高,但是这些平台要么只能使用在大型服务器上,要么限于Windows应用领域和网络应用服务.
因此很难将这些GIS平台应用在嵌入式Linux系统上,为了满足这方面的应用,本文设计了一种专门应用于嵌入式设备上的MiniGIS系统.
它将成为开发嵌入式设备图形化地图软件的可选工具之一.
由于MGIS是在QT/Embedded基础上进行开发的,所以凡是适合移植QT/Embedded的系统如Linux、vxWorks、uClinux等均可以使用MiniGIS,同时也使得开发出来的地图软件体积小、并且相对于其它GIS软件更具有价格优势【141.

3.
2MiniGIS用到的共享库介绍由于Mapinfo公司推出的矢量电子地图虽然得到了广泛的使用,但是由于种种原因,电子地图的格式还没有完全公开,因此对于电子地图的数据访问就必须使用到矢量电子地图读取的共享库GDAL/OGR.
同时由于GPS接收器输出的坐标是经纬坐标,因此必须通过投影坐标转换库PROJ.
4,变化成平面直角坐标,提供给电子地图使用,而且GⅨ也/oGR在地理坐标系和投射坐标系间转换数据时,底层也使用了PROJ.
4库进行相应的坐标转换工作,故GDAL库依赖于PROJ.
4库,因而MiniGIS也依赖于PROJ.
4库.

'甲浙江大学硕士毕业论文3.
2.
1第三章基于QTE的MiniGIS系统实现GDAL/OGR库简介DataAbstractionLibrary,SourceGeospatialGDAL是空间数据交换软件库的缩写,即Geospatial可以访问数十种地理信息数据.
它是由OSGeo基金会(OpenFoundation)基于开源软件发布的,旨在支持和建立高品质的开源地理空间软件,并推动社区项目的协作开发和使用.
作为一种开源库,它为各种支持的数据格式提供了一个简单的数据模型抽http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c象.
同时它还提供了一系列的命令行工具,可以进行各种数据的转换翻译和处理.

OGR作为GDAL库中的一个相对独立的部分,主要用于处理矢量形式的地理信息数据,现已实现了对十多种矢量GIS数据格式的读写功能.
OGR库主要用C-卜}语言实现,另外还提供了C语言的调用接口.

GDAI.
/oGR库广泛的应用于各种地理信息软件,如现在流行的GoogleEarth、GRASS、QuantumGIs以及各种GIS平台都是基于这个C++共享库开发的.
此共享库可以在GDAL/OGR官方网站http://www.
gdal.
org上进行下载,然后按照gdaltutorial的指导安装到系统中去便可使用.

对于Linux下的安装主要有以下几步:%cdgdal%.
/configure%make%su%makeinstall%exit对于W'mdows下的安装,除了以上步骤外,还需要用户自己修改Makefile里面的一些安装路径信息才能正确地完成安装.
3.
2.
2PROJ库使用PROJ.
4(CartographicProjectionsLibrary)是一个地理信息数据动态投射转换库,主要用于地理坐标系和投射坐标系数据的转换.
它支持超过一百种的投影变换,用户可以通过一些参数的设置和选择让它支持更多的投影变换,现在市场上流行的大多数地理信息软件(不管是商业软件还是开源软件)都需要它的支持,如MapServer、WebGIS等.
PROJ.
4同样提供命令行工具,通过这些工具用户可以进行简单的投影转换.
PROJ.
4最初是由USGS(UnitedStatesGeologicalSurvey美丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现国地质勘探局)的GeraldEvenden使用C语言开发的,现在由一些自由组织在维护这个库.
由于OGR库已对其进行了功能封装,所以在开发时不需要考虑其接口的调用.
同样对于它的源码可以在http://proj.
maptools.
org等官方网站上下载,对于安装一般mahttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228ckelibproj4、makelproj、makeinstall三条指令即可完成.
3.
3M嘶GIs系统设计MiniGIS旨在为电子地图数据库提供统一的访问接口,同时将与电子地图有关的所有操作进行封装,形成一个独立的系统.
系统主要功能模块及其关系如图3-1所示.
图3—1MiniGIS功能框图系统主要功能模块包括地图数据访问类抽象、坐标投影变换、地图检索、地图漫游、地图放大缩小以及地图绘制等.
地图数据访问类抽象主要完成基于GDAL/OGR库的地图数据库访问接口的统一设计,坐标投影变换主要完成基于PROJ.
4开放库的坐标转换设计,这两项均是为上层功能的实现提供基础支持.
GDAL/OGR库所能够支持的地图数据类型非常多,本系统暂时采用了Mapinfo公司的.
TAB格式矢量电子地图进行系统设计和分析,因此系统中主要使用OGR库处理地图数据,对OGR库进行一定的封装.
因此基于OGR库和矢量地图数据之上,对地图访问类进行抽象,MiniGIS系统所支持的数据格式也就只受到OGR库限制.

地图绘制模块功能是完成任意时刻的地图重绘工作,它不仅包括地图图元的绘出显示,同时还包括了文字层的绘制和用户结果层的绘制.
地图的漫游、缩小、1y浙江大学硕士毕业论文放大等均是实现用户浏览地图的功能.
第三章基于QTE的MiniGIS系统实现虽然MiniGIS在本文中是基于QT/Embedded来设计的,所有与GUI有关的操作都需要用到QT/Embedded的函数和模块,但系统在设计时尽量少地使用与GUI平台相关的函数和功能,只有在完成如地图绘制这种必须使用GUI来完成的功能时才使用QT/Embedded的函数.
因此本MiniGIS'系统能够非常方便的移植到其它的GUI平台上运行,只要将少部分与GUI相关的函数进行相应的转换就可以实现运行.

3.
4矢量地图数据库格式矢量电子地图数据格式多种多样,但是原理基本一样.
在不同公司推出的矢量电子地图中,又以MapInfo公司推出的.
TAB格式使用最为广泛.
因此本文将以Maplnfo公司的.
TAB格式作为范例来解释http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c.

矢量电子地图是以分层格式来存储的,它将地图里面的数据按照属性分成不同的层次来存储,即,将一幅矢量地图分成多个透明层的叠加,这些透明层就称为图层.
每个图层里存放一类信息,它由点、线、面等空问对象的集合组成.
图层的数目可以由地图的制作者确定.
层的概念就相当于具有相同属性的地图图元数据放在一起保存形成的一个整体,或者说图层是同类图元数据及属性的集合.
不同的图层代表了不同类型的图元数据,同一层则保存了相同类型的图元数据.
Maplnfo公司的.
TAB格式地图数据中的每一层由几种文件组合起来构成,这几种文件分别是:(1)属性数据表结构文件(.
TAB)属性数据表结构文件实际上是文本文件,它定义了地图属性数据的表结构,包括字段数(Field)、字段名称、字段类型和字段宽度、索引字段及相应图层的一些关键空间信息描述.
Mapinfo的属性数据有许多类型,如字符型、整形(2byte)、浮点型(8byte)、小数(用字符串形式表示)、日期型等【102].

(2)属性数据文件(.
DAT)属性数据文件实际上是二进制文件,它存放了完整的地图属性数据.
在文件头之后,是表结构的描述,其后首尾相接地紧跟着各条具体的属性记录.
(3)空间索引文件(.
ZD)空间索引文件记录了地图中每一个空间对象的最小外接矩形(Minimum丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现BoundingRectangle)及其空间数据文件(.
MAP)中的位置.
每四个字节构成一个指针.
指针的排列顺序与属性数据文件(.
DAD中的属性数据记录存放的顺序一致,这样就保证了空间数据与属性数据的互查询.
交叉索引文件实际上是一个空间对象的定位表.

(4)空间数据文件(.
MAP)空间数据文件具体包含了各地图图元对象的空间数据.
空间数据包括空间对象的几何类型、坐标信息和颜色信息等.
另外还描述了与该空间对象对应的属性数据记录在属性数据文件(.
DAD中的记录,这样当用户从地图上查询某一地图对象时,就能够方便地查询到与之相关的属性信息.

(5)索引文件(.
IND)索引文件并不是必须http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c的,只是当用户规定了数据库的索引字段后,Maphffo系统才会自动产生索引文件.
索引文件中对应于每个索引字段都有一个索引表.
在每个索引表中,先给出文件中的数据记录数目,然后按照索引顺序给出每条属性数据记录在对应的索引字段处的具体属性数据和该记录在属性数据文件(.
DAT)及空间索引文件(.
ID)中的记录号.

每一层地图数据都由它们之中的全部或者部分组成,因为如果某一层之中不存在图元对象,那么该层就会不存在与地图图元对象空间数据有关的.
MAP文件和.
D文件.
同时很多地图也不存在.
IND文件,它不是必须的,地图设计对,如果作者不规定数据库的索引字段,那么MapInfo系统就不会产生索引文州堋.

地图图层的数量其实是由地图的制作者按照某一种方法确定的,不同的公司制作的地图图层数量都有所不同.
现在比较流行的有九层地图,它们包括:road层、railway层、polygon层、interest层、landuse层、node层等,而PC机上使用较多的灵图软件就采用了更多的一种分法,它将各层又进行了细分,比如它将road层又分成了一级道路层、二级道路层、三级道路层、国道层、省道层、高速公路层等.
虽然各个公司推出的地图层数不一样,但这个不影响地图的访问和处理,因为每一层的访问方式一样,只要循环几次就能处理更多的图层.
图层的增加和细化可以将地图绘制得更加完善和准确,但同时也增加了系统的开销.

矢量电子地图的每层数据都是以矢量对象来保存的,就如矢量图形一样,图元对象都是以数学方式描述的曲线制作的图形.
例如道路层,这层地图图元数据大部分抽象成了直线,道路被描述成许多直线段,因此只需知道起点、终点以及丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现各个拐点的坐标就可以描述一条道路了.
其它各层也以同样的方式保存着各种图元,其问只有图元对象的数学描述方式不一样.
作为导航用电子地图,仅仅有一些图元信息还是远远不够的,系统中还需要各种各样的导航数据.
因此在图层中除了地图图元对象空间数据外,地图中还保存了大量的属性数据,这些属性数据就是专门为导航而设计的.
在导航时,车辆需要知道道路长度信息、道路等级信息、道路的通行能http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c力和找到大型停车场或者加油站,所有这些在图层的属性数据里都已经包含.
道路层是导航系统中最重要的图层,就road层而言,此层中的属性数据包括空间属性(即road的结点信息)、行政属性(属于哪个行政区划)、导航属性(等级、单双行道、名称、类型等)、通行能力等大量的数据,如表3.
1所示.
其它各层属性数据与此大致类似,只是保存的内容不同.

3.
5地图数据访问工具类设计MiniOIS是通过OGR库来实现访问地图数据的功能,而OGR库尽管其类结构定义得还比较清晰,但是对于一些常用操作,直接使用OGR库接口显得比较繁琐,所以本文在OGR库C抖类的基础之上再进行了一层封装,这样来降低直接操作OGR底层类的复杂度,同时也可使得MiniGIS系统的主干代码变得更加清晰.
同时系统还进行了一些类的抽象,形成一些虚拟的基类,这样构成了MiniGIS系统针对地图数据的主体结构,如下页图3.
1所示.
MGisMap是针对整个地图数据库进行的抽象,MCrisLaycr是对地图每一层进行的抽象,MG-isFeature是针对每层地图中的图元对象及其特征属性的抽象,MGisOeometry是对地图矢量图形的抽象.
下面几节将分别介绍这几个基类的设计以及在MiniGIs系统中的重要作用.
3.
5.
1地图抽象类MGisMap是抽象于0GR基础上封装出来的,它是对GIS地图数据访问的统一接口.
对应于0GR库没有与之对应的Map类,oGR库在访问地图数据库时是采用OGRDataSource类来处理,但是OORDataSource访问地图数据库时每次只能打开地图中的一层进行处理,释放之后再打开另外一层来访问处理,这样OGR库就不能对整个地图数据库进行统一的访问.
而MGisMap是面向整个地图对象来抽象的,因此它抽象出了地图处理的基本功能,也大大地简化了使用直接丫浙江大学硕士毕业论文第三章基于arE的MiniGIS系统实现OGRDataSouree访问地图数据库的复杂性.
MGisMap类除了地图数据的统一访问接口外,还包括了地图的打开、地图搜索的抽象、地图图元过虑的抽象、文字层和用户结果层的抽象.
MGisMap类的大致代码及其主要功能描述如下:://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c表3.
1道路层属性数据属性名域值空间属性路段编号,始连接点编码编号,终连接点编码行政区划1.
行政区划,2.
所在编码侧,3.
预留编码交通标志红绿灯个数枚举无红绿灯,/>3个…导航属性道路名称,等级,类型,营运里程,高度,道路代码,出入口代编码国道、省道、高速……l,2,4Byte,4Byte,4Byte定义代码路段的编码行政区划对象编码编码枚举Or1,2,3,4,……快速路,立交部分…l,2,3,……左转、直线、急转……国133,入40B……通行能力编码码……平均车速,高峰车速,高峰时段,功能等级,KMm24小时制枚举速度相关主要道、一级道……单行、双行,几车道编码1,2,3……交通流向,车道数…l.
2,……通行限制通行车辆类型,时问、复合数据1/10M1/10顿收费属性类型,标准,金额……枚举or数值是否收费,$/KIVI…编码一些通行限制1,2,3……A'B,C'D……24hour转弯,高度、速度载重限制……V浙江大学硕士毕业论文第三章基q:QTE的MiniGIS系统实现图3-2classMGisMapGIS系统地图基类结构{private:MGisMapO;public://防止任意实例化staticMGisMap'open(stringfilename);//实现地图打开功能MGisLayerP垃get_layer(hatoffset);intdraw(MGisDrawContext+de,intdrawflag);//地图的绘制有关set_filter(MGisFhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cilter*filter);voidvoidadd_filter(MGisFilter*filter);MG-isFilter+get_filterOconst;const脱图图元过虑有关voidscarch(MGisSearcher*searcher,stringlayer_name=");MGisResllltLayer'get_resultlayerO;private:MOisTextLayer'textlayer;}皮字层MGisResultLayer*result_layer;|慎;户锗果层……Vectortab_ds;∥图层访问指针Vectortab_layer;MG-isFilterEx'filters:一24—1lrr浙江大学硕士毕业论文voidloadfrom第三章基于QTE的Mi日jGJs系统实现directoryO;,,用来加载地图数据库};在MGisMap类之中定义了静态函数staticMGisMap*open(filename)打开电子地图.
它可以在MGisMap对象定义之前调用,返回MGisMap对象指针创建整个地图数据库抽象.
在openi函数中调用私有函数load_fromdircctorYO打开地图数据库,将访问地图数据库的各种指针保存到MGisMap类的私有数据中.
如tab_layer中保存了打开的所有地图图层指针,提供给此后的MiniGIS系统访问地图数据库使用.

MGisMap类中MGisT叙tLaye件textlayer,MGisResultLayer*result_layer保存了text层和result层的指针,只要需要就可以通过它们调用这两层数据来处理.

同时MGisMap类中还对search和filter功能进行了封装,但是具体的实现都要在相应的类中完成.
3.
52地图Layer抽象类://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cparMGisLaycr类是针对OGR库qbOGRLayer类的一层封装,但同时也是对OGR中"层"概念的进一步抽象.
系统将对Layer的操作提取出来,形成一个独立的抽象MGisLayer类,在该抽象上,系统提供了对OGRLayer封装实现MGisMapLayer类,即该类是从MGisLayer类继承而来.
因此MGisMapLayer类是对应于地图数据库中的层概念,是所有Layer中最重要的部分,地图数据库的真正访问都是经过它来获得的.
同时,系统还实现TMGisTextLayer类和MOisResultLayer类,分别用以提供文字层和结果层的操作以及显示功能.
MGisLayer类及其继承类之间的关系如图3-3所示.

MC_,-isTextLayer类是对地图图元对象的属性(名称)进行的一层封装,这样就可以对所有图元对象的文字标注进行统一处理.
MGisResultl_ayer类主要完成对用户各种操作(搜索、查询等)结果的统一保存和处理,并在适当的时候对各种结果进行绘制.
MGisMapLayer类对OGRLayer类封装并进行了相应功能的增强和实现,进一步简化地图数据库的提取.
MGisMapLayer类的大致代码及其主要功能描述如下:classMGisMapLayer:publicMGisLayer{V浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现占对用户操作中各种搜索结果进行保存,进行封装,占Laye冲最重要的部分.
它完成所有地图图元的获取,对图元进行基本的过虑占对地图中的图元的属性(名称)进行封装操{仁后,完成图层封巍圈3-3所有【ayer层次结构public:MGisMapLayer(MGisMap+pareatmap,OGRLayer*layer);vil'Ulal—MOisMapLayerO;//构造,指向parent_mapstringget_name();//获得图层name://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cpar//OGRLayer指针访问底层OGRLayer*get_ogr_layer();voidget_featurerewind();,,重读地图对象准备MGisMapFeature+getnext_feature();//获得下一个图元特征virtualvoidsearch(MGisSearcher*searcher);vLmlalintdraw(MOisDrawContext.
dO;private:OGRLayer*layer;);在MGisMapLayer类中定义了OORLayer*layer保存了访问底层的接I=1,所有Layer需要访问电子地图数据库时都需要用到这个私有成员,它是OGR库中实现访问地图的类.
Draw函数是实现每一层图元的绘制,search函数是在此层图元中搜索地图图元对象.
在此类中有两个关于feature的函数,它们是实现MGisMapLayer类的关键,层只是对地图的图层进行抽象,每层地图还拥有很多的国元特征对象(即feature对象),要实现具体的地图数据访问还需要MGisFeature丫浙江大学硕士毕业论文类的支持.
第兰章基于QTE的MiniGIS系统实现3.
5.
3地图Feature抽象类MGisFeature是MiniGis对地图图元信息的封装,提供了常用的图元操作.
同时,MGisFeature也是MiniGis对OGR|对装的核心部分.
地理信息数据的基本单位,就是图元(Feature),因此,MGisFeature所承担的责任是最多的.
基于单一职责原则,系统将MGisFeature的各种功能和责任分割到了更多类中,从而达到了良好的设计.
MOisFeature类及其继承类关系大致如图3_4所示.

图3-4MGisFeature类及其继承类关系MOisResultFeature类是相对于地图图元对象来说的,结果特征图元对象可以是用户各种操作的结果对象,也可以是用户根据规则定制的图元对象.
因此它不仅能够包括所有地图图元http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c对象,还能够包括用户根据对象规则定制的对象,这些用户定制的图元对象还可以通过函数保存到地图数据库中去.
MGisResultFeature类是一个抽象基类,它有许多具体的子类,如PointFeature、PolygonFeature、LineFeature等.

MOisMapFeantre类是地图图元特征类,是对OGR库中的OORFeature进行封装,它不仅可以访问图元属性数据,还能完成访问矢量图形数据的任务.
MGisMapFeature类的大致代码及其主要功能描述如下:classMCrisMapFeature:publicMGisFeature{public:virtualstringgetname();,/图元名称丫浙江大学硕士毕业论文virtualeonst第三章基于QTE的MiniGIS系统实现MCJisExtentget_extent0;//图元大小范围field(eonststring&field_name)eonst;virtualconststringge=tvirtualvirtualMGisLayer'get_layer0;MGisGeometry+get_geometry0;draw(MGisDrawContext+dc);virtualhatvirtualprivate:OGRFeature+get_ogr_feamreO;MGisLayer+layer;OGRFeature*feature;//OGR类MG-isGeometry+geometry;);MGisMapFeature类是对OGRFeature类的封装和增强,因此它包含了OGRFeature的指针,用来访问底层数据.
类中的get_field函数能够获得图元的属性数据,而get_name函数能够得到图元名称.
类中还提供了draw函数来绘制图元,但它的实现要根据MGisGeometry来确定.
MGisGehttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cometry类是矢量图形的抽象,由数学方式描述的矢量图形数据由它进行统一的访问和处理.
3.
5.
4地图Geometry抽象类图元信息最终是存储为矢量图形信息,对于这些图形信息,MiniGIS需要统一的方式进行操作和绘制,因此对应于OGR库中的各种图形对象,本文又进行了一层封装.
图3.
5为MGisGeometry类及其子类与0GR库中各个图形类的关系图.
……-,……!
陆陆I一一一一一一>:GI)AI/OGRIL.
…一一JIL.
…一.
JI图3-5MGisGeometry类及其继承类关系一28—丫浙江大学硕士毕业论文第三章基于arE的MiIliGIs系统实现图中MGisGeometry类是对OGR库中OGRGeometry类的封装,同样MGisGeomLine类是对OGR库中OGRLine类的封装,在MGisGeomLine类中除了保存OGRLine指针外,同时它还完成了图形对象的绘制功能.
其它各图形类对象(MCJiSGeomPoint、MGisGeomPolygon等)都一样,除了保存对应的访问底层图形的指针外,还都实现了图形本身的绘制.

3.
6MiniGIS地图的绘制实现地图的绘制工作是MiniGIS中最重要的工作,因为它是系统呈现给用户的最直观的部分,地图绘制的好坏直接决定MiniGIS系统的效果.
地图的绘制工作是依赖于GUI设计的,因此MiniGIS系统也要依赖于一种GUI才能正常工作,本文使用QT/Embedded来设计.
首先地图的最终绘出肯定需要用到QT/Embeddcd的绘图函数,然后,呈现给用户部分的地图,由于用户的操作和各种处理,肯定需要不断的重绘,而重绘一般GUI都是通过消息进行传递的,因此MiniGIS系统依赖QT/Embedded消息响应来调用相应的重绘函数,由MiniGIS系统实现重绘功能.

MiniGIS系统专门设计了一个MGisView类来完成地图的绘制工作.
系统使用MCrisView类来处理所有地图绘制工作,所有MiniGIS系统中其它类均可为它服务完成地图的绘制.
同时由于地图绘制工作需要QT/Embedded的支持,因此http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cMGisView类也就成了MiniGIS与QT/Embedded的接口.
为了让MGisView类具有接收和发送重绘消息的功能,系统在设计时利用了QT/Embedded的基类,将MGisView从QObject派生而来.
这样只要视窗有所改变,MiniGIS系统就可以发送重绘消息,由QT/Embcdded捕获消息然后交由MGisView类来处理,这样就可以完成地图的重绘工作.
MGisView类的具体设计及其功能介绍如下:classMGisView:publicQObject{Q_oBJECTsignals:void嘶dgcl=cbangedO;public://重绘消息voidinvalid_widget0{emitwidget_changed0;)一29—丫浙江大学硕士毕业论文voidvoid第三章基于qrE的MiniGIS系统实现change_pixel_length(floatscale,boolis_zoomin);ehange_state(MGisViewState+state);/,改变地图状态hatgetvoidvoidvoidvoidvoidvoidvoidvoidrnemjax_len_.
global0eonst{returnmem_px_len__global;)//设置过滤器'set_filterO;setup_map(MCrisMap*map);set_bg_size(10ngbg_to_win(10ngwin_to_bg(10ngwidth,long//初始化地图height);x0,longxO,longy0,long&xl,long&y1);yO,long&xl,long&y1);set_win_xy(10ngX,longy);zoom_to(intpixel_length);,/改变比例尺set_center(doubleortho_centhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cer_x,doubleortho_eenter.
.
y);boolneed_redraw_backgroundO;voiddraw_background0;//重绘背景inton_paint(QPaintDevice'paint_dev);voiddraw_seareh_result(MGisDrawContext+dc);//地图检索KeySearcher*key_search;private:MGisMap*gismap;MG-isViewState+state;QPixmap*memj】m;longwin_x0,win_yO;intwin_width,hat//打开的地图数据库/,内存绘图win_height;//窗口大小//背景图大小bg_、Ⅳid也,bgheight;doublemem_xO,mem_yO;hatmem_px_len;doublemem_xO_global,mem_yO_global;//比例尺);地图的绘制工作是从地图数据库(可以看成一张大图,即MGisView类中私有成员MOsMap木gismap打开的地图数据库)中提取一张小图的数据出来绘制,因此先设置一个矩形过滤器由MGisView类中set_fiiterO完成,然后要知道小图在XP_.
尺例比图地丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现地图数据库中的坐标(小图在大图中的起始坐标)才能提取,即MGisView类中私有成员memxO,mem_yO,同时需要知道小图的大小,即bgwidth,bg_height.
由于采用了大于窗口大小内存绘图,从地图数据库中提取出来的小图部分是内存绘图部分,因此取出来的内存图不会全部显示,需要知道显示窗口在内存绘图(小'图)中的起始位置坐标,即MGisView类中存放的位置坐标win_x0,win_yo.

内存绘图方法是先将地图http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c数据先绘制在内存画布上,不直接输出到窗口显示,MGisView类中Qvixmap木meInpm是内存画布,当绘制完成后才通过Q盹nbedded提供的bitblt函数一次性将内存绘图输出到窗口显示.
内存画布可以设置为几倍窗口的大小,因此可以只将部分内存图复制到窗口上显示.
MiniGIS系统设计时暂将内存画布设置成窗口的九倍大小,即将bgwidth和bg_height分别设置成win_width和win_height的三倍.

MGisView类中的MGisViewState*state是代表地图浏览状态(漫游、放大或缩小)中的一种,当用户移动地图时state将利用MG-isView::invalid_widgetoi累i数来发送重绘消息,MiniGIS系统会调用MGisView类中的砬on_paint(QPaintDeviee*paint.
dev)来处理重绘工作,重绘过程中如果需要绘制背景地图,那么将调用voiddraw_background0根据当前的比例Y己(mem_px_len)来完成地图所有图元对象的绘制.

MiniGIS系统在启动时也会调用On系统会调用voidsetup_map(MGisMap*map)来初始化设置地图绘制的几个重要显示参数,即MG-isView类中保存的数据:memlen:m锄x0:内存绘图在数据库中X位置,即是内存绘图左上角在地图数据库中的起始坐标xO.
mem_y0:内存绘图在数据库中Y位置,即是内存绘图左上角在地图数据库中的起始坐标yo.
winx0:显示窗口在内存绘图中的x位置,即是显示窗口左上角在内存画布中的起始位置坐标x0.
win_vO.
.
显示窗口在内存绘图中的Y位置,即是显示窗口左上角在内存画布中的起始位置坐标yo.
这五个参数是地图绘制和显示中最重要最基本的参数,地图的操作和重绘均'丫浙江大学硕士毕业论文是通过改变和调整这五个参数来实现的.
第三章基于QTE的MiniGIS系统实现3.
6.
1地图重绘流程http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c地图的重绘,是当地图的显示参数改变时,由MiniGIS系统调用MGisView类中的onpaint函数来重新绘制地图呈现给用户.
因此地图的重绘流程即是on_paint函数的执行过程,该函数执行过程如图3-6所示.

图3.
6地图重绘流程地图重绘开始时如果地图数据库没有打开,那么绘图将直接结束,因为无法获取原始地图数据,也就无法绘图.
对于文字层和结果层,重绘时是直接将其绘制在窗口上,即背景图上,这是因为文字层和结果层的数据是不确定的,需要动态绘制,每次用户移动地图之后,需要显示的文字和结果数据都将不同,因此每次地图重绘的时候都需要将这些数一32—丫浙江大学硕士毕业论文据重新读取出来显示给用户.
第三章基于QTE的MiniGIS系统实现地图的重绘采用了内存绘图的方法,即先在内存上开辟一张画布(mcmnewQPixmap),然后先在这张画布上绘图,绘制完成之后再将这张图一次性快速的复制到当前窗口上,这样可以防止绘制大量图元时时间较长而出现的绘图闪烁现象.
同时可以在内存绘制较大的地图,'每次复制部分内存绘图显示到窗口,这样只要用户在漫游时没有超出内存地图的边界,系统只需要从内存画布复制过来即可,系统响应速度也得到加快.
只有在用户漫游时超出内存画布边界,系统才再一次读取地图数据库,重新绘制一张内存画布,即流程中背景图的绘制draw_backgroundO.

3.
6.
2背景图的绘制背景图的绘制,即内存绘图的过程,是从地图数据库中读取相应的地图图元数据,然后将其描绘在内存画布上,它是整个地图的绘制过程中最重要的部分.
内存画布不是每次重绘时都需要更新,只有在用户移动时超出边界或者用户进行缩放操作时,需要重新绘制.
这个条件的判断是由MG-isVicw类中boolneed_redraw_backgroundO函数来完成的,而内存绘图是由draw_backgroundO完成的.

nccd_rcdraw_backgroundOi函数主要通过五个绘图参数中的三个来判断,即mem_.
px_len(地图比例尺)、mere—xO、memhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c_yO(内存绘图在数据库中x、Y位置,即内存绘图左上角在地图数据库中的起始坐标),只要这三个参数中任意一个改变,内存画布就需要重新绘制.
mcmpx用户可能进行了缩放,因此MiniGIS系统必须读一张更大或更小的地图到内存上来;mcm_xO、mem_yO之一改变代表用户漫游地图时超出了内存绘图的边界,因此需要重绘.
内存绘图需要通过读取地图数据库来重新获得地图图元对象,因此需要用到地图数据访问工具类来实现.
背景图的绘制流程及地图数据库访问的工具类调用关系如图3.
7和图3.
8所示.
在图3—7中,drawbackgroundO数首先设置图元过虑器、复位文字层、调整设置已改变的显示参数,为绘制地图做好准备工作.
然后在获得下一图层的指针之后,调用laycr->draw(dc)函数逐层绘制背景图,layer是一个基类MGisLayerV浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现指针,但是它指向了MGisLayer继承类MGisMapLayer,根据虚函数调用原则例(多态性),layer->draw(dc)此句将会调用MGisMapLayer::draw(dc)来绘制图层.

由于每个图层中含有大量的图元特征对象,因此MCJisMapLayer::draw(dc)在ResetReading图层的Feature对象之后就调用feature->draw(dc)函数绘制图元特征对象.
同样根据虚函数调用规则(多态性)feature->dra0'(dc)实际上将调用MGisMapFeature::draw(dc)来完成特征图元绘制.

drawbackground()MGisMapLayer.
:draw(de1图3-7图层绘制流程图一34—V浙江大学硕士毕业论文MGisMapFeature::draw(dc)第三章基于QTE的MiniGIS系统实现图形对象种类很多,以sGeomPolygon::draw(dc)为例.
缃JGeometry'I获得http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c描述图形原始数据Polygon以点描述fetch_lxfintsOf使用PROJ.
锉标转换latlong_to_window(size,墨y)I获得已设置好aqdcdc一>get_dcO0绘制图形ckawPolygon(array)1L绘制完成退出r~图3—8图元对象的绘制流程图MGisMapFeature::draw(dc)函数中首先获得图形对象,此处返回MGisGeometry指针是为了利用多态性,get__geometryOi函数会根据图元的属性构造一个相应的具体对象的指针,即MGisGeometry继承类对象指针,如MGisGeomLine、MG-isGeomPolygon等.
然后通过调用geom->draw函数来绘制矢量图形,此处geom是MGisGeometry指针,通过多态性调用MGisOeometry相应的继承类来实现矢量图形绘制.
MOisMapFeature::draw函数除了调用图形绘制函数外,它还要完成图元名称属性(text)l拘提取,并设置好其字体画笔之后添丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现加到文字层(textLayer)qb去,为文字层的绘制做好准备.
最后是矢量图形的绘制,也是地图绘制实质性的工作.
矢量图形的绘制需要MGisGeometry类及其所有继承类来共同完成,每一种类完成一种矢量图形的绘制工作,绘制的最底层操作还需要QT/Embedded来支持.
各种矢量图形的绘制过程基本上一样,以MGisGeomPolygon::draw来说,首先需要获取描述矢量图形的原始数据,polygon矢量图形是以点描述的,因此获取所有点的坐标,然后通过调用QT/Embedded底层函数实现即可.
但是有一个问题,地图数据库中所有的坐标都是以经纬度坐标形式保存的,不能直接用来绘制图形,必须经过投影坐标变换,将其转化成相应的windows坐标才能绘图.

3http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c.
6.
3投影坐标转换GIS中的坐标系定义是GIS系统的基础,正确定义GIS系统的坐标系非常重要.
地图坐标系由大地基准面和地图投影两项共同确定.
大地基准面是利用特定椭球体对特定地区地球表面的逼近,因此每个国家或地区均有各自的大地基准面,我们通常称谓的北京54坐标系、西安80坐标系实际上指的是我国的两个大地基准面.
我国参照前苏联从1953年起采用克拉索夫斯基(Krassovsky)椭球体建立了我国的北京54坐标系,1978年采用国际大地测量协会推荐的lAG75地球椭球体建立了我国新的大地坐标系——西安80坐标系.
因此相对同一地理位置,不同的大地基准面,它们的经纬度坐标是有差异的.
地图投影是将地图从球面转换到平面的数学变换,如果有人说:该点北京54坐标值为X=4231898,Y=21655933,实际上指的是北京54基准面下的投影坐标,也就是北京54基准面下的经纬度坐标在直角平面坐标上的投影结果【16】.
因此地图投影实质上是在地球面和平面之间建立的一种映射关系.

目前GPS定位所得出的结果都属于WGS84坐标系统,WGS84基准面采用WGS84椭球体,是地心坐标系,即以地心作为椭球体中心的坐标系.
我国的基本比例尺地形图(1:5千,1:1万,1:2.
5万,l:5万,1:10万,1:25万,1:50万,1:100万)中,大于等于50万的均采用高斯一克吕格投影(Gauss-Kruger),又叫横轴墨卡托投影(TransverseMercator);小于50万的地形图采用正轴等角割园锥投影,又叫兰勃特投影(LambertConformalConic).
我国的GIS系统中应该采用与我国基本比例尺地形图系列一致的地图投影系统.

1甲浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现本MiniGIS系统中,使用了高斯.
克吕格投影来变换坐标.
MiniGIS系统在处理地图数据库时使用北京54坐标系,在处理GPS接收器的数据时需要首先切换到WGS84坐标系统然后才进行坐标变换.
本文在设计MiniGlS系统时用到了两个类(MGisEnv,MGisCS)来处理与坐标系统有关的问题.

://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cMGisEnv类是基于OGR库中OGRSpafialReferenee类设计的,此类提供了对地图投影系统和椭球体的设置,因此MiniGIS系统就具有了设置和更换地图投影系统的功能,设置好地图投影系统之后,系统就能生成相应坐标转换公式,这些坐标转换公式都保存在MCrisCS类中.
MGisEnv类中存储了MGisCS类(MiniGISCoordinateSystem)的指针,因此通过该指针可以调用到相应的坐标转换公式来进行坐标转化.

MGisCS类专门为坐标转换而设计,此类根据MGisEnv类中设置好的地图投影系统生成的各种坐标转换公式,系统在绘制地图时可以进行任意的调用.
MG-isCS类的设计代码及相应的功能介绍如下:classMCJisCS{private:OGRCoordinateTransformation+trans_U_ortho;OGRCoordinateTransformation+transortho_ll;public:OGRCoordinateTransformation'gct_trans_ll_orth00;OGRCoordinateTransformation+get_trans_ortho_llO;voidlatlong_to_ortho(constint&num,double+X,double'y);latlong(eonstint&num,double+X,double+y);voidorthotovoidortho—to—window(constint&num,double+)【'double+y);(constint&hum,double+舄double+y);voidwindow—to—orthovoidlatlong_to_window(constint&hum,double+)【,double+y);latlong(eonstint&hum,double+骂double+y);voidwindow—http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cto);其中trans__ll_ortho和trans_ortho_U是两个主要的坐标转换公式,它们将坐标在球面坐标(经纬坐标)与平面直角坐标之间进行转换.
MGisCS类中还包含了到;tsilfxet.
据数1甲浙江大学硕士毕业论文第三章基于QTE的MiniGlS系统实现windows坐标的转换,地图数据首先由经纬坐标通过latlong_to_ortho函数转化成直角平面坐标上的投影坐标,然后通过ortho—to—window函数完成到windows坐标的转换.
latlong_to_ortho函数通过trans__11__ortho公式实现,而ortho—to—window函数只要通过平移缩放就可以将坐标转化成功.
而latlong_to_window函数只是latlong_to_ortho函数和ortho_to_window函数的合成而已,坐标转换的逆过程基本上与此相似.

3.
6.
4文字层绘制MiniOlS系统中设计了MGisTextLayer类来处理与文字有关的工作.
MG-isTextLayer类设计及其功能介绍如下:classMGisTextLayer:publicMGisLayer{public:voidvoidintintintresetO;result__reset0;//重置地图的text//重置结果的textlistlistdmw(MGisDrawContext+dc);//绘制文字层add_text(MGisText+texO;add_result_text(MGisText+text);one,,图元名称添加到textlist//加到result_textlisthatcountprivate:string_in_tcxtlist(stringstr);listtextlist;listresulthat//图元http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c名称list数据//text结果reet_in_region(MGisText*text);region(MGisText+text);intreetinresult};其中在背景图(即内存图)重新绘制时需要首先调用resetO'西i数用来重置textlist,然后背景图每绘制一个图元对象之后,就会调用add__text(MGisText+)将其名称加到textlist中去,并在适当的时候由MGisTextLayer::draw(de)将其绘制到窗口上去.
同时MGisTextLayer类中还保存了用户操作结果数据的名称列表1y浙江大学硕士毕业论文result第三章基于QTE的MiniGIS系统实现textlist,它能进行同textlist完全一样的操作.
MGisTextLayer操作的基本数据是MGisText,因此其部分操作还需要MGisText类的处理和实现.

MG-isTcxt类是专门为图元对象名称而设计的,它的每一个对象对应了每一个图元的名称,此类中除了保存了字符串之外,还保存了与图元名称字符串相关的字体、画笔画刷、字符输出位置坐标等数据.

文字层的绘制是动态的,每次窗口的重绘都会调用文字层输出函数,文字层输出时只输出了窗口显示部分的文本,而MGisTextLayer中保存的是整个内存绘图图元的文字,因此每次用户移动地图时,只要不超出内存图边界,背景图部分重绘只需要从内存绘图重新复制到窗口上即可,而文字层的重绘工作就必须从MGisTextLaycr中调用窗口将显示的文字绘制到窗口上,即MGisView中的onpaintO函数每次都需要调用gismap->draw(&dc,Draw_Text)来绘制文字层gismap->draw(Draw_Text)又将调用textlayer->draw(dc)来完成文字层的实质绘制工作.
textlayer->draw(dc)绘制文字层的流程如图3-9所示.

MGisText=draw[o~开始绘制习上医.
获得字符数据吾0臣字http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c符编码转换I‰.
眵GBK专Unicode~j.
、E设置字体画笔等I}setupde(dc).
输出文本}drawTexl(…)上f完成退出一"图3-9文字层绘制流程图1丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现文字层的绘制过程中还需要进行字符编码的转换,这是因为地图数据库中存放的图元属性中文名称都是以GBK进行编码的,而系统运行的QT/Ecmbcddcd系统只支持Unicode编码,因此在文字的输出前必须要进行字符编码的转换.
字符编码的转换功能是QT/Eembedded中QTextCodec类提供的,只需以下两句就可以实现编码转换.

QTextCodee*texteodec=QTextCodee::codecForName("GBK");QStringqunistr=texteodee->toUnieode(chinese_string);其中chinese_string是从地图数据库中读取出来的GBK编码的中文名称,转化结果qunislr是Unieode编码,这样就可以使用QT/Eembedded的字符处理函数直接输出中文.

3.
6.
5结果层绘制MiniGIS系统中同样设计了MGisResultLayer类来处理与结果对象有关的工作.
MGisRc砌tLaycr类设计及其功能介绍如下:classMG-isResultLayer:publicMGisLayer{public:……MCdsResultLayer(MCrisMap*parent_map);virtual~MGisResultLayer0;stringvoidvoidge!
t_nameO;add_feature(MCrisResultFeature+feature);clear_feature0;hatdraw(MGihttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228csDrawContext+dc);private:listfeature);list;MGisResultLayer类用list保存了各种MGisResdffeature对象,如PointFeature、PolygonFeature等,这些MGisResultFeature对象都实现了本身图形的绘制工作.
MGisResultLayer类中的draw函数也就是分别调用了每个feature对象的draw函数来完成结果层的绘制.

1丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现3.
7地图漫游缩放和测距实现地图漫游、放大、缩小和测距是地图操作的四种基本状态,也是用户可以执行的四种基本地图控制方式,地图控制处理的好坏直接影响到后续在电子地图基础上的应用.
地图控制方式主要是通过鼠标消息响应、地图显示参数更改、和地图重绘来实现.

对应于每种状态在MiniGIS系统中都设计了一个相应的类处理其功能.
MGisViewZoomln类处理地图缩小的功能,MGisViewZoomOm类处理地图放大的功能,MGisViewDrag类处理了地图漫游时的功能,MGisViewDistance类实现了地图中距离的测算,它们均从虚基类MGisViewState继承而来,图3.
10是它们之间的相互关系及其主要成员函数.

图3一lO漫游、缩放和测距类及其与基类关系3.
7.
1地图漫游地图漫游主要由MGisViewDrag类来实现.
用户在漫游地图,即移动窗口部一41—1r浙江大学硕士毕业论文第三章基于arE的MiIIiGIs系统实现分地图时,由于地图的绘制采用大于窗口大小内存绘图方法,只要用户移动时没有超出内存画布的边界,MiniGIS系统就只需要将内存画布中数据重新复制一片到窗口中即可.
MGisViewDrag类比较简单设计如下:classMGisViewDrag:publicMGisViewOpened'{Publhttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cic:……MGisViewDrag(MGisView*view);voidonmouse_down(intpre_x,hatprey);voidon_mousevoidonmove(intdes_x,intdesj);des_x,hatdcs-y);mouse_up(hathaton_paint(QPaintDeviee'paint_dev);private:……boolkey_dowmhatprex,prey;hatmove_x,move_y;);当用户切换到地图漫游状态时,QT/Embedded的用户交互界面就会通知MiniGIS系统地图操作状态已经切换到漫游状态.
然后MiniGIS系统会调用MGisViewDrag类来进行相应的鼠标消息响应.
当用户鼠标按下时调用on_mouse_down函数来响应,保存按下时鼠标位置到pre_x、prey中,鼠标移动时将调用on—mouse—move函数来响应,直到用户松开鼠标.
on_mouse_up函数将计算地图移动距离movex、move_y,同时设置地图显示参数并且发送地图重绘消息来实现地图重绘,从而达到漫游效果.

on_mouse_up函数中设置地图的一组显示参数是最重要部分,它关系到在地图重绘时是否需要进行背景图的重绘.
漫游时不会引起显示参数mem__pxJen(地图比例尺)的改变,它影响的地图显示参数是其它四个memxO、mereyO(内存绘图在数据库中位置)、win_xO、win_yo(_显示窗口在内存绘图中的位置).
该函数首先计算出地图移动距离move_x和move_y,然后根据移动距离判断用户移动窗口时是否超出了背景图的边界.
如果窗口没有超出背景图的边界,那么on_mouse_up函数只需要在原来的丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现win_x0、win_y0之上叠加move_x、movey然后发送地图重绘消息即可.
MiniGIS系统在重绘地图时就不需重绘背景图,只需从背景图上重新复http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c制一片到窗口上即可.

如果用户移动时窗12超出了背景图边界,那么on_mouse_up函数将更改地图显示参数mem_x0、mem_y0,并将窗口设置在背景图的中心位置(设置winwinxO、vO),同时发送地图重绘消息.
MiniGIS系统在重绘地图时检澳4到mere—x0、mem3.
72地图放大地图放大主要由MGisViewZoomOut类来实现,在收耍佣户地图操作状态切换到放大状态后,MiniGIS系统就调用MGisViewZoomOut类来完成对用户鼠标信息的响应、地图显示参数的设置及更改、以及发送地图重绘消息等功能.
用户进行缩放操作必然会引起背景图的重绘,因此MiniGIS系统在缩放时只要利用响应的类设置好地图显示参数,然后发送地图重绘消息即可.

放大的方式一般有两种,点击放大和矩形放大.
所谓点击放大即是以用户鼠标点击点为中心,利用事先设定好的放大倍数进行地图的放大.
所谓矩形放大即是用户把选种的矩形区域放大成全屏显示.
MiniGIS系统对两种放大方式都进行了实现.

MiniGIS系统进行放大时主要设置的地图显示参数有三个mem__pxlen(地图比例尺)和memxO、mereyO(1勾存绘图在数据库中位置),窗口每次均设在背景图的中央,因此显示参数win_xO、winvo(显示窗口在内存绘图中的位置)每次都设置成一个固定值.
系统进行放大时,MGisViewZoomOut类中函数将根据鼠标点击位置确定mem_px_len、mere—xO、mem_yO从而实现地图的放大.
MiniGIS系统处理放大的流程大致如图3-11所示.

MiniGIS系统在切换到放大状态之后,主要利用MGisViewZoomOut类中的Onmouseup函数来响应鼠标松开消息,并通过判断鼠标松开点的坐标与鼠标按下点的坐标的比较来判断属于那种放大类型.
鼠标松开点坐标如果等于鼠标按下点的坐标那是用户进行点击放大,如果两者不相等则用户是进行矩形放大.
MiniGIS系统将根据响应的放大类型进行相应的地图显示参数设置,最后发送地图重绘消息,MiniGIS系统响应重绘消息即可完成地图的放大.

切换到放大状http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c态后r1丽墓矿习I.
图3.
1l地图放大流程图3.
7.
3地图缩小地图缩小主要由MGisViewZoomIn类来实现,与地图的放大基本类似,在收到用户地图操作状态切换到缩小状态后,MiniGIS系统就调用MGisVicwZoomIn类来完成对用户鼠标信息的响应、地图显示参数的设置更改、以及发送地图重绘消息引起地图重绘等操作,来实现地图缩小.

地图的缩小同样有两种方法,点击缩小与矩形缩小.
地图缩小的流程以及实现基本上与地图的放大一样,在此就不再赘述.
3.
7.
4地图测距地图距离测算功能主要由MGisViewDistance类来实现,它主要完成了两点间的直线距离测算功能.
在收到用户地图操作状态切换到测距状态后,MiniGIS系统就调用MGisViewDistance类来响应用户鼠标信息,从而完成两点间距离测算功能.
在测距状态下,当用户按下鼠标,MiniGIS系统就会调用MGisViewDistance类的ononmousedown函数记下起点坐标,然后当用户鼠标每移动到一个点上,mousemove函数响应鼠标会实时的计算出两点间的距离显示在窗口上,最后当用户松开鼠标,on_mouse_up函数会计算出最终距离并显示给用户.

两点问直线距离计算过程比较简单,首先将起点与终点的windows坐标都转化成投影平面直角坐标系中的坐标,通过MGisCS类中window_to_ortho函数即可实现,然后通过数学上两点间的距离公式即可算出距离.

3.
8地图检索功能设计地图的检索,即根据用户界面输入的关键字信息,然后从电子地图数据库中搜索出相应的地理信息,并将其显示出来的过程.
其实这也是嵌入式导航系统简单的地图定位功能,即,将地图直接定位到某个地名上去,因此地图定位功能的实现基本与地图检索一致.

MiniGIS系统专门设计了类KeySearcher来处理地图的检索功能.
KeySeareher首先接收用户交互界面输入的http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c地名关键词信息,然后利用地图数据访问工具类来实现地图的检索.
KeySearcher类的设计及其功能介绍如下:classKeySearcher:publicMGisSearcher{Public:……keyKeySearcher(stringvoidstring):seareh_layer(MCrisLayer*layer);feature(MGisMapFeature+feature);,/搜索地图某层voidsearcheonstKeySearcb.
Result+get_result(intindex)const;get_result__size0const;//搜索结果数constintprotected:stringkey_string:veetorresults://关键字//搜索结果);地图的检索,首先是根据用户界面输入的关键词构造KeySearcher类,然后丫浙江大学硕士毕业论文第三章基于QTE的MiniGIS系统实现利用此类和地图访问工具类搜索相应的地图图层.
在图层检索过程中,通过该类中的searchfeature函数进行关键词和地图图元名称的比较判定,最后将搜索结果保存到ve=ctor容器中去,并将所有结果呈现给用户,用户可以任意选择其中一个进行显示.
地图检索的基本流程如图3.
12所示.

在地图检索开始之前用户除了需要输入关键字之外,用户还可以选择地图数据库中的某一层来搜索,缺省时MiniGIS系统将搜索所有图层.
检索过程中的所有结果都将添加到KeySearcher类的results容器中去,当用户选择其中一个结果显示时,MiniGIS系统将以此结果为中心放大地图,然后标注此结果并在窗口上显示给用户.

I开始1+界面输入关键字7MGisMapLayer::search/,I.
RcsFe—treadi—ng.
lNe构w造Khttp://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228ce搜yS索ea类rcher"jI读取下一个圈元对象j卜一上Nlayer->GetNextFeatureii选择搜索的图层.
缺省为全部.
l比较图元对象名称与搜索关键字实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解.
因此估价值与实际值越接近,估价函数取得就越好.
例如对于几何路网来说,可以取两节点间欧几里德距离(直线距离)做为估价值,即F--G(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))t这样估价函数F在G值一定的情况下,会或多或少地受估价值H的制约,节点距目标点近,H值小,F值相对就小,能保证最短路的搜索向终点的方向进行.
明显优于nijstra算法的毫无方向的向四周搜索【33】.

A算法主要创建两个列表:开启列表(OPEN表)保存所有已经打开生成而未考察的节点,关闭列表(CLOSED表)中记录已访问过(考察过)的节点.
A搜索算法的主要搜索过程如下所示:1):首先把起始结点添加到OPEN列表,初始化各结点的各种代价(F,GH),然后搜索相邻结点,逐步扩大搜索范围;2):重复以下过程:I;寻找开启列表中F值最低的结点.
本文称它为当前结点.
n:然后把它切换到关闭列表.
ⅡI:对相邻的所有结点中的每一个做下列操作:丫浙江大学硕士毕业论文第五章最短路径算法设计幸如果它不可通过或者已经在关闭列表中,略过它.
反之如下.
幸如果它不在开启列表中,把它添加进去.
把当前结点作为这一格的父://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cr节点.
记录这一格的F,G和H值.
}如果它已经在开启列表中,用G值为参考检查新的路径是否更好.
更低的G值意味着更好的路径.
如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值.
如果保持开启列表按F值排序,改变之后可能需要重新对开启列表排序.
Ⅳ;停止,当以下条件满足:,I把目标格添加进了关闭列表,这时候路径被找到,或者幸没有找到目标格,开启列表已经空了.
这时候,路径不存在.
3):如果路径已经被找到则保存路径.
从目标节点开始,沿着每一格的父节点移动直到回到起始格,这就是所寻路径.
A算法早期的做法是当目标格(或节点)被加入到开启列表,而不是关闭列表的时候停止寻路.
这么做会更迅速,而且几乎总是能找到最短的路径,但不是绝对的.
当从倒数第二个节点到最后一个(目标节点)之间的移动耗费悬殊很大时一—例如刚好有一条河穿越两个节点中间,这时候旧的做法和新的做法就会有显著不同.
要使用A,算法必须包含上面讨论的所有元素——特定的开启和关闭列表,用F,G和H作路径评价.
有很多其他的寻路算法,但他们并不是A,A算法被认为是他们当中最好的.
5.
3.
2A算法的优缺点从上述的算法过程分析中可以看出,A算法对Dijkg妇算法进行了改进,增加了终点信息对搜索路径的启发性作用,这样路径的搜索效率得到了大大的提高.
经过测试比较,在其它条件一样的情况下,A+算法的效率要比Dijk觯法的效率高很多倍,特别是对于结点数目较多的时候.

但是与Dijks吮算法一样,如果开启列表(蹦ks仃a算法中是未标记列表)直接采取无序线性表而不进行任何优化,同样会存在严重的效率问题.
因此一般在处理开启列表过程中都保持开启列表以按F值排序,每次要插入一个结点到开启列表,就将该结点插入到适当的位置,仍然保持开启列表的顺序.
这样搜索路径过程中,每次取出最小F值的结点就非常方便,只要取最前面的即可.

1丫浙江大学硕士毕业论文第五章最短路径算法设计开启列表可以数组、链表等多种形式保http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c存.
但是它们各有各的优点,同时也有本身的劣势.
如果采用有序数组保存开启列表,在插入操作的时候,寻找插入位置非常方便,可以采用二分法寻找,效率较高,但是在插入该结点数值时需要移动大量结点,此时效率又比较低.
如果采用链表形式保存开启列表,在插入操作时,要寻找插入位置时,就必须遍历链表来寻找插入位置,此时效率较低,但是在插入该结点数值时,就可以直接断开链表然后插入即可,非常高效.
其实对于开启列表,根本没有必要保持所有结点都按照F值进行排序,只需要保持开启列表中的第一个结点为最小F值的结点即可,而维持其它结点均有序肯定需要更多的开销.
因此针对这种情况,本文提出了一种更优的改进方法,即使用二叉堆来保存开启列表.
二叉堆的特点就是能保持列表的第一个元素为最小值,但是列表里面的其它元素不一定有序,然后能够非常方便的处理结点的插入和删除操作,它结合了数组和链表的优点,减少了不必要的开销,这样又进一步的提高了A搜索算法的效率.
下面将使用二叉堆来优化A.
搜索算法.
5.
3.
3A算法的优化在一个排好序的列表里,每一个节点都有它适当的顺序,从低到高或从高到低.
这很好但是超过了算法的需求.
但是实际上,A算法并不关心列表里节点20是否比21更低,算法真正需要的是F值最小的节点能够在列表的顶部很容易被访问.
列表剩下的部分可以是混乱的,算法不关心.
因此把列表剩余部分也排序是多余的.
因此算法需要这样一个二叉堆,它保存了这样一组结点,它的F值最小或最大(根据需要)的节点在堆的顶部.
由于算法要查找F值最小的节点,所以我们把它放在堆的顶部.
这个节点有2个孩子,每个孩子节点要么F值与它相等,要么就比它大,每个孩子又有2个孩子节点,如此继续.
下图5-4是一个二叉堆示例.
注意,最小的节点12在顶部,第二小的节点2l是它的孩子.
然后就没有任何疑问了.
第三小的节点是25,它在比顶部低2层的位置,比节点31小,它在顶部下一层的左边位置.
简单的放置,并不关心其他节点的值.
只要保证每个节点比他的父亲大或是相等,比他的两个孩子小或是相等就可以了.
这些要求这里都满丫浙江大学硕士毕业论文://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cr足,所以这就是一个二叉堆.
第五章最短路径算法设计图5-4二叉堆示例二叉堆的最大的好处就在于,它可以简单地用一个数组保存它的元素,在这个数组里,二叉堆顶部的节点在数组的第1个位置(IG位置,不是0号位置),它的两个孩子在位置2和3,这两个节点的4个孩子分别在位置4—7.
数组保存的二叉堆如下图5.
5所示:图5-5数组保存的二叉堆从上图可以看出,二叉堆中任一个节点的两个孩子可以通过把它在数组中的位置乘以2(找到第一个孩子)和乘以2再加1(找到第二个孩子)找到.
比如,第3个节点(值为21)的2个孩子在数组里的位置为3*2=6和3*2+l=7.
这些位置的值就是31和25,即第三个结点的两个孩子.

二叉堆的优势就在于它结合了数组寻找插入点的快速性和链表插入结点的快速性,从而大大加快了路径搜索算法的速度.
想象一下系统有一个1000个节点的开放列表,在一个拥有很多节点的地图(100*100个节点的地图就有10000个节点)上这并不是不可能的.
对于链表如果你做一个简单的插入排序,从列表头部开始,直到你找到你可以插入新节点的位置,你平均要做500次的比较;对于简1Irr浙江大学硕士毕业论文第五章最短路径算法设计单数组每次插入时你就平均需要移动500次.
使用二叉堆,从底部开始,你平均只需做1—3次的比较就可以插入到合适的位置.
你也只需平均做9次比较就可以从开启列表移出一个节点并把二叉堆重新排序.
在A算法中,你几乎每一次寻路都要移出一个节点(F值最小的),然后在任意位置添加好几个新节点.
这总共才是在相同数目的节点上作插入排序所花时间的1%.
地图越大差别就越明显.
对于小地图,优势就比较小.
这就是为什么当你使用只有少量节点的小地图时,使用二叉堆并没有多大价值的原因.
下面来看看二叉堆怎样做到这样高效的完成这些添加和删除操作的.

(1)插入新结点添加一个新结点,首先需要把它放在数组的尾部.
然后把它和它的父亲比较,父亲在它的当前位置po眈的位置上,小数部分被取整.
如果新节点的F值小,就把这两节点交换.
再把新节点和它的新父亲比较,http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c同样新父亲位置为新节点当前位置po舵的位置,小数部分被取整,如果F值小,再次进行交换.
重复这个过程,直到新节点不再比它的父亲小,或者新节点到达了二叉堆的项部,也就是数据的第一个位置.

让我们来看看把F值为19的节点添加到二叉堆的情况.
二叉堆中现在已经有7个节点,新节点应该放在8号位置.
现在二叉堆看起来是这样的,新节点用下划线和加粗标志:12312l34393125丝现在把它和它父亲比较,父亲在位置8/2=4上.
4号位置的F值是34,因为19比34dx,所以进行交换操作.
现在二叉堆看起来这样;123l21堡393l2534再把它和新父亲比较.
因为现在它位置是4,所以和位置4/2--2比较.
2号位置F值是31,19比31小,再次交换,现在二叉堆看起来这样:12堡2l3l39312534再把它和父亲比较.
因为现在它在位置2,所以和位置2/2=1比较,这就是堆的顶部.
此时,19比12大,因此停止交换,保持堆的状态不变.
(2)删除结点重排序删除一个结点与添加一个原理基本相似,只不过过程相反.
首先,移出1号位置的节点,此时1号位置空置了,然后把最后一个节点移动到l号位置.
在上面丫浙江大学硕士毕业论文丝1921第五章最短路径算法设计的堆中,这是改变后的结果,之前的最后一个节点用下划线和加粗标志:31393l25下一步,把它和它的两个孩子比较,分别在它当前位置/2和当前位置/2+1的位置上.
如果比它两个孩子的F值都低,就原地不动.
否则就和它F值较低的那个孩子交换.
因此,此时1号位置节点的两个孩子在位置12--2和1'2+1=3的位置上.
34不比两个孩子都小,因此把它和F较小的那个孩子交换,这里是F为19的节点.
结果如下:19丝2l31393l25接着,和它的两个新孩子比较,分别在位置2*2=4和2.
2+1=5上.
它并不比两个孩子都小,再次把它和较小的那个孩子交换,这里是F值为31在4号位置的节点.
结果如下;://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228cpar193121丝393125最后,再和它的两个新孩予比较.
这时,两个孩子的位置为4*2=8和4丰2+l=9,而这两个位置并不存在,因此数据没这么大.
已经到达了堆的底部,所以停止,从而完成结点删除和重新排序操作.
使用二叉堆优化A算法,可以将算法的速度提高2--3倍,如果在更大的地图上(比如100.
100个"节点或更大)速度将会提升更多.
5.
3.
4A算法设计实现本文设计的导航系统最短路径搜索算法是基于使用二叉堆优化的A算法,该算法效率高,运行良好.
下面来分析一下二叉堆优化的A算法实现过程中的问题以及算法运行实现步骤.
在本章的前面的章节,已经为A算法实现奠定了基础.
算法实现时,使用的道路网络拓扑结构即是两个数组(ArcList和NodeList)和一个属性数据表,使用二叉堆来优化算法中的开启列表,同时还要选择估价函数H(n)来进行路径的搜索,最后就是一步步实现"算法.
对于算法的下面来分别讨论这几个关键问题:二叉堆使用,估价函数选择,算法实现步骤.

(1)二叉堆的使用从上一节知道,我们的二叉堆是一个存有F值的列表,但对于道路网络来说,它遗漏了一些重要的东西.
诚然在二叉堆中有一堆F值,但是我们没办法知道他们到底与地图的哪个结点关联.
基本上,现在我们只知道12是二叉堆中F值最小的节点,但是它到底与地图上哪个方格关联呢为了解决这个问题,我们需要改变数组元素的值.
不把F值村在数组里,我们需要保存一个唯一标识符,它可以告诉我们它到底与地图上哪个结点关联.
因此我们在堆中保存了路网中的唯一的结点标识号,然后再保存了该结点的F值.
同时在搜索路径的过程中,我们同样需要G值和H值,因此我们也把G值和H值对应到结点的标号上,最后二叉堆看起来就像图5.
6所示:使用二叉NodeIDFcostGcostHcost7129323115165211011463911183311417125178http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c341222图5-6二叉堆示意图上图看起来好像有点复杂,它其实就是用来优化A.
算法的二叉堆,只是多了一些必要的道路节点信息而已.
NodeID是结点在路网中唯一标号,它拥有最小的F值12,仍然在堆的顶部,在OpenList的第一列.
但是现在我们在二叉堆中保存的是它的ID而不是F值.
也就是说OpenList[1]=7.
这个唯一的ID被用来查找的它的F值、G值和H值,即该节点的F值是Feost[7]=12,ocost[7]=9,Hcost[7]----3.
堆顶部的节点有两个孩子,他们的值是2和5,他们的F值分别是31和2l,分别在OpenList雕J2号位置和3号位置.
如此类推,基本上我们拥有和之前一样的堆,只是多了一些可以告诉我们节点在地图上的位置和节点的F值的信息.
(2)估价函数选择在讨论路网的拓扑结构时,本文使用电子地图数据库生成了NodeList数组来保存和结点有关的信息.
在NodeList之中我们保存了道路结点的投影平面直角坐标,它反应了该结点与终点的位置关系,可以加以利用来选择估价函数H(n).
H(n)是用来估计从该点到终点的最佳代价估计,但是此代价根本没有办法预测,因此我们使用简单的直线距离来进行估计,只是在搜索算法进行时起到一些启发性作用.
由于知道两点的投影平面直角坐标,可以直接使用几何距离公司求出直线距离.
但是有一个问题需要注意,此距离的计算,即是计算估计最佳代价.
每次进行搜索时都需要计算H(n),如果计算H01)非常复杂,将直接导致算法变慢,那么A算法的启发性就不存在任何作用了.
因此如果计算几何直线距离,需要多次乘法,还需要开方运算,这些计算花费太多时间,有必要进行简化.
既然H(n)仅仅是一些启发性作用,我们可以直接使用两直角边距离和,来代表最佳代价估计.
而且因为最短路径一般不太可能为直线,使用两直角边距离和可能还更接近实际值,所以A算法设计时估价函数选择了使用两直角边的距离和来处理.
(3)算法实际运行步骤导航系统路径搜索算法在运行时,首先由用户输入起点位置和终点位置,从而在路网数据结构中得到其实结点和中止结点.
然后以路网数据结构为基础,使用A算法搜索最http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c短路径.
算法运行过程中除了使用到前面介绍的变量ArcList、NodeList、openlist、closclist、Fcost、Gcost、Heost以外,还使用到以下重要变量,WhicList数组代表了一个结点属于哪个列表(开启列表、关闭列表与未考察结点三个中的一个);Parent数组代表了该结点的父结点;A算法实现的基本步骤与其原理的步骤基本相似,流程图如图5-7所示.
5.
4本章小结本章主要介绍了最短路径算法在导航系统中的应用,首先基于城市电子地图,在分析其它路网拓扑结构的基础上提出了一种城市道路网拓扑结构的表示方法,为路径寻优算法的使用奠定了基础.
第二部分主要分析了经典的最短路径搜索算法——Dijkstra算法的基本原理和其在搜索过程中存在的优缺点,为后续改进算法做好了准备.
第三部分是本章的重点,主要讲述了A木算法的原理,分析了其存在的问题,然后针对此问题提出了一种改进算法的方法.
最后介绍了改进的斛算法怎样在嵌1丫浙江大学硕士毕业论文第五章最短路径算法设计入式导航系统中实现,并对Dijkstra算法和A母算法的效率进行了比较.
图5.
7A算法实现流程图一73—第六章总结和展望6.
1总结本文首先介绍了国内和国外导航系统的现状,在国内导航系统逐渐发展起来但是技术不是非常成熟的技术背景下,本课题顺应市场车载嵌入式导航系统的要求,提出了基于QT/Embeded的嵌入式GPS/GIS车载导航系统构架.
导航系统采用了基于ARM9的硬件设计,同时自行设计MiniGIS系统处理电子地图数据库,旨在提供一种低成本、高实用性的车辆导航定位系统.

第三章、第四章、第五章是本文的重点内容.
第三章设计的MiniGIS系统是实现导航系统最基础最关键的部分,它的好坏直接决定了导航系统的性能.
同时MiniGIS系统为以后电子地图在嵌入式Linux上的应用开拓了思路,提供了一种更好更适合的选择.
GUI界面设计的合理性和美观性是系统的容貌,好的容貌更能促进产品的畅销.
最后最短路径算法设计也是导航系统必不可少的部分,它大大地方便了导航系统用户的出行,同http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c时减少了大量的旅行代价.

总之,本文力求做到了嵌入式导航系统应用软件的合理、稳定和可靠.
6.
2展望由于个人能力和时间上面的原因,本文所设计的嵌入式导航系统或多或少地存在着一些问题,今后的工作主要可以在以下方面进行改进:≯MiniGIS系统的完善:MiniGIS系统是导航系统的核心部分,它采用了基于QT/Embedded的嵌入式设计.
虽然该系统在功能上已经基本完备,但是MiniGIS系统的许多模块还需进一步的改进和完善.
≯最短路径算法改进:在最短路径算法方面,本文采用了基于二叉堆的A算法来实现,效率已经比较高,但是仍然存在一些问题,有必要采用更加高效的算法来设计实现.
>系统功能方面:由于ARM9平台本身具有强大的处理能力,针对该平台还可以有更多应用,除了车载导航系统之外,还可利用Linux操作系统开发功能更强的车载多媒体系统,实现娱乐、通讯、导航、防盗监控等一体化集成功能.

参考文献【1】曹晓航.
GPS车载导航系统技术趋势浅析.
现代测绘,2006,29(1):14.
17【2】【3】陈照佳,姚远等.
车载导航终端.
电子车辆技术,2005,(4):57.
58张庆锋,韩飞.
一种基于电子地图的GPS定位技术.
现代电子技术,2005,(17):88-88【4】杨殿阁,p健等.
车载导航系统的研究与实现.
汽车技术,2005,(1):1-4[5】(英)NeilMatthew,RichardStones著.
马修斯通斯译.
Linux程序设计.
机械工业出版社,2001【6】李江,常葆林.
嵌入式操作系统设计中的若干问题.
微型机与应用,2000【刀王田苗.
嵌入式系统设计与实例开发.
清华大学出版社,2002[8】杨玉华.
GPS/电子地图车辆导航系统.
华北工学院硕士学位论文,2004【9】$3C2410XUSER'SMANUAL.
SAMSUANG,2001【10】杜春雷.
ARM体系结构与编程.
清华大学出版http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c社,2002【11】马忠梅.
ARM嵌入式处理器结构与应用基础.
北京航空航天大学出版社,2002【12】范质坚.
LINUX在嵌入式系统中的应用.
计算机与现代化,2000【13】朱江.
GIS系统研制及其在GPS车载导航中的应用.
南京航空航天大学硕士学位论文,2002【14】陆锋,程昌秀等.
Linux环境下的GIS基础平台研发.
地理信息系统,2003,01(6):1216【15】刘云翔.
最短路径分析及GIS/GPS集成技术研究.
国防科学技术大学硕士学位论文,2002【16】OpenGISImplementationSpecification:CoordinateTransformationServicesOpenGeospatialConsortium,lne.
【l7】杨联安,肖蓓.
WebGIS综论.
测绘技术装备,2002,4(2):16-18【18】张小京.
车载导航产品的数字地图格式.
GNSSWorldofChina,2004,(3):6-9【19]Trolltech公司.
Qt-embedded-2.
3.
7参考文档白皮书,2002【20】Xterm(qb国)软件技术有限公司.
Qt程序设计1丫浙江大学硕士毕业论文【21】袁鹏飞译.
24小时学通Qt编程,2000参考文献【22】JasminBlanchettc,MarkSummerfield.
C++GUIProgramming稍mQt3.
PrenticeHallinassociationwithTblltechPress[23】ArthurOriffith.
KDE2/QtProgrammingIndustryBible.
PublishingHouseofElectronics.
【24】于志宏译.
C/C++嵌入式系统编程.
中国电力出版社【25】夏春林,蒋瑞波,宋伟东http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c.
道路路网中最短路径的算法与实现.
辽宁工程技术大学学报,2003,22(2):180—181[26】徐业昌,李树祥,朱建民,许岚,首次华.
基于地理信息系统的最短路径搜索算法.
中国图象图形学报,1998,(1):39-43.
【27】严蔚敏,吴伟民.
数据结构.
北京:清华大学出版社,1997【28】乐阳,龚健雅.
Dijkstra最短路径算法的一种高效实现.
武汉测绘科技大学学报,1999,24(3):209.
212[29】张贵明.
GPS/GIS车辆导航系统中最佳路径算法研究.
四川师范大学学报,2005.
7,28(4):497-500【30】李宁宁,刘玉树.
改进的DDks妇算法在GIs路径规划中的应用.
计算机与现代化,2004,(9):12-14【31】ZMnFB.
ThreeshortestpathalgoritlmrsOnrealroadnetworks.
JournalofGeographicInformationandDecisionAnalysis,2001,l(1):69-82.
【32】潘燕燕,陈自立.
浅淡Dijkstra算法在城市交通最优路径中的应用.
电脑知识与技术,2006【33】李春葆.
GIS中最短路径搜索算法川.
计算机工程与应用,2002(20):7071【34】管素清,刘捷,冷青.
嵌入式车载导航系统的设计.
计算机工程与设计,2005,26(5):1320—1322'甲浙江大学硕士毕业论文发表论文作者在攻读硕士期间发表的论文1.
王国英,杨扬,朱善安.
基于手机平台的双CDMA嵌入式远程监控系统叨.
机电工程,2006.
23(10):36--,38.
1节浙江大学硕士毕业论文'致谢致谢在论文工作完成之际,首先衷心感谢我的导师朱善安教授对课题和论文工作的精心指导.
朱老师在我最迷茫的时候,给我指明了方向,并http://www.
1mpi.
com/doc/c9dd0863e13c960a69f2228c且以自己求真务实的治学精神、渊博的知识、丰富的实践经验和平易近人的态度,使我终身难忘,并将深深影响我以后的工作和学习.
这是我人生路上最宝贵的一笔财富.
在此,谨向朱老师表示最诚挚的感谢和最崇高的敬意.

衷心感谢参与嵌入式车载导航项目的孙志海师兄,孔万增师兄,胡裕峰师兄,黎云汉师兄,刘源等同学,课题凝聚着你们的智慧和工作.
衷心感谢李景师姐认真仔细的帮我修改论文,感谢实验室王金宝,张亚丽,陆晶晶,杨扬,李良,罗小科,叶高翔,王焱等在项目中给予的支持和鼓励,你们的热情帮助才使得论文顺利完成.
祝福你们,以后在自己的领域中取得杰出的成就.

在研究生学习期间得到了朱老师实验室众多师兄师姐们的教诲和师弟师妹们热情的帮助,也得到了电气学院0504硕同班同学的支持和协助,在此一并表示感谢.
祝福他们能有最成功的事业.
此外,我要感谢所有我认识的浙江大学的老师.
六年来,我所取得的成绩也和你们的教诲与指导息息相关.
祝福你们以后生活美满幸福.
最后,我还要感谢我的家人.
在求学十余年来,家人一直在生活上给予我无微不至的关怀,我所取得的点点滴滴与他们在精神和物质上无私的支持是密不可分的.
在这里,我只能用我深深的祝福来表达我的感激之情.

王国英彩叨年5月于浙大求是园[此处图片未下载成功]基于QTE的嵌入式GPS/GIS车载导航系统设计与实现作者:学位授予单位:王国英浙江大学电气工程学院本文链接:http://www.
1mpi.
com/Thesis_Y1213526.
aspx文档下载网是专业的免费文档搜索与下载网站,提供行业资料,考试资料,教学课件,学术论文,技术资料,研究报告,工作范文,资格考试,word文档,专业文献,应用文书,行业论文等文档搜索与文档下载,是您文档写作和查找参考资料的必备网站.