package Ġcom . so y wiz . k orm a . triangle . path find Ċ Ċ import Ġcom . so y wiz . k ds .* Ċ import Ġcom . so y wiz . k orm a . geom .* Ċ import Ġcom . so y wiz . k orm a . geom . triangle .* Ċ import Ġkotlin . math .* Ċ Ċ private Ġtype alias ĠSpatial Node Ġ= ĠSpatial Mesh . Node Ċ Ċ class ĠSpatial Mesh Find ( val Ġspatial Mesh : ĠSpatial Mesh ) Ġ{ ĊĠĠĠ Ġprivate Ġvar Ġopen edList Ġ= ĠPriority Queue < Spatial Node > Ġ{ Ġl , Ġr Ġ-> Ġl . F . compareTo ( r . F ) Ġ} ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġreset () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġreset () Ġ{ ĊĠĠĠĠĠĠĠ Ġopen edList Ġ= ĠPriority Queue Ġ{ Ġl , Ġr Ġ-> Ġl . F . compareTo ( r . F ) Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( node Ġin Ġthis . spatial Mesh . nodes ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . G Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . H Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . closed Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfind ( start Node : ĠSpatial Node ?, Ġend Node : ĠSpatial Node ?): ĠList < Spatial Node > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġreturn List Ġ= ĠArrayList < Spatial Node >() ĊĠĠĠĠĠĠĠ Ġreset () ĊĠĠĠĠĠĠĠ Ġvar ĠcurrentNode Ġ= Ġstart Node ĊĊĠĠĠĠĠĠĠ Ġif Ġ( start Node Ġ!== Ġnull Ġ&& Ġend Node Ġ!== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠaddTo Open edList ( start Node ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(( currentNode Ġ!= Ġend Node ) Ġ&& Ġopen edList Has Items ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠcurrentNode Ġ= Ġget And Remove First From Open edList () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd Node To Closed List ( currentNode ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( neighbor Node Ġin ĠgetNode Neighbors ( currentNode )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIgnore Ġinvalid Ġpaths Ġand Ġthe Ġones Ġon Ġthe Ġclosed Ġlist . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( in Closed List ( neighbor Node )) Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠG Ġ= ĠcurrentNode . G Ġ+ Ġneighbor Node . distance To Spatial Node ( currentNode ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNot Ġin Ġopened Ġlist Ġyet . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! in Open edList ( neighbor Node )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠaddTo Open edList ( neighbor Node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġneighbor Node . G Ġ= ĠG ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġneighbor Node . H Ġ= Ġneighbor Node . distance To Spatial Node ( end Node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġneighbor Node . parent Ġ= ĠcurrentNode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġupdated Node On Open edList ( neighbor Node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIn Ġopened Ġlist Ġbut Ġwith Ġa Ġworse ĠG Ġthan Ġthis Ġone . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġif Ġ( G Ġ< Ġneighbor Node . G ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġneighbor Node . G Ġ= ĠG ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġneighbor Node . parent Ġ= ĠcurrentNode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġupdated Node On Open edList ( neighbor Node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( currentNode Ġ!= Ġend Node ) Ġthrow ( Exception (" Can 't Ġfind Ġa Ġpath ", Ġ 1 )) ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( currentNode Ġ!= Ġstart Node ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn List . add ( currentNode !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// return List . push ( currentNode ); ĊĠĠĠĠĠĠĠĠĠĠĠ ĠcurrentNode Ġ= ĠcurrentNode . parent ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( start Node Ġ!= Ġnull ) Ġreturn List . add ( start Node ) ĊĊĠĠĠĠĠĠĠ Ġreturn List . reverse () ĊĊĠĠĠĠĠĠĠ Ġreturn Ġreturn List ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun ĠaddTo Open edList ( node : ĠSpatial Node ): ĠUnit Ġ= Ġrun Ġ{ Ġopen edList . add ( node ) Ġ} ĊĠĠĠ Ġprivate Ġfun Ġopen edList Has Items (): ĠBoolean Ġ= Ġopen edList . size Ġ> Ġ 0 ĊĠĠĠ Ġprivate Ġfun Ġget And Remove First From Open edList (): ĠSpatial Node Ġ= Ġopen edList . remove Head () ĊĠĠĠ Ġprivate Ġfun Ġadd Node To Closed List ( node : ĠSpatial Node ): ĠUnit Ġ= Ġrun Ġ{ Ġnode . closed Ġ= Ġtrue Ġ} ĊĠĠĠ Ġprivate Ġfun Ġin Closed List ( node : ĠSpatial Node ): ĠBoolean Ġ= Ġnode . closed ĊĠĠĠ Ġprivate Ġfun ĠgetNode Neighbors ( node : ĠSpatial Node ): ĠArrayList < Spatial Node > Ġ= Ġnode . neighbors ĊĠĠĠ Ġprivate Ġfun Ġin Open edList ( node : ĠSpatial Node ): ĠBoolean Ġ= Ġopen edList . contains ( node ) ĊĊĠĠĠ Ġprivate Ġfun Ġupdated Node On Open edList ( node : ĠSpatial Node ): ĠUnit Ġ{ ĊĠĠĠĠĠĠĠ Ġopen edList . update Object ( node ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* public Ġfun Ġin Closed List ( node : Spatial Node ): Boolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( closed List [ node ] Ġ!== Ġundefined ); ĊĠĠĠ Ġ}*/ ĊĊĠĠĠ Ġobject ĠChannel Ġ{ ĊĠĠĠĠĠĠĠ Ġclass ĠEdge Context Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġget Common Edge ( t 1 : ĠTriangle , Ġt 2 : ĠTriangle ): ĠEdge Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcommon Indexes Ġ= ĠArrayList < I Point >() ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( n Ġin Ġ 0 Ġuntil Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Ġ= Ġt 1 . point ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t 2 . contains Point ( point )) Ġcommon Indexes . add ( point ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( common Indexes . size Ġ!= Ġ 2 ) Ġthrow ĠError (" Triangles Ġare Ġnot Ġcontiguous ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠEdge ( common Indexes [ 0 ], Ġcommon Indexes [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġchannel To Port als ( start Point : ĠI Point , Ġend Point : ĠI Point , Ġchannel : ĠList < Spatial Node >): ĠF unnel Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġport als Ġ= ĠF unnel () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġport als . push ( start Point ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( channel . size Ġ>= Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Triangle Ġ= Ġchannel [ 0 ]. triangle !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsecond Triangle Ġ= Ġchannel [ 1 ]. triangle !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlast Triangle Ġ= Ġchannel [ channel . size Ġ- Ġ 1 ]. triangle !! ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( first Triangle . point Inside Triangle ( start Point )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( last Triangle . point Inside Triangle ( end Point )) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġstart Vertex Ġ= ĠTriangle . get Not Common Vertex ( first Triangle , Ġsecond Triangle ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġvertex CW 0 : ĠI Point Ġ= Ġstart Vertex ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġvertex CC W 0 : ĠI Point Ġ= Ġstart Vertex ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// trace ( start Vertex ); ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġctx Edge Ġ= ĠEdge Context () ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( n Ġin Ġ 0 Ġuntil Ġchannel . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtriangle Current Ġ= Ġchannel [ n Ġ+ Ġ 0 ]. triangle !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtriangle Next Ġ= Ġchannel [ n Ġ+ Ġ 1 ]. triangle !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcommon Edge Ġ= Ġctx Edge . get Common Edge ( triangle Current , Ġtriangle Next ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvertex CW 1 Ġ= Ġtriangle Current . point CW ( vertex CW 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvertex CC W 1 Ġ= Ġtriangle Current . point CC W ( vertex CC W 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! common Edge . has Point ( vertex CW 0 )) Ġvertex CW 0 Ġ= Ġvertex CW 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! common Edge . has Point ( vertex CC W 0 )) Ġvertex CC W 0 Ġ= Ġvertex CC W 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġport als . push ( vertex CW 0 , Ġvertex CC W 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// trace ( vertex CW 0 , Ġvertex CC W 0 ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġport als . push ( end Point ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġport als . string Pull () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġport als ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġassert ( test : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! test ) Ġthrow ( Error (" Assert Ġerror ")) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġclass ĠF unnel Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġval Ġport als Ġ= ĠArrayList < Portal >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpath Ġ= Ġarray ListOf < I Point >() ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġfun Ġtri area 2 ( a : ĠI Point , Ġb : ĠI Point , Ġc : ĠI Point ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġax Ġ= Ġb . x Ġ- Ġa . x ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġay Ġ= Ġb . y Ġ- Ġa . y ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbx Ġ= Ġc . x Ġ- Ġa . x ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġby Ġ= Ġc . y Ġ- Ġa . y ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġbx Ġ* Ġay Ġ- Ġax Ġ* Ġby ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġfun Ġv dist sqr ( a : ĠI Point , Ġb : ĠI Point ): ĠDouble Ġ= Ġh ypot ( b . x Ġ- Ġa . x , Ġb . y Ġ- Ġa . y ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġfun Ġv equal ( a : ĠI Point , Ġb : ĠI Point ): ĠBoolean Ġ= Ġv dist sqr ( a , Ġb ) Ġ< Ġ( 0 . 0 0 1 Ġ* Ġ 0 . 0 0 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġpush ( p 1 : ĠI Point , Ġp 2 : ĠI Point Ġ= Ġp 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . port als . add ( Portal ( p 1 , Ġp 2 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* if Ġ( p 2 Ġ== Ġp 1 ) Ġ{ Ċĉĉĉĉ ĉ trace (' channel . push (' Ġ+ Ġp 1 Ġ+ Ġ'); '); Ċĉĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉĉ ĉ trace (' channel . push (' Ġ+ Ġp 1 Ġ+ Ġ', Ġ' Ġ+ Ġp 2 Ġ+ Ġ'); '); Ċĉĉĉ ĉ }*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġstring Pull (): ĠArrayList < I Point > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpts Ġ= ĠArrayList < I Point >() ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠInit Ġscan Ġstate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġportal Apex : ĠI Point ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġportal Left : ĠI Point ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġportal Right : ĠI Point ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġap ex Index : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġleft Index : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġright Index : ĠInt Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Apex Ġ= Ġport als [ 0 ]. left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Left Ġ= Ġport als [ 0 ]. left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Right Ġ= Ġport als [ 0 ]. right ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAdd Ġstart Ġpoint . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts . add ( portal Apex ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġport als . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Ġ= Ġport als [ i ]. left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Ġ= Ġport als [ i ]. right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUpdate Ġright Ġvertex . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( tri area 2 ( portal Apex , Ġportal Right , Ġright ) Ġ<= Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ve qual ( portal Apex , Ġportal Right ) Ġ|| Ġtri area 2 ( portal Apex , Ġportal Left , Ġright ) Ġ> Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠT ight en Ġthe Ġfun nel . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Right Ġ= Ġright ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Index Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRight Ġover Ġleft , Ġinsert Ġleft Ġto Ġpath Ġand Ġrestart Ġscan Ġfrom Ġportal Ġleft Ġpoint . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts . add ( portal Left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMake Ġcurrent Ġleft Ġthe Ġap ex . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Apex Ġ= Ġportal Left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġap ex Index Ġ= Ġleft Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠReset Ġportal ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Left Ġ= Ġportal Apex ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Right Ġ= Ġportal Apex ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Index Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Index Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRestart Ġscan ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUpdate Ġleft Ġvertex . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( tri area 2 ( portal Apex , Ġportal Left , Ġleft ) Ġ>= Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ve qual ( portal Apex , Ġportal Left ) Ġ|| Ġtri area 2 ( portal Apex , Ġportal Right , Ġleft ) Ġ< Ġ 0 . 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠT ight en Ġthe Ġfun nel . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Left Ġ= Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Index Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠLeft Ġover Ġright , Ġinsert Ġright Ġto Ġpath Ġand Ġrestart Ġscan Ġfrom Ġportal Ġright Ġpoint . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts . add ( portal Right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMake Ġcurrent Ġright Ġthe Ġap ex . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Apex Ġ= Ġportal Right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġap ex Index Ġ= Ġright Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠReset Ġportal ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Left Ġ= Ġportal Apex ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġportal Right Ġ= Ġportal Apex ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Index Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Index Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRestart Ġscan ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġap ex Index ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( pts . size Ġ== Ġ 0 ) Ġ|| Ġ(! ve qual ( pts [ pts . size Ġ- Ġ 1 ], Ġport als [ port als . size Ġ- Ġ 1 ]. left ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAppend Ġlast Ġpoint Ġto Ġpath . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts . add ( port als [ port als . size Ġ- Ġ 1 ]. left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . path Ġ= Ġpts ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġpts ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata Ġclass ĠPortal ( val Ġleft : ĠI Point , Ġval Ġright : ĠI Point ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠException ( message : ĠString Ġ= Ġ"", Ġval Ġindex : ĠInt Ġ= Ġ 0 ) Ġ: Ġkotlin . Exception ( message ) Ċ } Ċ