文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane
侵权投诉

k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane

We present an algorithm for computing k-link rectilinear shortest paths among rectilinear obstacles in the plane. We extend the “continuous Dijkstra ” paradigm to store the link distance information associated with each propagating “wavefront”. Our alg

ofwavefrontscorrectly,thefollowinginformationasso-ciatedwitheachsegmentofthewavefrontisstoredinapriorityqueue(calledtheeventqueue):

(a).itsorientation,whichwillalwaysbeeithernorth-west(NW),southwest(SW),southeast(SE)ornorth-east(NE)inthecaseoftheL1metric;

(b).itsendpointsqandq ,whicharethepositionsofthesegment’sendpointsatthemomentthesegmentis rstinstantiated,beforeitstartsbeing“dragged”;

(c).itsleftandrighttrackrays—thesearetheraysalongwhichqandq mustbedragged,andtheymaybehorizontalorverticalraysthroughfreespaceorrayscontainingobstacleedges;

(d).thestoppointsLandRoftheleftandrighttrackrays—thesearethe rstobstaclepoints“hit”bytheleftandrighttrackrays.(Ifthetrackraysintersecteachotheratpointubeforetheyhitobstacles,thenL=R=u,whereuistheinsidecornerofthecorrespondingsegmentdraggingquery.);

(e).itsrootr,whichisanobstaclevertexthatisresponsibleforpropagatingtheportionofthewavefronttowhichthesegmentbelongs;

(f).itscontactlist,whichisthesetofobstacleedgesthatthedraggedsegmenttouches(includingtheobsta-cleedgesonwhichitsendpointsmaybesliding);

,whichisthenextposition(g).itseventpositionqeqe

ofthesegmentatwhichthecontactlistchanges;

(h).itseventpointp,whichisthepointthatisre-sponsibleforthechangeinthecontactlistwhenthesegmentreachesitseventposition.Theeventpointpmustlieontheboundaryofanobstacle,anditwilleitherbeastoppointoravertex;

(i).theeventdistance,whichisthedistancefromsatwhichtheeventpointisencounteredbythesegment.Thesegmentsintheeventqueueareorderedaccord-ingtotheireventdistances.Thenexteventisthedraggedsegmentwhoseeventdistanceisminimumandisobtainedbypoppingthequeue.Inthecaseofties,wecanordertheeventdistancesbythelexicographicorderingofthex-andy-coordinatesoftheirroots.Eachobstaclevertexuhasassociatedwithitasortedlist,theSE-hitlist,RSE(u)={r1,...,rN}ofrootsriofdraggedsegmentsthataresoutheastofuandaresuchthatthedraggedsegmenthas“hit”pointu(i.e.,uhasbeenaneventpointforadraggedsegmentrootedatri,andthiseventhasalreadyoccurred).Similarde nitionsapplytothehitlistsRNE(u),RNW(u),andRSW(u)oftherootsofthesegmentswhichhavehitufromsouthwest,southeastandnortheastrespectively.ThetotalsizeofalllistsisboundedabovebyO(nlogn).Alsoassociatedwitheachobstaclevertexuisaper-manentlabel,d(u),which,attheconclusionoftheal-gorithm,givesthelength (s,u)ofshortestpathfromstou.Initially,d(u)=+∞forallu.Wesaythatuhasbeenpermanentlylabeledifd(u)<+∞.Wesay

thatanon-vertexpointxhasbeenpermanentlyla-beledifitliesintheregionsweptoutbysomedraggedsegment.Eachvertexualsohasapointer,parent(u),which,attheconclusionofthealgorithm,pointstotheparentofuintheshortestpathtreeSPT(s).Initially,parent(u)=NIL.

Therearethreetypesofevents:

(I).theeventpointpisoneofthestoppoints;

(II).pisinteriortothedraggedsegmentinitseventposition;and,

(III).pisavertexencounteredbyanendpointofthedraggedsegment.

Theeventqueueisupdatedateacheventsoastosim-ulatethewavefrontpropagationcorrectly.DeterminingeventsinthecontinuousDijkstramethodinvolvesan-sweringsegmentdraggingqueriesofspecialforms;see[9]fordetails.

Modi cationstoaccountforlinkdistance.Inordertomodifytheabovealgorithmforthek-linkpathprob-lem,weextendthecontinuousDijkstraalgorithmtostorethe(rectilinear)linkdistancefromstoanypointuonthewavefront.Inparticular,wedistinguishbetweens-upathsendingwithaverticallinkands-upathsend-ingwithahorizontallink.Tothisendweassociatewitheachwavefrontsegmentoneortwoadditionalsegments:ahorizontalsegment,calledav-sourceand/oraverti-calsegment,calledanh-source.Witheachv-sourcevwestoreitslinknumber,l.v,whichisthelinkdis-tancefromstov,andpointertoapredecessorh-source,pred.v.Thentheshortest(l.v+1)-links-upathwithlastlinkverticalmaygofromsthroughpred.vtovandthentou.Westoresimilarinformationwitheachoftheh-sources.RefertoFigure1.

Righttrack

  h-sourceroot

Lefttrack

 v-source

Figure1:Theinformationassociatedwithawavefrontsegment.

Eachobstaclevertexuhasnowassociatedwithitk

SE

SE-hitlists.Forj∈{1...k},thehitlistjR(u)con-tainstherootsandsourcesofdraggedsegmentsthataresoutheastofuandaresuchthatthedraggedsegmenthas“hit”pointuandthelinkdistancefromstothesourceislessthanj.(Clearly,1RSE(u) 2RSE(u) ··· kRSE(u),soweonlystorethecorrespondingsetdi erences).Wesimilarlyde nehitlistsforotherhitdirections.

Initially,sispermanentlylabeledwith0.Four

2

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email