package Ġdev . edu ay uso . cg kotlin . shared . impl . algorithms . conv ex hull Ċ Ċ import Ġdev . edu ay uso . cg kotlin . shared . domain . algorithms . I Convex H ull Algorithm Ċ import Ġdev . edu ay uso . cg kotlin . shared . domain . algorithms . I Convex H ull Task Listener Ċ import Ġdev . edu ay uso . cg kotlin . shared . domain . entities . Point Entity Ċ import Ġdev . edu ay uso . cg kotlin . shared . domain . entities . Point Set Entity Ċ import Ġdev . edu ay uso . cg kotlin . shared . impl . algorithms . Algorithm Util Ċ import Ġjava . util .* Ċ Ċ /** Ċ Ġ* Ġ================================================================= ================================ Ċ Ġ* ĠGra ham ĠScan ĠAlgorithm Ċ Ġ* Ġ================================================================= ================================ Ċ Ġ* ĠComplex ity ĠO ( n * log n ) Ċ Ġ* Ġ------------------------------------------------------------------------------------------------ - Ċ Ġ* ĠPhase Ġ 1 : ĠPre processing Ċ Ġ* Ġ------------------------------------------------------------------------------------------------ - Ċ Ġ* ĠFirst Ġwe Ġsearch Ġthe Ġlower And Then Left Most Ġpoint : Ġs 0 . Ċ Ġ* ĠThe Ġrest Ġof Ġpoints Ġis Ġordered Ġaccording Ġto Ġthe Ġpolar Ġangle Ġof Ġthe Ġvector Ġfrom Ġs 0 Ġto Ġeach Ġpoint . Ċ Ġ* ĠWe Ġtake Ġthe Ġfirst Ġof Ġthe Ġordered Ġpoints : Ġs 1 . ĠSo , Ġs 0 -> s 1 Ġis Ġthe Ġfirst Ġextreme Ġedge Ċ Ġ* ĠWe Ġhave Ġtwo Ġstacks : Ċ Ġ* ĠStack ĠS Ġholds Ġthe Ġcandidate Ġextreme Ġpoints . ĠThe Ġfirst Ġelements Ġpushed Ġare Ġs 0 Ġand Ġs 1 Ċ Ġ* ĠStack ĠT Ġholds Ġthe Ġrest Ġof Ġthe Ġpoints Ġpushed Ġin Ġorder Ċ Ġ* Ġ------------------------------------------------------------------------------------------------ - Ċ Ġ* ĠPhase Ġ 2 : ĠScan Ċ Ġ* Ġ------------------------------------------------------------------------------------------------ - Ċ Ġ* ĠWe Ġtake Ġtwo Ġpoints Ġfrom Ġthe Ġtop Ġof ĠS Ġand Ġdo Ġa Ġleft Test Ġwith Ġthe Ġfirst Ġpoint Ġfrom Ġtop Ġof ĠT . Ċ Ġ* ĠIf Ġtest Ġreturns Ġtrue Ġ-> Ġpop Ġfrom ĠT Ġ-> Ġpush Ġpop ped Ġpoint Ġto ĠS Ċ Ġ* ĠIf Ġtest Ġreturns Ġfalse Ġ-> Ġpop Ġfrom ĠS Ġ( discard Ġcandidate ) Ċ Ġ* ĠRepeat Ġuntil ĠT Ġis Ġempty Ċ Ġ*/ Ċ object ĠGra ham Scan Algorithm : ĠI Convex H ull Algorithm Ġ{ ĊĊĠĠĠ Ġoverride Ġval Ġstep Option Ġ= Ġtrue ĊĊĠĠĠ Ġval Ġstack S : ĠStack < Point Entity > Ġ= ĠStack () ĊĠĠĠ Ġval Ġstack T : ĠStack < Point Entity > Ġ= ĠStack () ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠV ars Ġonly Ġfor Ġsteps ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġvar Ġste pping Ġ= Ġfalse ĊĠĠĠ Ġvar Ġs 0 : ĠInt ? Ġ= Ġnull Ġ// Ġfirst Ġpoint ĊĠĠĠ Ġvar Ġsn : ĠInt Ġ= Ġ 0 Ġ// Ġstack S Ġindex ĊĠĠĠ Ġvar Ġtn : ĠInt Ġ= Ġ 0 Ġ// Ġstack T Ġindex ĊĊĠĠĠ Ġoverride Ġfun Ġrun ( input : ĠPoint Set Entity , Ġlistener : ĠI Convex H ull Task Listener ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġthis . reset () ĊĠĠĠĠĠĠĠ Ġinput . reset () ĊĊĠĠĠĠĠĠĠ Ġpreprocessing ( input ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack T . isNotEmpty ()) Ġscan () ĊĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġjoin Ġthe Ġlast Ġpoint Ġto Ġthe Ġfirst , Ġso Ġwe Ġclose Ġthe Ġconvex Ġh ull ĊĠĠĠĠĠĠĠ Ġstack S . last Element (). success or Ġ= Ġstack S . first Element () ĊĊĠĠĠĠĠĠĠ Ġ// ĠPresent Ġresult Ġ( all Ġpoints Ġare Ġreferences , Ġso Ġ' input ' Ġcontains Ġthe Ġpoints Ġupdated Ġas Ġextreme ) ĊĠĠĠĠĠĠĠ Ġlistener . on Finish ( input ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġpreprocessing ( input : ĠPoint Set Entity ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// ĠFirst Ġwe Ġsearch Ġthe Ġlower And Then Left Most Ġpoint : Ġp 0 ĊĠĠĠĠĠĠĠ Ġval Ġs 0 Ġ= ĠAlgorithm Util . lower Then Left Most ( input ) ĊĠĠĠĠĠĠĠ Ġval Ġp 0 Ġ= Ġinput . list [ s 0 ] ĊĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġother Ġpoints Ġ( all Ġbut Ġp 0 ) Ġis Ġordered Ġaccording Ġto Ġthe Ġpolar Ġangle Ġof Ġthe Ġvector Ġfrom Ġp 0 Ġto Ġeach Ġpoint . ĊĠĠĠĠĠĠĠ Ġval Ġinput But P 0 Ġ= Ġinput . list . filter Ġ{ Ġit Ġ!= Ġp 0 Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġsorted List Ġ= Ġinput But P 0 . sorted With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa , Ġb Ġ-> ĠAlgorithm Util . polar Angle Comparator ( p 0 , Ġa , Ġb ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġbuild Ġa Ġstack Ġpushing Ġthe Ġordered Ġpoints Ġbut ĊĠĠĠĠĠĠĠ Ġsorted List . forEach Ġ{ Ġstack T . push ( it ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠOur Ġfirst Ġextreme Ġpoint Ġis Ġp 0 Ġand Ġthe Ġfirst Ġof Ġthe Ġordered Ġlist Ġ( p 1 ) ĊĠĠĠĠĠĠĠ Ġp 0 . apply Ġ{ Ġis Ext reme Ġ= Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġp 1 Ġ= Ġstack T . pop (). apply Ġ{ Ġis Ext reme Ġ= Ġtrue Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġhave Ġthe Ġfirst Ġextreme Ġedge : Ġs 0 -> s 1 ĊĠĠĠĠĠĠĠ Ġ// ĠStack ĠS Ġholds Ġthe Ġcandidate Ġextreme Ġpoints . ĠThe Ġfirst Ġelements Ġpushed Ġare Ġs 0 Ġand Ġs 1 ĊĠĠĠĠĠĠĠ Ġ// ĠStack ĠT Ġholds Ġthe Ġrest Ġof Ġthe Ġpoints Ġpushed Ġin Ġorder ĊĠĠĠĠĠĠĠ Ġstack S . push ( p 0 ) ĊĠĠĠĠĠĠĠ Ġstack S . push ( p 1 ) ĊĠĠĠĠĠĠĠ Ġp 0 . success or Ġ= Ġp 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġscan () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġtake Ġtwo Ġpoints Ġfrom Ġthe Ġtop Ġof ĠS Ġand Ġdo Ġa Ġleft Test Ġwith Ġthe Ġfirst Ġpoint Ġfrom Ġtop Ġof ĠT . ĊĠĠĠĠĠĠĠ Ġval Ġs 0 Ġ= Ġstack S . peek () ĊĠĠĠĠĠĠĠ Ġval Ġs 1 Ġ= Ġstack S . elementAt ( stack S . size - 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ Ġ= Ġstack T . peek () ĊĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġtest Ġreturns Ġtrue Ġ-> Ġpop Ġfrom ĠT Ġ-> Ġpush Ġpop ped Ġpoint Ġto ĠS ĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġtest Ġreturns Ġfalse Ġ-> Ġpop Ġfrom ĠS Ġ( discard Ġcandidate ) ĊĠĠĠĠĠĠĠ Ġif Ġ( Algorithm Util . to Left ( s 1 , Ġs 0 , Ġp )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Ġ= Ġstack T . pop () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! stack S . contains ( point )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack S . push ( point . apply Ġ{ Ġis Ext reme Ġ= Ġtrue Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs 0 . success or Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġs 0 . success or Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack S . pop (). is Ext reme Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġshows Ġthe Ġprocess Ġstep Ġby Ġstep ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġstep ( input : ĠPoint Set Entity , Ġlistener : ĠI Convex H ull Task Listener ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġif Ġ(! ste pping Ġ|| Ġstack T . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . reset () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput . reset () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġste pping Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġs 0 Ġ= ĠAlgorithm Util . lower Then Left Most ( input ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpreprocessing ( input ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġp 0 Ġ= Ġinput . list [ s 0 !! ] ĊĠĠĠĠĠĠĠ Ġval Ġpn Ġ= Ġstack T . peek () ĊĊĠĠĠĠĠĠĠ Ġscan () ĊĊĠĠĠĠĠĠĠ Ġif Ġ(! stack T . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhelper Ġ= ĠPoint Set Entity ( listOf ( p 0 , Ġpn )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlistener . on Step ( helper , Ġinput ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġjoin Ġthe Ġlast Ġpoint Ġto Ġthe Ġfirst , Ġso Ġwe Ġclose Ġthe Ġconvex Ġh ull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack S . last Element (). success or Ġ= Ġstack S . first Element () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlistener . on Finish ( input ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġreset () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġste pping Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġs 0 Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġsn Ġ= Ġ 0 ĊĠĠĠĠĠĠ Ġ// Ġtn Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġstack S . clear () ĊĠĠĠĠĠĠĠ Ġstack T . clear () ĊĠĠĠ Ġ} Ċ }