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
shortest, or find, among all noncrossing paths with a minimum total length... in collisionfree rectilinear paths in the presence of rectilinear obstacles. ...
Given n points in the plane and a positive integer k, the Rectilinear k-Bends Traveling Salesman Problem asks if there is a piecewise linear tour ...
Plane E 2 , the Rectilinear Minimum Steiner Arborescence (RMSA) problem is to nd a shortest-path tree of the minimum length rooted at the origin, ...
Worst-Case Ratios of Networks in the Rectilinear Plane Ulrich Brenner Jens...We compare the length of a minimum spanning tree and a shortest Steiner ...
scheme (PTAS) for the rectilinear Steiner arborescence problem in the plane....paths from the source to any sink are shortest paths with respect to the...
found an algorithm for the rectilinear 2-center problem in the plane with...Shortest connection networks and some generalizations. Bell Syst. Tech. J.,...
Optimal Rectilinear Steiner Tree Routing in the Presence of Obstacles Joseph L. Ganley and James P. Cohoon Department of Computer Science University of ...
FORSTer An Efficient Heuristic for Obstacle-Avoiding Rectilinear Steiner Tree ...Moreover, it can tackle large scale nets among complex obstacles, such as...
Optimal rectilinear stei... 暂无评价 11页 免费 Implicitization of surfa..... Connecting Points in the Presence of Obstacles in the Plane Given a point...
Given a set of disjoint rectilinear line segments in the plane. For a horizontal segment s, there are exactly 3 ways to place a rectangle. 1. s is...
热门文档