import Ġkotlin . math . pow Ċ Ċ class ĠVector ( var Ġx : ĠDouble , Ġvar Ġy : ĠDouble ) Ċ Ċ /** Ċ Ġ* Ġ@ param Ġpoly 1 , Ġpoly 2 ĠThe Ġtwo Ġpoly gons Ġdescribed Ġas Ġarrays Ġof Ġpoints Ġas ĠVector s Ċ Ġ* Ġ ĠNote : ĠThe Ġpoints Ġlist Ġmust Ġgo Ġin Ġsequence Ġaround Ġthe Ġpolygon Ċ Ġ* Ġ@ param Ġmax Dist ĠThe Ġmaximum Ġdistance Ġbetween Ġany Ġtwo Ġpoints Ġof Ġany Ġtwo Ġpoly gons Ġthat Ġcan Ġbe Ġtouch ing Ċ Ġ* Ġ ĠIf Ġthis Ġnull Ġthen Ġthe Ġoptimization Ġcheck Ġthat Ġuses Ġit Ġwill Ġbe Ġskipped Ċ Ġ*/ Ċ fun Ġhas Col li ded ( poly 1 : ĠArray < Vector >, Ġpoly 2 : ĠArray < Vector >, Ġmax Dist : ĠDouble ?= null ): ĠBoolean Ġ{ ĊĠĠĠ Ġ// ĠDo Ġan Ġoptimization Ġcheck Ġusing Ġthe Ġmax Dist ĊĠĠĠ Ġif Ġ( max Dist Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(( poly 1 [ 1 ]. x Ġ- Ġpoly 2 [ 0 ]. x ). pow ( 2 ) Ġ+ Ġ( poly 1 [ 1 ]. y Ġ- Ġpoly 2 [ 0 ]. y ). pow ( 2 ) Ġ<= Ġmax Dist . pow ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCollision Ġis Ġpossible Ġso Ġrun ĠS AT Ġon Ġthe Ġpol ys ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġrun SAT ( poly 1 , Ġpoly 2 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠNo Ġmax Dist Ġso Ġrun ĠS AT Ġon Ġthe Ġpol ys ĊĠĠĠĠĠĠĠ Ġreturn Ġrun SAT ( poly 1 , Ġpoly 2 ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġrun SAT ( poly 1 : ĠArray < Vector >, Ġpoly 2 : ĠArray < Vector >): ĠBoolean Ġ{ ĊĠĠĠ Ġ// ĠImplements Ġthe Ġactual ĠS AT Ġalgorithm ĊĠĠĠ Ġval Ġedges Ġ= Ġpoly To Edges ( poly 1 ) Ġ+ Ġpoly To Edges ( poly 2 ) ĊĠĠĠ Ġval Ġaxes Ġ= ĠArray ( edges . size , Ġ{ Ġindex Ġ-> Ġor thogonal ( edges [ index ]) }) ĊĊĠĠĠ Ġfor Ġ( axis Ġin Ġaxes ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! overlap ( project ( poly 1 , Ġaxis ), Ġproject ( poly 2 , Ġaxis ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġpol ys Ġdon 't Ġoverlap Ġon Ġthis Ġaxis Ġso Ġthey Ġcan 't Ġbe Ġtouch ing ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠThe Ġpol ys Ġoverlap Ġon Ġall Ġaxes Ġso Ġthey Ġmust Ġbe Ġtouch ing ĊĠĠĠ Ġreturn Ġtrue Ċ } Ċ Ċ /** Ċ Ġ* ĠReturns Ġa Ġvector Ġgoing Ġfrom Ġpoint 1 Ġto Ġpoint 2 Ċ Ġ*/ Ċ fun Ġedge Vector ( point 1 : ĠVector , Ġpoint 2 : ĠVector ) Ġ= ĠVector ( point 2 . x Ġ- Ġpoint 1 . x , Ġpoint 2 . y Ġ- Ġpoint 1 . y ) Ċ Ċ /** Ċ Ġ* ĠReturns Ġan Ġarray Ġof Ġthe Ġedges Ġof Ġthe Ġpoly Ġas Ġvectors Ċ Ġ*/ Ċ fun Ġpoly To Edges ( poly : ĠArray < Vector >) Ġ= ĠArray ( poly . size , ĊĠĠĠĠĠĠĠ Ġ{ Ġindex Ġ-> Ġedge Vector ( poly [ index ], Ġpoly [( index Ġ+ Ġ 1 ) Ġ% Ġpoly . size ]) Ġ}) Ċ Ċ /** Ċ Ġ* ĠReturns Ġa Ġnew Ġvector Ġwhich Ġis Ġor thogonal Ġto Ġthe Ġgiven Ġvector Ċ Ġ*/ Ċ fun Ġor thogonal ( vector : ĠVector ) Ġ= ĠVector ( vector . y , Ġ- vector . x ) Ċ Ċ /** Ċ Ġ* ĠReturns Ġthe Ġdot Ġ( or Ġscalar ) Ġproduct Ġof Ġthe Ġtwo Ġvectors Ċ Ġ*/ Ċ fun Ġdot Product ( vector 1 : ĠVector , Ġvector 2 : ĠVector ) Ġ= Ġvector 1 . x Ġ* Ġvector 2 . x Ġ+ Ġvector 1 . y Ġ* Ġvector 2 . y Ċ Ċ /** Ċ Ġ* ĠReturns Ġa Ġvector Ġshowing Ġhow Ġmuch Ġof Ġthe Ġpoly Ġlies Ġalong Ġthe Ġaxis Ċ Ġ*/ Ċ fun Ġproject ( poly : ĠArray < Vector >, Ġaxis : ĠVector ): ĠVector Ġ{ ĊĠĠĠ Ġval Ġdots Ġ= ĠArray ( poly . size , Ġ{ Ġindex Ġ-> Ġdot Product ( poly [ index ], Ġaxis ) Ġ}) ĊĠĠĠ Ġreturn ĠVector ( dots . min () !! , Ġdots . max () !! ) Ċ } Ċ Ċ /** Ċ Ġ* ĠReturns Ġa Ġboolean Ġindicating Ġif Ġthe Ġtwo Ġprojection s Ġoverlap Ċ Ġ*/ Ċ fun Ġoverlap ( projection 1 : ĠVector , Ġprojection 2 : ĠVector ) Ġ= Ġprojection 1 . x Ġ<= Ġprojection 2 . y Ġ&& ĊĠĠĠĠĠĠĠ Ġprojection 2 . x Ġ<= Ġprojection 1 . y