import Ġandroidx . core . util . Pair Ċ import Ġjava . util .* Ċ import Ġkotlin . math . abs Ċ import Ġkotlin . math . atan 2 Ċ import Ġkotlin . math . pow Ċ import Ġkotlin . math . sqrt Ċ Ċ /** Ċ Ġ* ĠCon c ave H ull . kt Ġ- Ġ 5 / 1 1 / 2 0 Ċ Ġ* Ċ Ġ* Ġ@ author ĠD ani il ĠPo zd ny ak ov Ġhttps :// github . com / mak aron is Ċ Ġ* Ġ@ version Ġ 1 . 0 Ċ Ġ* Ċ Ġ* ĠThis Ġis Ġan Ġimplementation Ġof Ġthe Ġalgorithm Ġdescribed Ġby ĠAd ri ano ĠMore ira Ġand ĠMar ib el ĠY as min a ĠSan tos : Ċ Ġ* ĠCON CA VE ĠH ULL : ĠA ĠK - NE ARE ST ĠNE IGH BO UR S ĠAP PRO ACH ĠFOR ĠTHE ĠCOMP UT ATION ĠOF ĠTHE ĠREGION ĠO CC U PI ED ĠBY ĠA ĠSET ĠOF ĠPOINT S . Ċ Ġ* ĠGR APP Ġ 2 0 0 7 Ġ- ĠInternational ĠConference Ġon ĠComputer ĠGraphics ĠTheory Ġand ĠApplications ; Ġpp Ġ 6 1 - 6 8 . Ċ Ġ* Ċ Ġ* Ġhttps :// re positor ium . sd um . umin ho . pt / bit stream / 1 8 2 2 / 6 4 2 9 / 1 / Con c ave H ull _ ACM _ MY S . pdf Ċ Ġ* Ċ Ġ* ĠBased Ġon Ġhttps :// github . com / Mer ow ech / java - conc ave - hull / blob / master / Con c ave H ull . java Ċ Ġ*/ Ċ Ċ class ĠCon c ave H ull Ġ{ ĊĠĠĠ Ġclass ĠPoint ( val Ġx : ĠDouble , Ġval Ġy : ĠDouble ) Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ" ($ x Ġ$ y )" ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġequals ( obj : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( obj Ġis ĠPoint ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ== Ġobj . x Ġ&& Ġy Ġ== Ġobj . y ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġhttp :// stackoverflow . com / questions / 2 2 8 2 6 3 2 6 / good - hash code - function - for - 2 d - coordinates ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġhttp :// www . cs . up c . edu /~ al vare z / calcul abil itat / enum er abil itat . pdf ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġ( y Ġ+ Ġ( x Ġ+ Ġ 1 ) Ġ/ Ġ 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġabs (( x Ġ+ Ġtmp Ġ* Ġtmp ). toInt ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġe uclidean Distance ( a : ĠPoint , Ġb : ĠPoint ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġsqrt (( a . x Ġ- Ġb . x ). pow ( 2 . 0 ) Ġ+ Ġ( a . y Ġ- Ġb . y ). pow ( 2 . 0 )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġk Nearest Neighbors ( ĊĠĠĠĠĠĠĠ Ġpoints : ĠArrayList < Point >, ĊĠĠĠĠĠĠĠ Ġcenter Point : ĠPoint , ĊĠĠĠĠĠĠĠ Ġk : ĠInt ĊĠĠĠ Ġ): ĠArrayList < Pair < Double , ĠPoint >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnearest List Ġ= ĠArrayList < Pair < Double , ĠPoint >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( point Ġin Ġpoints ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnearest List . add ( Pair ( e uclidean Distance ( center Point , Ġpoint ), Ġpoint )) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġnearest List . sortBy Ġ{ Ġit . first Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠArrayList < Pair < Double , ĠPoint >>() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġk . coerce At Most ( nearest List . size )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġneighbour Ġ= Ġnearest List . get OrNull ( i ) Ġ?: Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( ne ighbour ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Min Y Point ( points : ĠArrayList < Point >): ĠPoint Ġ{ ĊĠĠĠĠĠĠĠ Ġpoints . sort With Ġ{ Ġo 1 , Ġo 2 Ġ-> Ġo 1 . y . compareTo ( o 2 . y ) Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġpoints [ 0 ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcalculate Angle ( o 1 : ĠPoint ?, Ġo 2 : ĠPoint ?): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġatan 2 ( o 2 !!. y Ġ- Ġo 1 !!. y , Ġo 2 . x Ġ- Ġo 1 . x ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġangle Difference ( a 1 : ĠDouble , Ġa 2 : ĠDouble ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġangle Ġdifference Ġin Ġclock wise Ġdirections Ġas Ġradians ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( a 1 Ġ> Ġ 0 Ġ&& Ġa 2 Ġ>= Ġ 0 Ġ&& Ġa 1 Ġ> Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġabs ( a 1 Ġ- Ġa 2 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( a 1 Ġ>= Ġ 0 Ġ&& Ġa 2 Ġ> Ġ 0 Ġ&& Ġa 1 Ġ< Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ* ĠMath . PI Ġ+ Ġa 1 Ġ- Ġa 2 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( a 1 Ġ< Ġ 0 Ġ&& Ġa 2 Ġ<= Ġ 0 Ġ&& Ġa 1 Ġ< Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ* ĠMath . PI Ġ+ Ġa 1 Ġ+ Ġabs ( a 2 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( a 1 Ġ<= Ġ 0 Ġ&& Ġa 2 Ġ< Ġ 0 Ġ&& Ġa 1 Ġ> Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġabs ( a 1 Ġ- Ġa 2 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( a 1 Ġ<= Ġ 0 Ġ&& Ġ 0 Ġ< Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ* ĠMath . PI Ġ+ Ġa 1 Ġ- Ġa 2 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( a 1 Ġ>= Ġ 0 Ġ&& Ġ 0 Ġ>= Ġa 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa 1 Ġ+ Ġabs ( a 2 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 . 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun ĠsortBy Angle ( ĊĠĠĠĠĠĠĠ Ġnearest Points : ĠArrayList < Pair < Double , ĠPoint >>, ĊĠĠĠĠĠĠĠ Ġcurrent Point : ĠPoint , ĊĠĠĠĠĠĠĠ Ġprev Angle : ĠDouble ĊĠĠĠ Ġ): ĠList < Point > Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠSort Ġby Ġangle Ġdescending ĊĠĠĠĠĠĠĠ Ġval Ġsorted List Ġ= Ġnearest Points . to Mutable List (). as Re versed () ĊĠĠĠĠĠĠĠ Ġsorted List . sort With Ġ{ Ġo 1 , Ġo 2 Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa 1 Ġ= Ġangle Difference ( prev Angle , Ġcalculate Angle ( current Point , Ġo 1 . second )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa 2 Ġ= Ġangle Difference ( prev Angle , Ġcalculate Angle ( current Point , Ġo 2 . second )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcompare Ġ= Ġa 2 . compareTo ( a 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġtwo Ġangle Ġa Ġsame , Ġselect Ġone Ġthat Ġmore Ġclosely ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( compare Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Distance Ġ= Ġo 1 . first Ġ?: Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsecond Distance Ġ= Ġo 2 . first Ġ?: Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfirst Distance . compareTo ( second Distance ) Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcompare ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġsorted List . map Ġ{ Ġit . second Ġ?: ĠPoint ( 0 . 0 , Ġ 0 . 0 ) Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġintersect ( l 1 p 1 : ĠPoint ?, Ġl 1 p 2 : ĠPoint ?, Ġl 2 p 1 : ĠPoint ?, Ġl 2 p 2 : ĠPoint ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġpart Ġequations Ġfor Ġline - line Ġintersection ĊĠĠĠĠĠĠĠ Ġval Ġa 1 Ġ= Ġl 1 p 2 !!. y Ġ- Ġl 1 p 1 !!. y ĊĠĠĠĠĠĠĠ Ġval Ġb 1 Ġ= Ġl 1 p 1 . x Ġ- Ġl 1 p 2 . x ĊĠĠĠĠĠĠĠ Ġval Ġc 1 Ġ= Ġa 1 Ġ* Ġl 1 p 1 . x Ġ+ Ġb 1 Ġ* Ġl 1 p 1 . y ĊĠĠĠĠĠĠĠ Ġval Ġa 2 Ġ= Ġl 2 p 2 !!. y Ġ- Ġl 2 p 1 !!. y ĊĠĠĠĠĠĠĠ Ġval Ġb 2 Ġ= Ġl 2 p 1 . x Ġ- Ġl 2 p 2 . x ĊĠĠĠĠĠĠĠ Ġval Ġc 2 Ġ= Ġa 2 Ġ* Ġl 2 p 1 . x Ġ+ Ġb 2 Ġ* Ġl 2 p 1 . y ĊĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġthe Ġdivisor ĊĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġa 1 Ġ* Ġb 2 Ġ- Ġa 2 Ġ* Ġb 1 ĊĊĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġintersection Ġpoint Ġx Ġcoordinate ĊĠĠĠĠĠĠĠ Ġval Ġp X Ġ= Ġ( c 1 Ġ* Ġb 2 Ġ- Ġc 2 Ġ* Ġb 1 ) Ġ/ Ġtmp ĊĠĠĠĠĠĠĠ Ġif Ġ( pX . isNaN ()) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġintersection Ġx Ġcoordinate Ġlies Ġin Ġline Ġline Ġsegment ĊĠĠĠĠĠĠĠ Ġif Ġ( pX Ġ> Ġl 1 p 1 . x Ġ&& Ġp X Ġ> Ġl 1 p 2 . x Ġ|| Ġp X Ġ> Ġl 2 p 1 . x Ġ&& Ġp X Ġ> Ġl 2 p 2 . x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġp X Ġ< Ġl 1 p 1 . x Ġ&& Ġp X Ġ< Ġl 1 p 2 . x Ġ|| Ġp X Ġ< Ġl 2 p 1 . x Ġ&& Ġp X Ġ< Ġl 2 p 2 . x ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġintersection Ġpoint Ġy Ġcoordinate ĊĠĠĠĠĠĠĠ Ġval Ġp Y Ġ= Ġ( a 1 Ġ* Ġc 2 Ġ- Ġa 2 Ġ* Ġc 1 ) Ġ/ Ġtmp ĊĠĠĠĠĠĠĠ Ġif Ġ( p Y . isNaN ()) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġintersection Ġy Ġcoordinate Ġlies Ġin Ġline Ġline Ġsegment ĊĠĠĠĠĠĠĠ Ġreturn Ġ!( p Y Ġ> Ġl 1 p 1 . y Ġ&& Ġp Y Ġ> Ġl 1 p 2 . y Ġ|| Ġp Y Ġ> Ġl 2 p 1 . y Ġ&& Ġp Y Ġ> Ġl 2 p 2 . y ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġp Y Ġ< Ġl 1 p 1 . y Ġ&& Ġp Y Ġ< Ġl 1 p 2 . y Ġ|| Ġp Y Ġ< Ġl 2 p 1 . y Ġ&& Ġp Y Ġ< Ġl 2 p 2 . y ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġpoint In Polygon ( p : ĠPoint ?, Ġpp : ĠArrayList < Point >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġpp . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġpp . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( pp [ i ]. y Ġ> Ġp !!. y Ġ!= Ġpp [ j ]. y Ġ> Ġp . y Ġ&& ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . x Ġ< Ġ( pp [ j ]. x Ġ- Ġpp [ i ]. x ) Ġ* Ġ( p . y Ġ- Ġpp [ i ]. y ) Ġ/ Ġ( pp [ j ]. y Ġ- Ġpp [ i ]. y ) Ġ+ Ġpp [ i ]. x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġ! result ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ= Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcalculate Con c ave H ull ( ĊĠĠĠĠĠĠĠ Ġpoint ArrayList : ĠArrayList < Point >, ĊĠĠĠĠĠĠĠ Ġk : ĠInt ĊĠĠĠ Ġ): ĠArrayList < Point > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġresulting Ġconc ave Ġh ull ĊĠĠĠĠĠĠĠ Ġval Ġconc ave H ull Ġ= ĠArrayList < Point >() ĊĊĠĠĠĠĠĠĠ Ġ// Ġoptional Ġremove Ġduplicates ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= ĠHashSet ( point ArrayList ) ĊĠĠĠĠĠĠĠ Ġval Ġpoint Array Set Ġ= ĠArrayList ( set ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġk Ġhas Ġto Ġbe Ġgreater Ġthan Ġ 3 Ġto Ġexecute Ġthe Ġalgorithm ĊĠĠĠĠĠĠĠ Ġvar Ġkk Ġ= Ġk . coerce At Least ( 3 ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġreturn ĠPoints Ġif Ġalready ĠCon c ave ĠH ull ĊĠĠĠĠĠĠĠ Ġif Ġ( point Array Set . size Ġ< Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġpoint Array Set ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthat Ġk Ġneighbors Ġcan Ġbe Ġfound ĊĠĠĠĠĠĠĠ Ġkk Ġ= Ġkk . coerce At Most ( point Array Set . size Ġ- Ġ 1 ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġfind Ġfirst Ġpoint Ġand Ġremove Ġfrom Ġpoint Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġfirst Point Ġ= Ġfind Min Y Point ( point Array Set ) ĊĠĠĠĠĠĠĠ Ġconc ave H ull . add ( first Point ) ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent Point Ġ= Ġfirst Point ĊĠĠĠĠĠĠĠ Ġpoint Array Set . remove ( first Point ) ĊĊĠĠĠĠĠĠĠ Ġvar Ġprevious Angle Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠ Ġvar Ġstep Ġ= Ġ 2 ĊĠĠĠĠĠĠĠ Ġwhile Ġ(( current Point Ġ!== Ġfirst Point Ġ|| Ġstep Ġ== Ġ 2 ) Ġ&& Ġpoint Array Set . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġafter Ġ 3 Ġsteps Ġadd Ġfirst Ġpoint Ġto Ġdataset , Ġotherwise Ġh ull Ġcannot Ġbe Ġclosed ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( step Ġ== Ġ 5 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Array Set . add ( first Point ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġget Ġk Ġnearest Ġneighbors Ġof Ġcurrent Ġpoint ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk Nearest Points Ġ= Ġk Nearest Neighbors ( point Array Set , Ġcurrent Point , Ġkk ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsort Ġpoints Ġby Ġangle Ġclock wise ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġclock wise Points Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠsortBy Angle ( k Nearest Points , Ġcurrent Point , Ġprevious Angle ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġclock wise Ġangle Ġnearest Ġneighbors Ġare Ġcandidates Ġfor Ġconc ave Ġh ull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġits Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( its Ġ&& Ġi Ġ< Ġclock wise Points . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġlast Point Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( clock wise Points [ i ] Ġ=== Ġfirst Point ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Point Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġpossible Ġnew Ġconc ave Ġh ull Ġpoint Ġintersect s Ġwith Ġothers ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġits Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! its Ġ&& Ġj Ġ< Ġconc ave H ull . size Ġ- Ġlast Point ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġits Ġ= Ġintersect ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Point , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġclock wise Points [ i ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconc ave H ull [ step Ġ- Ġ 2 Ġ- Ġj ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconc ave H ull [ step Ġ- Ġ 1 Ġ- Ġj ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthere Ġis Ġno Ġcandidate Ġincrease Ġk Ġ- Ġtry Ġagain ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( its ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcalculate Con c ave H ull ( point ArrayList , Ġk Ġ+ Ġ 1 ); ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġadd Ġcandidate Ġto Ġconc ave Ġh ull Ġand Ġremove Ġfrom Ġdataset ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Point Ġ= Ġclock wise Points [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġconc ave H ull . add ( current Point ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Array Set . remove ( current Point ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcalculate Ġlast Ġangle Ġof Ġthe Ġconc ave Ġh ull Ġline ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprevious Angle Ġ= Ġcalculate Angle ( conc ave H ull [ step Ġ- Ġ 1 ], Ġconc ave H ull [ step Ġ- Ġ 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstep ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠCheck Ġif Ġall Ġpoints Ġare Ġcontained Ġin Ġthe Ġconc ave Ġh ull ĊĠĠĠĠĠĠĠ Ġvar Ġinside Check Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġpoint Array Set . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( inside Check Ġ&& Ġi Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinside Check Ġ= Ġpoint In Polygon ( point Array Set [ i ], Ġconc ave H ull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi -- ĊĠĠĠĠĠĠĠ Ġ} Ċ Ċ // ĠĠĠĠĠĠĠĠ Ġif Ġnot Ġall Ġpoints Ġinside Ġ- Ġ Ġtry Ġagain ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(! inside Check ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcalculate Con c ave H ull ( point ArrayList , Ġk Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġconc ave H ull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ