package Ġch . ober mu hl ner . k image . math Ċ Ċ import Ġkotlin . math . h ypot Ċ Ċ /** Ċ Ġ* Ġhttps :// gist . github . com / le cho / 7 6 2 7 7 3 9 Ċ Ġ*/ Ċ class ĠSpl ine Interpolator Ġprivate Ġconstructor ( private Ġval Ġm X : ĠList < Double >, Ġprivate Ġval Ġm Y : ĠList < Double >, Ġprivate Ġval Ġm M : ĠDouble Array ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInterpol ates Ġthe Ġvalue Ġof ĠY Ġ= Ġf ( X ) Ġfor Ġgiven ĠX . ĠCl amp s ĠX Ġto Ġthe Ġdomain Ġof Ġthe Ġspline . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġx ĊĠĠĠĠ Ġ* ĠThe ĠX Ġvalue . ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġinterpolated ĠY Ġ= Ġf ( X ) Ġvalue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġinterpolate ( x : ĠDouble ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠHandle Ġthe Ġboundary Ġcases . ĊĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġm X . size ĊĠĠĠĠĠĠĠ Ġif Ġ( java . lang . Double . isNaN ( x )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġx ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( x Ġ<= Ġm X [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm Y [ 0 ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( x Ġ>= Ġm X [ n Ġ- Ġ 1 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm Y [ n Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠFind Ġthe Ġindex Ġ' i ' Ġof Ġthe Ġlast Ġpoint Ġwith Ġsmaller ĠX . ĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthis Ġwill Ġbe Ġwithin Ġthe Ġspline Ġdue Ġto Ġthe Ġboundary Ġtests . ĊĠĠĠĠĠĠĠ Ġvar Ġi : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ>= Ġm X [ i Ġ+ Ġ 1 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x Ġ== Ġm X [ i ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm Y [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠPerform Ġcubic ĠH erm ite Ġspline Ġinterpolation . ĊĠĠĠĠĠĠĠ Ġval Ġh : ĠDouble Ġ= Ġm X [ i Ġ+ Ġ 1 ] Ġ- Ġm X [ i ] ĊĠĠĠĠĠĠĠ Ġval Ġt : ĠDouble Ġ= Ġ( x Ġ- Ġm X [ i ]) Ġ/ Ġh ĊĠĠĠĠĠĠĠ Ġreturn Ġ(( m Y [ i ] Ġ* Ġ( 1 Ġ+ Ġ 2 Ġ* Ġt ) Ġ+ Ġh Ġ* Ġm M [ i ] Ġ* Ġt ) Ġ* Ġ( 1 Ġ- Ġt ) Ġ* Ġ( 1 Ġ- Ġt ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġ( m Y [ i Ġ+ Ġ 1 ] Ġ* Ġ( 3 Ġ- Ġ 2 Ġ* Ġt ) Ġ+ Ġh Ġ* Ġm M [ i Ġ+ Ġ 1 ] Ġ* Ġ( t Ġ- Ġ 1 )) Ġ* Ġt Ġ* Ġt ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠFor Ġdebugging . ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstr : ĠStringBuilder Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġm X . size ĊĠĠĠĠĠĠĠ Ġstr . append ("[ ") ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstr . append (", Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstr . append (" (" ). append ( m X [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstr . append (", Ġ"). append ( m Y [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstr . append (": Ġ"). append ( m M [ i ]). append (" )") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġstr . append (" ]") ĊĠĠĠĠĠĠĠ Ġreturn Ġstr . toString () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠCreates Ġa Ġmon ot one Ġcubic Ġspline Ġfrom Ġa Ġgiven Ġset Ġof Ġcontrol Ġpoints . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġspline Ġis Ġguaranteed Ġto Ġpass Ġthrough Ġeach Ġcontrol Ġpoint Ġexactly . ĠMore over , Ġassuming Ġthe Ġcontrol Ġpoints Ġare ĊĠĠĠĠĠĠĠĠ Ġ* Ġmon otonic Ġ( Y Ġis Ġnon - de creasing Ġor Ġnon - in creasing ) Ġthen Ġthe Ġinterpolated Ġvalues Ġwill Ġalso Ġbe Ġmon otonic . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġfunction Ġuses Ġthe ĠF rit sch - Car l son Ġmethod Ġfor Ġcomputing Ġthe Ġspline Ġparameters . ĊĠĠĠĠĠĠĠĠ Ġ* Ġhttp :// en . wikipedia . org / wiki / Mon ot one _ cubic _ interpolation ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġx ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe ĠX Ġcomponent Ġof Ġthe Ġcontrol Ġpoints , Ġstrictly Ġincreasing . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġy ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe ĠY Ġcomponent Ġof Ġthe Ġcontrol Ġpoints ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ throws ĠIllegalArgumentException ĊĠĠĠĠĠĠĠĠ Ġ* Ġif Ġthe ĠX Ġor ĠY Ġarrays Ġare Ġnull , Ġhave Ġdifferent Ġlengths Ġor Ġhave Ġfewer Ġthan Ġ 2 Ġvalues . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġcreate Mon ot one Cubic Spline ( x : ĠList < Double > ?, Ġy : ĠList < Double >? ): ĠSpl ine Interpolator Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( x Ġ== Ġnull ) Ġ|| Ġ( y Ġ== Ġnull ) Ġ|| Ġ( x . size Ġ!= Ġy . size ) Ġ|| Ġ( x . size Ġ< Ġ 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException ((" There Ġmust Ġbe Ġat Ġleast Ġtwo Ġcontrol Ġ" ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġ" points Ġand Ġthe Ġarrays Ġmust Ġbe Ġof Ġequal Ġlength .")) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġx . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd : ĠDouble Array Ġ= ĠDouble Array ( n Ġ- Ġ 1 ) Ġ// Ġcould Ġoptimize Ġthis Ġout ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġm : ĠDouble Array Ġ= ĠDouble Array ( n ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCompute Ġslo pes Ġof Ġsec ant Ġlines Ġbetween Ġsuccess ive Ġpoints . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġh : ĠDouble Ġ= Ġx [ i Ġ+ Ġ 1 ] Ġ- Ġx [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( h Ġ<= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException (" The Ġcontrol Ġpoints Ġmust Ġall Ġhave Ġstrictly Ġincreasing ĠX Ġvalues .") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd [ i ] Ġ= Ġ( y [ i Ġ+ Ġ 1 ] Ġ- Ġy [ i ]) Ġ/ Ġh ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠInitialize Ġthe Ġtang ents Ġas Ġthe Ġaverage Ġof Ġthe Ġsec ants . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm [ 0 ] Ġ= Ġd [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġn Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm [ i ] Ġ= Ġ( d [ i Ġ- Ġ 1 ] Ġ+ Ġd [ i ]) Ġ* Ġ 0 . 5 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm [ n Ġ- Ġ 1 ] Ġ= Ġd [ n Ġ- Ġ 2 ] ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUpdate Ġthe Ġtang ents Ġto Ġpreserve Ġmon otonic ity . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d [ i ] Ġ== Ġ 0 . 0 ) Ġ{ Ġ// Ġsuccess ive ĠY Ġvalues Ġare Ġequal ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm [ i ] Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm [ i Ġ+ Ġ 1 ] Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa : ĠDouble Ġ= Ġm [ i ] Ġ/ Ġd [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb : ĠDouble Ġ= Ġm [ i Ġ+ Ġ 1 ] Ġ/ Ġd [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġh : ĠDouble Ġ= Ġh ypot ( a , Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( h Ġ> Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt : ĠDouble Ġ= Ġ 3 Ġ/ Ġh ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm [ i ] Ġ= Ġt Ġ* Ġa Ġ* Ġd [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm [ i Ġ+ Ġ 1 ] Ġ= Ġt Ġ* Ġb Ġ* Ġd [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠSpl ine Interpolator ( x , Ġy , Ġm ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }