/* Ċ Ġ* ĠCopyright Ġ( C ) Ġ 2 0 1 0 - 2 0 2 0 , ĠD ani lo ĠP ian ini Ġand Ġcontributors Ċ Ġ* Ġlisted Ġin Ġthe Ġmain Ġproject 's Ġal che mist / build . gradle . k ts Ġfile . Ċ Ġ* Ċ Ġ* ĠThis Ġfile Ġis Ġpart Ġof ĠAl che mist , Ġand Ġis Ġdistributed Ġunder Ġthe Ġterms Ġof Ġthe Ċ Ġ* ĠGNU ĠGeneral ĠPublic ĠLicense , Ġwith Ġa Ġlinking Ġexception , Ċ Ġ* Ġas Ġdescribed Ġin Ġthe Ġfile ĠLICENSE Ġin Ġthe ĠAl che mist Ġdistribution 's Ġtop Ġdirectory . Ċ Ġ*/ Ċ Ċ package Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . navigator Ċ Ċ import Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . A wt Mutable Convex Polygon Ċ import Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . A wt Shape Extension . vertices Ċ import Ġit . uni bo . al che mist . model . implement ations . geometry . e uclidean 2 d . Segment 2 DI mpl Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . e uclidean 2 d . Intersection 2 D Ċ import Ġit . uni bo . al che mist . model . implement ations . positions . E uclidean 2 D Position Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Vector 2 D Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . Vector 2 D . Companion . z Cross Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . e uclidean 2 d . Convex Polygon Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . e uclidean 2 d . Segment 2 D Ċ import Ġit . uni bo . al che mist . model . interfaces . geometry . e uclidean 2 d . navigator . Extend able Convex Polygon Ċ import Ġjava . awt . Shape Ċ import Ġjava . awt . geom . Point 2 D Ċ import Ġjava . awt . geom . Line 2 D Ċ import Ġjava . lang . IllegalStateException Ċ Ċ /** Ċ Ġ* ĠAn Ġ[ Extend able Convex Polygon ] Ġlocated Ġinside Ġan Ġenvironment Ġwith Ġob stacles . Ċ Ġ* ĠOb stacles , Ġas Ġwell Ġas Ġthe Ġenvironment 's Ġboundaries , Ġare Ġtaken Ġinto Ġaccount Ġwhen Ġthe Ġpolygon Ġis Ċ Ġ* Ġextended Ġ( i . e . Ġthe Ġpolygon Ġis Ġprevent ed Ġfrom Ġintersect ing Ġan Ġobstacle Ġor Ġgrowing Ġbeyond Ġsuch Ċ Ġ* Ġboundaries ). Ċ Ġ* ĠA Ġrect angular Ġregion Ġis Ġassumed , Ġits Ġ[ origin ], Ġ[ width ] Ġand Ġ[ height ] Ġare Ġto Ġbe Ġspecified . ĠBoth Ċ Ġ* Ġ[ java . awt . Shape ] s Ġand Ġ[ Convex Polygon ] s Ġcan Ġbe Ġspecified Ġas Ġob stacles Ġ( see Ġ[ awt Ob stacles ] Ċ Ġ* Ġand Ġ[ polygon al Ob stacles ]). Ċ Ġ* ĠThis Ġclass Ġis Ġexplicitly Ġdesigned Ġfor Ġthe Ġalgorithm Ġcontained Ġin Ġ[ generate Navigation Graph ]. Ċ Ġ* ĠTODO ( impro ve Ġthe Ġquality Ġof Ġthis Ġclass ) Ċ Ġ*/ Ċ class ĠExtend able Convex Polygon In Environment ( ĊĠĠĠ Ġprivate Ġval Ġvertices : ĠMutable List < E uclidean 2 D Position >, ĊĠĠĠ Ġprivate Ġval Ġorigin : ĠE uclidean 2 D Position , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠWidth Ġof Ġthe Ġenvironment Ġ( only Ġpositive ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġwidth : ĠDouble , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠHeight Ġof Ġthe Ġenvironment Ġ( only Ġpositive ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġheight : ĠDouble , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠOb stacles Ġrepresented Ġas Ġ[ java . awt . Shape ] s , Ġare Ġassumed Ġto Ġbe Ġimmutable Ġand Ġmust Ġbe Ġpoly gons ĊĠĠĠĠ Ġ* Ġ( i . e . Ġshapes Ġwithout Ġcur ved Ġsegments ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġa wt Ob stacles : ĠList < Shape > Ċ ) Ġ: ĠA wt Mutable Convex Polygon ( vertices ), ĠExtend able Convex Polygon Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠOb stacles Ġrepresented Ġas Ġ[ Convex Polygon ] s , Ġare Ġassumed Ġto Ġbe Ġmutable Ġbut Ġlimited Ġto Ġthe Ġextension ĊĠĠĠĠ Ġ* Ġ( i . e . Ġthey Ġcan Ġonly Ġgrow , Ġnot Ġshrink ). ĠThis Ġis Ġthe Ġbehavior Ġof Ġseeds Ġused Ġby Ġ[ generate Navigation Graph ], ĊĠĠĠĠ Ġ* Ġmaking Ġthis Ġassumption Ġallows Ġto Ġcache Ġuseful Ġdata Ġsuch Ġas Ġwhether Ġan Ġedge Ġcan Ġstill Ġadvance Ġor ĊĠĠĠĠ Ġ* Ġan Ġobstacle Ġhas Ġalready Ġbeen Ġencountered . ĠThis Ġis Ġa Ġvar Ġbut Ġis Ġassumed Ġto Ġbe Ġset Ġonly Ġonce Ġbefore ĊĠĠĠĠ Ġ* Ġstarting Ġto Ġextend Ġthis Ġpolygon . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġlateinit Ġvar Ġpolygon al Ob stacles : ĠList < Convex Polygon > ĊĊĠĠĠ Ġprivate Ġvar Ġcan Edge Advance : ĠMutable List < Boolean > Ġ= ĠMutable List ( vertices . size ) Ġ{ Ġtrue Ġ} ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCache s Ġthe Ġnormal Ġvers or Ġto Ġeach Ġedge . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġvar Ġnormals : ĠMutable List < E uclidean 2 D Position ?> Ġ= ĠMutable List ( vertices . size ) Ġ{ Ġnull Ġ} ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCache s Ġthe Ġgrowth Ġdirection Ġ( a Ġvector ) Ġof Ġboth Ġthe Ġvertices Ġof Ġeach Ġedge , Ġthis Ġis Ġuseful Ġin ĊĠĠĠĠ Ġ* Ġthe Ġadvanced Ġcase Ġ( see Ġ[ extend ]). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġvar Ġgrowth Directions : ĠMutable List < Pair < E uclidean 2 D Position ?, ĠE uclidean 2 D Position ?> ?> Ġ= ĊĠĠĠĠĠĠĠ ĠMutable List ( vertices . size ) Ġ{ Ġnull Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġadd Vertex ( index : ĠInt , Ġx : ĠDouble , Ġy : ĠDouble ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Edge Ġ= Ġget Edge ( circular Previous ( index )) ĊĠĠĠĠĠĠĠ Ġif Ġ( super . add Vertex ( index , Ġx , Ġy )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Cache At ( index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvoid Cache At ( circular Previous ( index ), Ġold Edge ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove Vertex ( index : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Edge Ġ= Ġget Edge ( circular Previous ( index )) ĊĠĠĠĠĠĠĠ Ġif Ġ( super . remove Vertex ( index )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove Cache At ( index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvoid Cache At ( circular Previous ( index ), Ġold Edge ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġmove Vertex ( index : ĠInt , Ġnew X : ĠDouble , Ġnew Y : ĠDouble ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmodified Edges Ġ= ĠlistOf ( circular Previous ( index ), Ġindex ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġit Ġto Ġget Edge ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( super . move Vertex ( index , Ġnew X , Ġnew Y )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmodified Edges . forEach Ġ{ Ġvoid Cache At ( it . first , Ġit . second ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġreplace Edge ( index : ĠInt , Ġnew Edge : ĠSegment 2 D < E uclidean 2 D Position >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmodified Edges Ġ= ĠlistOf ( circular Previous ( index ), Ġindex , Ġcircular Next ( index )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġit Ġto Ġget Edge ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( super . replace Edge ( index , Ġnew Edge )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmodified Edges . forEach Ġ{ Ġvoid Cache At ( it . first , Ġit . second ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġcache Ġis Ġset Ġto Ġsome Ġdefault Ġvalue , Ġthe Ġsame Ġit Ġassumes Ġwhen Ġit 's Ġvo ided . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġadd Cache At ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġcan Edge Advance . add ( index , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġgrowth Directions . add ( index , Ġnull ) ĊĠĠĠĠĠĠĠ Ġnormals . add ( index , Ġnull ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġremove Cache At ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġcan Edge Advance . remove At ( index ) ĊĠĠĠĠĠĠĠ Ġgrowth Directions . remove At ( index ) ĊĠĠĠĠĠĠĠ Ġnormals . remove At ( index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUsually Ġcache Ġrelated Ġto Ġan Ġedge Ġis Ġvo ided Ġwhen Ġthe Ġedge Ġis Ġsomehow Ġmodified . ĠHowever , Ġdifferent ĊĠĠĠĠ Ġ* Ġcaches Ġmay Ġapply Ġdifferent Ġpolicies Ġfor Ġvoid ing Ġ( e . g . Ġa Ġcache Ġmem oriz ing Ġthe Ġnormal Ġof Ġeach Ġedge ĊĠĠĠĠ Ġ* Ġis Ġto Ġbe Ġvo ided Ġif Ġthe Ġslope Ġof Ġthe Ġedge Ġchanges ). ĠThis Ġmethod Ġaccepts Ġthe Ġindex Ġof Ġa Ġmodified Ġedge ĊĠĠĠĠ Ġ* Ġand Ġthe Ġold Ġedge Ġand Ġapplies Ġdifferent Ġpolicies Ġto Ġdecide Ġif Ġeach Ġcache Ġshould Ġbe Ġvo ided . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġvoid Cache At ( index : ĠInt , Ġold : ĠSegment 2 D < E uclidean 2 D Position >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnew Ġ= Ġget Edge ( index ) ĊĠĠĠĠĠĠĠ Ġcan Edge Advance [ index ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġif Ġ(! old . is Parallel To ( new ) Ġ&& Ġ!( old . is De generate Ġ|| Ġnew . is De generate )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ index ] Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnormals [ index ] Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdv ances Ġan Ġedge Ġin Ġits Ġnormal Ġdirection Ġof Ġa Ġquantity Ġequal Ġto Ġ[ step ], Ġif Ġ[ extend ] Ġhas ĊĠĠĠĠ Ġ* Ġmodified Ġthe Ġgrowth Ġdirection Ġof Ġthe Ġedge Ġso Ġas Ġto Ġfollow Ġan Ġob lique Ġobstacle Ġ( advanced Ġcase ), ĊĠĠĠĠ Ġ* Ġthe Ġmodified Ġgrowth Ġdirection Ġis Ġused . ĊĠĠĠĠ Ġ* ĠThe Ġpolygon Ġis Ġprevent ed Ġfrom Ġgrowing Ġout Ġof Ġthe Ġenvironment 's Ġboundaries , Ġbut Ġnot Ġfrom ĊĠĠĠĠ Ġ* Ġintersect ing Ġob stacles . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠNote Ġthat Ġeven Ġwhen Ġgrowth Ġdirection Ġis Ġmodified Ġthe Ġedge Ġstill Ġadv ances Ġin Ġits Ġnormal Ġdirection . ĊĠĠĠĠ Ġ* ĠWhat Ġhas Ġbeen Ġmodified Ġare Ġthe Ġindividual Ġgrowth Ġdirections Ġof Ġits Ġendpoints , Ġwhich Ġmeans Ġits ĊĠĠĠĠ Ġ* Ġslope Ġwill Ġbe Ġpreserved Ġbut Ġnot Ġits Ġlength . ĊĠĠĠĠ Ġ* ĠIn Ġorder Ġto Ġguarantee Ġthat Ġthe Ġadvanced Ġedge Ġis Ġalways Ġparallel Ġto Ġthe Ġold Ġone Ġ( i . e . Ġthat Ġthe ĊĠĠĠĠ Ġ* Ġedge Ġactually Ġadvance Ġin Ġits Ġnormal Ġdirection ), Ġwe Ġneed Ġto Ġresize Ġthe Ġdirections Ġof Ġgrowth ĊĠĠĠĠ Ġ* Ġof Ġthe Ġendpoints Ġso Ġthat Ġtheir Ġcomponent Ġin Ġthe Ġdirection Ġnormal Ġto Ġthe Ġedge Ġis Ġequal Ġto Ġstep . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġadvance Edge ( index : ĠInt , Ġstep : ĠDouble ): ĠBoolean Ġ= Ġtrue . take If Ġ{ Ġstep Ġ== Ġ 0 . 0 Ġ} Ġ?: Ġrun Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġget Edge ( index ) ĊĠĠĠĠĠĠĠ Ġif Ġ( edge . is De generate ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( normals [ index ] Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnormals [ index ] Ġ= Ġcompute Normal ( index , Ġedge ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġnormal Ġ= Ġnormals [ index ] Ġ?: Ġthrow ĠIllegalStateException (" internal Ġerror : Ġno Ġnormal Ġfound ") ĊĠĠĠĠĠĠĠ Ġcache Grow th Direction ( index , Ġnormal ) ĊĠĠĠĠĠĠĠ Ġval Ġto Movement Vector : Ġ( E uclidean 2 D Position ?). () Ġ-> ĠE uclidean 2 D Position Ġ= Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlength Ġ= Ġfind Length ( it , Ġnormal , Ġstep ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrequire ( length . is Finite ()) Ġ{ Ġ" internal Ġerror : Ġinvalid Ġlength " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . res ized ( length ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġ?: Ġthrow ĠIllegalStateException (" internal Ġerror : Ġno Ġgrowth Ġdirection Ġfound ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġfirst Movement Ġ= Ġgrowth Directions [ index ]?. first . to Movement Vector () ĊĠĠĠĠĠĠĠ Ġval Ġsecond Movement Ġ= Ġgrowth Directions [ index ]?. second . to Movement Vector () ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* Ġsuper Ġmethod Ġis Ġused Ġin Ġorder Ġto Ġavoid Ġvoid ing Ġuseful Ġcache ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġif Ġ( super . replace Edge ( index , Ġedge . copy With ( edge . first Ġ+ Ġfirst Movement , Ġedge . second Ġ+ Ġsecond Movement ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( get Edge ( index ). isIn Rectangle ( origin , Ġwidth , Ġheight )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsuper . replace Edge ( index , Ġedge ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠComputes Ġthe Ġnormal Ġvector Ġto Ġthe Ġspecified Ġedge , Ġtaking Ġcare Ġthat Ġits Ġver se Ġallows Ġto Ġextend ĊĠĠĠĠ Ġ* Ġthe Ġpolygon Ġand Ġnot Ġshrink Ġit Ġ( this Ġis Ġall Ġabout Ġfig uring Ġout Ġin Ġwhich Ġver se Ġthe Ġpolygon Ġextends ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġcompute Normal ( index : ĠInt , Ġedge : ĠSegment 2 D < E uclidean 2 D Position > Ġ= Ġget Edge ( index )): ĠE uclidean 2 D Position Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcurr Ġ= Ġedge . to Vector ĊĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġget Edge ( circular Previous ( index )). to Vector ĊĠĠĠĠĠĠĠ Ġval Ġnormal Ġ= Ġcurr . normal (). normalized () ĊĠĠĠĠĠĠĠ Ġif Ġ( z Cross ( curr , Ġnormal ) Ġ> Ġ 0 . 0 Ġ!= Ġz Cross ( curr , Ġprev ) Ġ> Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnormal Ġ* Ġ- 1 . 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnormal ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCache s Ġthe Ġgrowth Ġdirections Ġof Ġboth Ġthe Ġvertices Ġof Ġthe Ġspecified Ġedge Ġif Ġthey 're Ġnot Ġcached Ġyet . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġcache Grow th Direction ( index : ĠInt , Ġnormal : ĠE uclidean 2 D Position ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġgrowth Direction Ġ= Ġgrowth Directions [ index ] ĊĠĠĠĠĠĠĠ Ġif Ġ( growth Direction ?. first Ġ== Ġnull Ġ|| Ġgrowth Direction . second Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( growth Direction Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ index ] Ġ= ĠPair ( normal , Ġnormal ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( growth Direction . first Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ index ] Ġ= Ġgrowth Direction . copy ( first Ġ= Ġnormal ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( growth Direction . second Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ index ] Ġ= Ġgrowth Direction . copy ( second Ġ= Ġnormal ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGiven Ġa Ġvector Ġa , Ġwe Ġwant Ġto Ġresize Ġit Ġso Ġthat Ġits Ġscalar Ġprojection Ġon Ġa Ġsecond Ġvector Ġb ĊĠĠĠĠ Ġ* Ġis Ġequal Ġto Ġa Ġcertain Ġquantity Ġq . ĠIn Ġorder Ġto Ġdo Ġso , Ġwe Ġneed Ġto Ġknow Ġthe Ġlength Ġof Ġthe Ġnew ĊĠĠĠĠ Ġ* Ġvector Ġa '. ĠThis Ġmethod Ġcomputes Ġthat Ġquantity . Ġ[ b Unit ] Ġis Ġb Ġof Ġunit ary Ġmagnitude . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfind Length ( a : ĠE uclidean 2 D Position , Ġb Unit : ĠE uclidean 2 D Position , Ġq : ĠDouble ) Ġ= Ġq Ġ/ Ġa . dot ( b Unit ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠExt ends Ġthe Ġpolygon Ġin Ġeach Ġdirection Ġof Ġa Ġquantity Ġequal Ġto Ġ[ step ]. ĊĠĠĠĠ Ġ* ĠThe Ġadvance ment Ġof Ġan Ġedge Ġis Ġblocked Ġif Ġan Ġobstacle Ġis Ġintersect ed , Ġunless Ġin Ġa ĊĠĠĠĠ Ġ* Ġparticular Ġcase Ġcalled Ġadvanced Ġcase . ĠSuch Ġcase Ġshows Ġup Ġwhen Ġa Ġsingle Ġvertex Ġof ĊĠĠĠĠ Ġ* Ġthe Ġpolygon Ġintr ude d Ġan Ġobstacle , Ġbut Ġno Ġvertex Ġfrom Ġthe Ġobstacle Ġintr ude d Ġthe Ġpolygon . ĊĠĠĠĠ Ġ* ĠPlus , Ġthe Ġintr ude d Ġside Ġof Ġthe Ġobstacle Ġshould Ġbe Ġob lique Ġ( or Ġbetter , Ġits Ġslope Ġshould ĊĠĠĠĠ Ġ* Ġbe Ġdifferent Ġfrom Ġthe Ġone Ġof Ġthe Ġadv ancing Ġedge ). ĊĠĠĠĠ Ġ* ĠWhen Ġthis Ġhappens , Ġwe Ġcan Ġdo Ġa Ġsimple Ġoperation Ġin Ġorder Ġto Ġkeep Ġgrowing Ġand Ġallow Ġa ĊĠĠĠĠ Ġ* Ġhigher Ġcoverage Ġof Ġthe Ġwalk able Ġarea . ĠWe Ġincrement Ġthe Ġorder Ġof Ġthe Ġpolygon Ġ( by Ġadding ĊĠĠĠĠ Ġ* Ġa Ġvertex ) Ġand Ġadjust Ġthe Ġdirection Ġof Ġgrowth Ġin Ġorder Ġfor Ġthe Ġnew Ġedge Ġto Ġfollow Ġthe ĊĠĠĠĠ Ġ* Ġside Ġof Ġthe Ġobstacle . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġextend ( step : ĠDouble ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġob stacles Ġ= Ġa wt Ob stacles Ġ+ Ġpolygon al Ob stacles . map Ġ{ Ġit . as A wt Shape () Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġextended Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġvertices . indices . filter Ġ{ Ġcan Edge Advance [ it ] Ġ}. forEach Ġ{ Ġi Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhas Advanced Ġ= Ġadvance Edge ( i , Ġstep ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġintersect ed Obs Ġ= Ġob stacles . filter Ġ{ Ġintersect s ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ* ĠReturns Ġtrue Ġif Ġno Ġobstacle Ġis Ġintersect ed Ġor Ġif Ġwe Ġare Ġin Ġthe Ġadvanced Ġcase . ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġis Advanced Case : Ġ() Ġ-> ĠBoolean Ġ= Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ* ĠCan Ġbe Ġin Ġthe Ġadvanced Ġcase Ġfor Ġat Ġmost Ġ 2 Ġob stacles . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġintersect ed Obs . size Ġ<= Ġ 2 Ġ&& Ġintersect ed Obs . all Ġ{ Ġis Advanced Case ( it , Ġi , Ġstep ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( has Advanced Ġ&& Ġget Edge ( i ). isIn Rectangle ( origin , Ġwidth , Ġheight ) Ġ&& Ġis Advanced Case ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġintersect ed Obs . forEach Ġ{ Ġadjust Grow th ( it , Ġi , Ġstep ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġextended Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( has Advanced ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadvance Edge ( i , Ġ- step ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġa Ġflag Ġin Ġorder Ġto Ġstop Ġtrying Ġto Ġextend Ġthis Ġedge ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcan Edge Advance [ i ] Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġextended ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠChecks Ġwhether Ġwe Ġare Ġin Ġadvanced Ġcase . ĠSee Ġ[ extend ]. ĠThe Ġindex Ġof Ġthe ĊĠĠĠĠ Ġ* Ġgrowing Ġedge Ġand Ġthe Ġstep Ġof Ġgrowth Ġshould Ġbe Ġprovided Ġas Ġwell . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġis Advanced Case ( ob stacle : ĠShape , Ġindex : ĠInt , Ġstep : ĠDouble ) Ġ= ĊĠĠĠĠĠĠĠ Ġobstacle . vertices (). none Ġ{ Ġcontains Boundary Included ( it ) Ġ} Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvertices . filter Ġ{ Ġobstacle . contains ( it . to Point ()) Ġ}. size Ġ== Ġ 1 Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ! first Intr ude d Edge ( ob stacle , Ġindex , Ġstep ). is Parallel To ( get Edge ( index )) ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠDuring Ġthe Ġadvance ment Ġof Ġan Ġedge , Ġmultiple Ġedges Ġof Ġan Ġobstacle Ġmay Ġbe ĊĠĠĠĠ Ġ* Ġintersect ed . ĠThis Ġmethod Ġallows Ġto Ġfind Ġthe Ġfirst Ġintr ude d Ġedge Ġin Ġthe ĊĠĠĠĠ Ġ* Ġadvanced Ġcase Ġ( i . e ., Ġthe Ġone Ġthat Ġthe Ġpolygon Ġfirst Ġintr ude d Ġduring Ġits ĊĠĠĠĠ Ġ* Ġadvance ment ). ĠThe Ġindex Ġof Ġthe Ġgrowing Ġedge Ġand Ġthe Ġstep Ġof Ġgrowth Ġshould ĊĠĠĠĠ Ġ* Ġbe Ġprovided Ġas Ġwell . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfirst Intr ude d Edge ( ob stacle : ĠShape , Ġindex : ĠInt , Ġstep : ĠDouble ): ĠSegment 2 D < E uclidean 2 D Position > Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġintr uding Vertex Ġ= Ġget Edge ( index ). first ĊĠĠĠĠĠĠĠ Ġvar Ġgrowth Direction Ġ= Ġgrowth Directions [ index ]?. first ĊĠĠĠĠĠĠĠ Ġif Ġ(! ob stacle . contains ( intr uding Vertex . to Point ())) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġintr uding Vertex Ġ= Ġget Edge ( index ). second ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Direction Ġ= Ġgrowth Directions [ index ]?. second ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġgrowth Direction Ġ?: Ġthrow ĠIllegalStateException (" no Ġgrowth Ġdirection Ġfound ") ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* Ġa Ġsegment Ġgoing Ġfrom Ġthe Ġold Ġposition Ġof Ġthe Ġintr uding Ġvertex Ġto Ġthe Ġnew Ġone ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġmovement Segment Ġ= ĠSegment 2 DI mpl ( intr uding Vertex , Ġintr uding Vertex Ġ- Ġgrowth Direction . res ized ( step )) ĊĠĠĠĠĠĠĠ Ġval Ġintr ude d Edges Ġ= Ġfind Intersect ing Edges ( ob stacle , Ġmovement Segment ) ĊĠĠĠĠĠĠĠ Ġrequire ( intr ude d Edges . size Ġ== Ġ 1 ) Ġ{ Ġ" vertex Ġis Ġnot Ġintr uding " Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġintr ude d Edges . first () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠFinds Ġthe Ġedges Ġof Ġthe Ġobstacle Ġintersect ing Ġwith Ġthe Ġgiven Ġedge Ġof Ġthe Ġpolygon . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfind Intersect ing Edges ( ob stacle : ĠShape , Ġe : ĠSegment 2 D < E uclidean 2 D Position >) Ġ= ĊĠĠĠĠĠĠĠ Ġobstacle . vertices (). run Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmap Indexed Ġ{ Ġi , Ġv Ġ-> ĠSegment 2 DI mpl ( v , Ġthis [( i Ġ+ Ġ 1 ) Ġ% Ġsize ]) Ġ}. filter Ġ{ Ġedges Intersect ( it , Ġe ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠDeleg ates Ġthe Ġcheck Ġto Ġjava . awt . geom . Line 2 D . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġedges Intersect ( e 1 : ĠSegment 2 D <* >, Ġe 2 : ĠSegment 2 D <* >) Ġ= ĊĠĠĠĠĠĠĠ ĠLine 2 D . Double ( e 1 . first . to Point (), Ġe 1 . second . to Point ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. intersect s Line ( e 2 . first . x , Ġe 2 . first . y , Ġe 2 . second . x , Ġe 2 . second . y ) ĊĊĠĠĠ Ġprivate Ġval ĠVector 2 D <* >. to E uclidean Ġget () Ġ= Ġwhen Ġ( this ) Ġ{ ĊĠĠĠĠĠĠĠ Ġis ĠE uclidean 2 D Position Ġ-> Ġthis ĊĠĠĠĠĠĠĠ Ġelse Ġ-> ĠE uclidean 2 D Position ( x , Ġy ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠAdjust s Ġthe Ġgrowth Ġdirections Ġin Ġthe Ġadvanced Ġcase . ĠSee Ġ[ extend ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġadjust Grow th ( ob stacle : ĠShape , ĠindexOf Adv ancing Edge : ĠInt , Ġstep : ĠDouble ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval ĠindexOf Intr uding V Ġ= Ġvertices . indexOf First Ġ{ Ġobstacle . contains ( it . to Point ()) Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġintersect ing Ġedges ĊĠĠĠĠĠĠĠ Ġval Ġpolygon Edge 1 Ġ= Ġget Edge ( indexOf Intr uding V ) ĊĠĠĠĠĠĠĠ Ġval Ġpolygon Edge 2 Ġ= Ġget Edge ( circular Previous ( indexOf Intr uding V )) ĊĠĠĠĠĠĠĠ Ġval Ġobstacle Edge : ĠSegment 2 D < E uclidean 2 D Position > Ġ= Ġfirst Intr ude d Edge ( ob stacle , ĠindexOf Adv ancing Edge , Ġstep ) ĊĠĠĠĠĠĠĠ Ġ// Ġintersect ing Ġpoints Ġl ying Ġon Ġpolygon Ġboundary ĊĠĠĠĠĠĠĠ Ġval Ġintersection 1 Ġ= Ġpolygon Edge 1 . intersect ( ob stacle Edge ) ĊĠĠĠĠĠĠĠ Ġval Ġintersection 2 Ġ= Ġpolygon Edge 2 . intersect ( ob stacle Edge ) ĊĠĠĠĠĠĠĠ Ġrequire ( intersection 1 Ġis ĠIntersection 2 D . Single Point Ġ&& Ġintersection 2 Ġis ĠIntersection 2 D . Single Point ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ" Bug Ġin Ġthe ĠAl che mist Ġge ometric Ġengine . ĠFound Ġin Ġ${ this :: class . qualified Name }" ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġp 1 Ġ= Ġintersection 1 . point . to E uclidean ĊĠĠĠĠĠĠĠ Ġval Ġp 2 Ġ= Ġintersection 2 . point . to E uclidean ĊĠĠĠĠĠĠĠ Ġ// Ġa Ġnew Ġedge Ġis Ġgoing Ġto Ġbe Ġadded , Ġits Ġvertices Ġwill Ġgrow Ġfollowing Ġthe Ġintr ude d ĊĠĠĠĠĠĠĠ Ġ// Ġobstacle Edge . ĠIn Ġorder Ġto Ġdo Ġso , Ġtheir Ġgrowth Ġdirections Ġwill Ġbe Ġmodified Ġto Ġbe ĊĠĠĠĠĠĠĠ Ġ// Ġparallel Ġto Ġsuch Ġedge , Ġbut Ġin Ġopposite Ġsense s . ĊĠĠĠĠĠĠĠ Ġval Ġd 1 : ĠE uclidean 2 D Position ĊĠĠĠĠĠĠĠ Ġval Ġd 2 : ĠE uclidean 2 D Position ĊĠĠĠĠĠĠĠ Ġif Ġ( p 1 . distance To ( ob stacle Edge . first ) Ġ< Ġp 2 . distance To ( ob stacle Edge . first )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd 1 Ġ= Ġ( ob stacle Edge . first Ġ- Ġp 1 ). normalized () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd 2 Ġ= Ġ( ob stacle Edge . second Ġ- Ġp 2 ). normalized () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd 1 Ġ= Ġ( ob stacle Edge . second Ġ- Ġp 1 ). normalized () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd 2 Ġ= Ġ( ob stacle Edge . first Ġ- Ġp 2 ). normalized () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġsince Ġwe Ġintr ude d Ġan Ġobstacle Ġwe Ġneed Ġto Ġstep Ġback Ġanyway ĊĠĠĠĠĠĠĠ Ġadvance Edge ( indexOf Adv ancing Edge , Ġ- step ) ĊĠĠĠĠĠĠĠ Ġmodify Grow th Direction ( indexOf Intr uding V , Ġd 1 , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġadd Vertex ( indexOf Intr uding V , Ġvertices [ indexOf Intr uding V ]. x , Ġvertices [ indexOf Intr uding V ]. y ) ĊĠĠĠĠĠĠĠ Ġcan Edge Advance [ indexOf Intr uding V ] Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġmodify Grow th Direction ( circular Previous ( indexOf Intr uding V ), Ġd 2 , Ġfalse ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġmodify Grow th Direction ( i : ĠInt , Ġnew D : ĠE uclidean 2 D Position , Ġfirst : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġgrowth Directions [ i ] ĊĠĠĠĠĠĠĠ Ġif Ġ( d Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ i ] Ġ= Ġif Ġ( first ) ĠPair ( new D , Ġnull ) Ġelse ĠPair ( null , Ġnew D ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrowth Directions [ i ] Ġ= Ġif Ġ( first ) Ġd . copy ( first Ġ= Ġnew D ) Ġelse Ġd . copy ( second Ġ= Ġnew D ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun ĠVector 2 D <* >. to Point () Ġ= ĠPoint 2 D . Double ( x , Ġy ) ĊĊĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?) Ġ= Ġsuper . equals ( other ) ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode () Ġ= Ġsuper . hashCode () Ċ } Ċ