package Ġpl . sh ock ah . god wit . geom . polygon Ċ Ċ import Ġpl . sh ock ah . god wit . geom . Triangle Ċ import Ġpl . sh ock ah . god wit . geom . Vec 2 Ċ Ċ /* Ċ Ġ* Ġcode Ġtaken Ġfrom ĠS lick 2 D Ġ- Ġhttp :// slick . nin jac ave . com / Ċ Ġ*/ Ċ class ĠBasic Tri ang ulator Ġ: ĠTri ang ulator Ġ{ Ċ ĉ comp anion Ġobject Ġ{ Ċĉ ĉ private Ġconst Ġval ĠEPS ILON Ġ= Ġ 0 . 0 0 0 0 0 0 0 0 0 1 f Ċ ĉ } ĊĊ ĉ override Ġfun Ġtri ang ulate ( points : ĠList < Vec 2 >): ĠList < Triangle >? Ġ{ Ċĉ ĉ val Ġprocess Ġ= ĠProcess ( points ) Ċĉ ĉ return Ġif Ġ( process . tri ang ulate ()) Ġprocess . tris Ġelse Ġnull Ċ ĉ } ĊĊ ĉ inner Ġclass ĠProcess ( Ċĉĉ ĉ val Ġpoints : ĠList < Vec 2 > Ċ ĉ ) Ġ{ Ċĉ ĉ val Ġtr is : ĠMutable List < Triangle > Ġ= Ġmutable ListOf () Ċĉ ĉ private Ġvar Ġtried : ĠBoolean Ġ= Ġfalse ĊĊĉ ĉ val Ġtriangle Count : ĠInt Ċĉĉ ĉ get () Ġ{ Ċĉĉĉ ĉ if Ġ(! tri ed ) Ċĉĉĉĉ ĉ tri ang ulate () Ċĉĉĉ ĉ return Ġtr is . size Ġ/ Ġ 3 Ċĉĉ ĉ } ĊĊĉ ĉ fun Ġtri ang ulate (): ĠBoolean Ġ{ Ċĉĉ ĉ tri ed Ġ= Ġtrue Ċĉĉ ĉ return Ġprocess ( points , Ġtr is ) Ċĉ ĉ } ĊĊĉ ĉ private Ġfun Ġarea ( contour : ĠList < Vec 2 >): ĠFloat Ġ{ Ċĉĉ ĉ val Ġn Ġ= Ġcontour . size ĊĊĉĉ ĉ var ĠA Ġ= Ġ 0 f Ċĉĉ ĉ var Ġp Ġ= Ġn Ġ- Ġ 1 Ċĉĉ ĉ var Ġq Ġ= Ġ 0 Ċĉĉ ĉ while Ġ( q Ġ< Ġn ) Ġ{ Ċĉĉĉ ĉ val Ġcontour P Ġ= Ġcontour [ p ] Ċĉĉĉ ĉ val Ġcontour Q Ġ= Ġcontour [ q ] Ċĉĉĉ ĉ A Ġ+= Ġcontour P . x Ġ* Ġcontour Q . y Ġ- Ġcontour Q . x Ġ* Ġcontour P . y Ċĉĉĉ ĉ p Ġ= Ġq ++ Ċĉĉ ĉ } Ċĉĉ ĉ return ĠA Ġ* Ġ 0 . 5 f Ċĉ ĉ } ĊĊĉ ĉ private Ġfun Ġinside Triangle ( Ax : ĠDouble , ĠA y : ĠDouble , ĠB x : ĠDouble , ĠBy : ĠDouble , ĠC x : ĠDouble , ĠCy : ĠDouble , ĠPx : ĠDouble , ĠPy : ĠDouble ): ĠBoolean Ġ{ Ċĉĉ ĉ val Ġax : ĠDouble Ġ= ĠC x Ġ- ĠB x Ċĉĉ ĉ val Ġay : ĠDouble Ġ= ĠCy Ġ- ĠBy Ċĉĉ ĉ val Ġbx : ĠDouble Ġ= ĠAx Ġ- ĠC x Ċĉĉ ĉ val Ġby : ĠDouble Ġ= ĠA y Ġ- ĠCy Ċĉĉ ĉ val Ġcx : ĠDouble Ġ= ĠB x Ġ- ĠAx Ċĉĉ ĉ val Ġcy : ĠDouble Ġ= ĠBy Ġ- ĠA y Ċĉĉ ĉ val Ġa px : ĠDouble Ġ= ĠPx Ġ- ĠAx Ċĉĉ ĉ val Ġa py : ĠDouble Ġ= ĠPy Ġ- ĠA y Ċĉĉ ĉ val Ġb px : ĠDouble Ġ= ĠPx Ġ- ĠB x Ċĉĉ ĉ val Ġb py : ĠDouble Ġ= ĠPy Ġ- ĠBy Ċĉĉ ĉ val Ġc px : ĠDouble Ġ= ĠPx Ġ- ĠC x Ċĉĉ ĉ val Ġc py : ĠDouble Ġ= ĠPy Ġ- ĠCy Ċĉĉ ĉ val Ġc CROSS ap : ĠDouble Ġ= Ġcx Ġ* Ġa py Ġ- Ġcy Ġ* Ġa px Ċĉĉ ĉ val Ġb CROSS cp : ĠDouble Ġ= Ġbx Ġ* Ġc py Ġ- Ġby Ġ* Ġc px Ċĉĉ ĉ val Ġa CROSS bp : ĠDouble Ġ= Ġax Ġ* Ġb py Ġ- Ġay Ġ* Ġb px Ċĉĉ ĉ return Ġa CROSS bp Ġ>= Ġ 0 f Ġ&& Ġb CROSS cp Ġ>= Ġ 0 f Ġ&& Ġc CROSS ap Ġ>= Ġ 0 f Ċĉ ĉ } ĊĊĉ ĉ private Ġfun Ġsn ip ( contour : ĠList < Vec 2 >, Ġu : ĠInt , Ġv : ĠInt , Ġw : ĠInt , Ġn : ĠInt , ĠV : ĠInt Array ): ĠBoolean Ġ{ Ċĉĉ ĉ var Ġp : ĠInt Ġ= Ġ 0 Ċĉĉ ĉ val ĠAx : ĠDouble Ġ= Ġcontour [ V [ u ]]. x . toDouble () Ċĉĉ ĉ val ĠA y : ĠDouble Ġ= Ġcontour [ V [ u ]]. y . toDouble () Ċĉĉ ĉ val ĠB x : ĠDouble Ġ= Ġcontour [ V [ v ]]. x . toDouble () Ċĉĉ ĉ val ĠBy : ĠDouble Ġ= Ġcontour [ V [ v ]]. y . toDouble () Ċĉĉ ĉ val ĠC x : ĠDouble Ġ= Ġcontour [ V [ w ]]. x . toDouble () Ċĉĉ ĉ val ĠCy : ĠDouble Ġ= Ġcontour [ V [ w ]]. y . toDouble () Ċĉĉ ĉ var ĠPx : ĠDouble Ċĉĉ ĉ var ĠPy : ĠDouble ĊĊĉĉ ĉ if Ġ( EPS ILON Ġ> Ġ( Bx Ġ- ĠAx ) Ġ* Ġ( Cy Ġ- ĠA y ) Ġ- Ġ( By Ġ- ĠA y ) Ġ* Ġ( Cx Ġ- ĠAx )) Ċĉĉĉ ĉ return Ġfalse ĊĊĉĉ ĉ while Ġ( p Ġ< Ġn ) Ġ{ Ċĉĉĉ ĉ if Ġ( p Ġ== Ġu Ġ|| Ġp Ġ== Ġv Ġ|| Ġp Ġ== Ġw ) Ġ{ Ċĉĉĉĉ ĉ p ++ Ċĉĉĉĉ ĉ continue Ċĉĉĉ ĉ } Ċĉĉĉ ĉ Px Ġ= Ġcontour [ V [ p ]]. x . toDouble () Ċĉĉĉ ĉ Py Ġ= Ġcontour [ V [ p ]]. y . toDouble () Ċĉĉĉ ĉ if Ġ( inside Triangle ( Ax , ĠA y , ĠB x , ĠBy , ĠC x , ĠCy , ĠPx , ĠPy )) Ċĉĉĉĉ ĉ return Ġfalse Ċĉĉĉ ĉ p ++ Ċĉĉ ĉ } ĊĊĉĉ ĉ return Ġtrue Ċĉ ĉ } ĊĊĉ ĉ private Ġfun Ġprocess ( contour : ĠList < Vec 2 >, Ġresult : ĠMutable List < Triangle >): ĠBoolean Ġ{ Ċĉĉ ĉ result . clear () ĊĊĉĉ ĉ val Ġn Ġ= Ġcontour . size Ċĉĉ ĉ if Ġ( n Ġ< Ġ 3 ) Ċĉĉĉ ĉ return Ġfalse ĊĊĉĉ ĉ val ĠV Ġ= ĠInt Array ( n ) ĊĊĉĉ ĉ if Ġ( 0 f Ġ< Ġarea ( contour )) Ġ{ Ċĉĉĉ ĉ for Ġ( v Ġin Ġ 0 Ġuntil Ġn ) Ġ{ Ċĉĉĉĉ ĉ V [ v ] Ġ= Ġv Ċĉĉĉ ĉ } Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ for Ġ( v Ġin Ġ 0 Ġuntil Ġn ) Ġ{ Ċĉĉĉĉ ĉ V [ v ] Ġ= Ġn Ġ- Ġ 1 Ġ- Ġv Ċĉĉĉ ĉ } Ċĉĉ ĉ } ĊĊĉĉ ĉ var Ġnv Ġ= Ġn Ċĉĉ ĉ var Ġcount Ġ= Ġ 2 Ġ* Ġnv ĊĊĉĉ ĉ var Ġv Ġ= Ġnv Ġ- Ġ 1 Ċĉĉ ĉ while Ġ( nv Ġ> Ġ 2 ) Ġ{ Ċĉĉĉ ĉ if Ġ( 0 Ġ>= Ġcount --) Ċĉĉĉĉ ĉ return Ġfalse ĊĊĉĉĉ ĉ var Ġu Ġ= Ġv Ċĉĉĉ ĉ if Ġ( nv Ġ<= Ġu ) Ċĉĉĉĉ ĉ u Ġ= Ġ 0 Ċĉĉĉ ĉ v Ġ= Ġu Ġ+ Ġ 1 Ċĉĉĉ ĉ if Ġ( nv Ġ<= Ġv ) Ċĉĉĉĉ ĉ v Ġ= Ġ 0 Ċĉĉĉ ĉ var Ġw Ġ= Ġv Ġ+ Ġ 1 Ċĉĉĉ ĉ if Ġ( nv Ġ<= Ġw ) Ċĉĉĉĉ ĉ w Ġ= Ġ 0 ĊĊĉĉĉ ĉ if Ġ( sn ip ( contour , Ġu , Ġv , Ġw , Ġnv , ĠV )) Ġ{ Ċĉĉĉĉ ĉ val Ġa : ĠInt Ġ= ĠV [ u ] Ċĉĉĉĉ ĉ val Ġb : ĠInt Ġ= ĠV [ v ] Ċĉĉĉĉ ĉ val Ġc : ĠInt Ġ= ĠV [ w ] Ċĉĉĉĉ ĉ var Ġs : ĠInt Ġ= Ġv Ċĉĉĉĉ ĉ var Ġt : ĠInt Ġ= Ġv Ġ+ Ġ 1 ĊĊĉĉĉĉ ĉ result . add ( Triangle ( contour [ a ], Ġcontour [ b ], Ġcontour [ c ])) ĊĊĉĉĉĉ ĉ while Ġ( t Ġ< Ġnv ) Ġ{ Ċĉĉĉĉĉ ĉ V [ s ] Ġ= ĠV [ t ] Ċĉĉĉĉĉ ĉ s ++ Ċĉĉĉĉĉ ĉ t ++ Ċĉĉĉĉ ĉ } Ċĉĉĉĉ ĉ nv -- Ċĉĉĉĉ ĉ count Ġ= Ġ 2 Ġ* Ġnv Ċĉĉĉ ĉ } Ċĉĉ ĉ } Ċĉĉ ĉ return Ġtrue Ċĉ ĉ } Ċ ĉ } Ċ }