基于OpenStreetMap最短路径算法的分析与实现

2013－02－062013－05－122013－08－28KJ20121971988－、、。http//．cnki．net/kcms/detail/61．1450．TP．20130828．0829．016．htmlOpenStreetMap710077、、。OSMDijkstra。OSMOSMDijkstra。TP301．6A1673－629X201311－0037－05doi10．3969/j．issn．1673－629X．2013．11．010AnalysisandImplementationofShortestPathAlgorithmBasedonOpenStreetMapZHANGYing－huiZHANGShui－pingZHANGFeng－qinWANGＲongCollegeofInformationandNavigationUniversityofAirForceEngineeringXi’an710077ChinaAbstractWiththerapiddevelopmentofcomputernetworkandGIStechnologytheshortestpathproblemplaysanimportantroleintransportationcityplanninglogisticsmanagementnetworkcommunicationetc．FocusondescribinghowtouseDijkstraalgorithmtocal-culatetheshortestpathbetweentwoconnectednodesbasedonOSM．FirstlyintroducethecharacteristicsofOSManddatastructureofroadimagefeature．SecondlyextractroadinformationbyregularexpressionfromOSMdatafileandstoretheminappropriateconstruc-tion．FinallyformroadtopologicaldiagramandtakesthegeographicaldistanceasroadweightcalculatingtheshortestpathbetweentwoconnectednodesbyDijkstraalgorithm．KeywordsshortestpathalgorithmOSMGISregularexpression0GeographicInformationSystemGIS、、、、。GIS、。1GIS。Dijk-stra2。1OSMOpenStreetMapOSM34。GISGPS、OSM5、、。OSM2311201311COMPUTEＲTECHNOLOGYANDDEVELOPMENTVol．23No．11Nov．2013。6。OSM。1．1OSMOSM。OSM。XML．osmOpenStreetMap。OSM1JOSM。JOSMJavaOpenStreetMapOSM。7。。2HTTP。OSMAPI8UＲLOSMhttp//api．openstreet-map．org/api/0．6/mapbbox=11．5448．1411．54348．145bbox、、、。UＲLOSM。3OSM。OSMOpenStreetMapOs-mosisplanetoasm。4OSM。OpenStreetMap。CloudmadOSM。1．2OSMOSMxmlxmlosm8。、。OSM9NodeWay。1Node。Node。nametag。NodeXML。＜osmversion=0．6generator=OpenStreetMapserver＞＜nodeid=483034256lat=55．9458449lon=－3．2035477version=1changeset=2369219user=spytfyreuid=166957visible=truetimestamp=2009－09－04T133542Z＞＜tagk=namev=TheBlueBlazer/＞＜tagk=amenityv=pub/＞＜/node＞＜/osm＞2Way。Way2～2000nodesWay3、、。2000nodesWay。＜osmversion=0．6generator=OpenStreetMapserver＞＜wayid=43157302visible=truetimestamp=2009－10－26T104509Zversion=1changeset=2954960user=EdAvisuid=31257＞＜ndref=540653724/＞＜ndref=25507043/＞＜ndref=107762/＞＜ndref=25507038/＞＜ndref=107759/＞＜tagk=highwayv=primary/＞＜tagk=lcn_refv=6a/＞＜tagk=namev=ParliamentStreet/＞＜/way＞＜/osm＞NoderefNodeID。1．3OSMOSMWaytag“highway”Key“highway”Value“primary”、“motorway”、“trunk”、“track”。、、、。“nd”WayNodes“ref”NodesNodeIDNodeID。10OSMNodeIDOSM11。·83·23classPointGeo//publicdoublelatpublicdoublelngclassLineInfor//publicPointGeoBeginpublicPointGeoEnd//privateHashtableDecodeNodesstringxmlMapDataMatchCollectionMatchesMatchItemHashtablehsNodes=newHashtableMatches=Ｒegex．MatchesxmlMapData＜node\\s|\\S|．*＞\\s|\\S|．*＜/node＞ＲegexOptions．Ignore-Case|ＲegexOptions．ExplicitCaptureforeachMatchiteminMatchesPointGeonode=newPointGeoMatchItem=Ｒegex．Matchesitem．ToStringid=\＜NodeId＞\\d*\*lat=\＜lat＞\\d|\\．*\*lon=\＜lon＞－|\\d|．*ＲegexOptions．Ignore-Case|ＲegexOptions．ExplicitCaptureifMatchItem==null||MatchItem．Count＜=0continuestringNodeId=MatchItem0．GroupsNodeId．To-Stringnode．lat=double．ParseMatchItem0．Groupslat．ToStringnode．lng=double．ParseMatchItem0．Groupslon．ToStringhsNodes．AddNodeIdnodereturnhsNodes//privateList＜LineInfor＞DecodeLinesstringxmlMapDataHashtablehsNodesMatchCollectionMatchesNodesListList＜LineInfor＞lstLines=newList＜LineInfor＞Matches=Ｒegex．MatchesxmlMapData＜way\\s|\\S|．*＞\\s|\\S|．*＜/way＞ＲegexOptions．Ignore-Case|ＲegexOptions．ExplicitCaptureforeachMatchiteminMatchesNodesList=Ｒegex．Matchesitem．ToString＜ndref=\＜NodeId＞\\d*\/＞ＲegexOptions．Ignore-Case|ＲegexOptions．ExplicitCaptureforeachMatchnodeinNodesListboolBegin=trueLineInforobjLine=newLineInforobjLine．Begin=newPointGeoobjLine．End=newPointGeostringNodeId=node．GroupsNodeId．ToStringifBegin==trueobjLine．Begin．lng=PointGeohsNodesNo-deId．lng/100000objLine．Begin．lat=PointGeohsNodesNo-deId．lat/100000Begin=falseelseobjLine．End．lng=PointGeohsNodesNo-deId．lng/100000objLine．End．lat=PointGeohsNodesNo-deId．lat/100000lstLines．AddobjLineobjLine．Begin．lng=PointGeohsNodesNo-deId．lng/100000objLine．Begin．lat=PointGeohsNodesNo-deId．lat/100000returnlstLines2DijkstraDijkstra。Di-jkstra12。Dijkstra131DDi2VSVS。SV3path_matrix。1V、SarcsD∞2DDii·93·11OpenStreetMapS=S∪iiS3iDV－SkDi+arcsik＜DkDk=Di+arcsik42、3V。3Dijkstra1。OSM14。15。。。privatevoidPrepareNodeMatrixdoubleＲightValueradLat1radLat2b_NodesMatrix=newdouble_lstLines．Count_lstLines．Countforinti=0i＜_NodesMatrix．GetLength0i++forintj=0j＜_NodesMatrix．GetLength1j++_NodesMatrixij=double．MaxValueforinti=0i＜_lstLines．Counti++radLat1=_lstLinesi．Begin．lat*Math．PI/180.0radLat2=_lstLinesi．End．lat*Math．PI/180．0b=_lstLinesi．Begin．lng*Math．PI/180．0－_lstLinesi．End．lng*Math．PI/180．0ＲightValue=2*Math．AsinMath．SqrtMath．PowMath．SinradLat1－radLat2/22+Math．CosradLat1*Math．CosradLat2*Math．PowMath．Sinb/22ＲightValue=Math．ＲoundＲightValue*63781370*10000/10000_NodesMatrixii+1=ＲightValue_NodesMatrixi+1i=ＲightValue_UnVisitedPath．Addi2。intGetMinWayIndexint_Psdoublemin=double．MaxValueintMinIdx=－1nodeIndexforinti=0i＜_UnVisitedPath．Counti++nodeIndex=int_UnVisitedPathiifmin＞_NodesMatrix_PsnodeIndexmin=_NodesMatrix_PsnodeIndexMinIdx=ireturnMinIdx3。publicstringFindWayintidxnodeIdxtmp