/* Ċ Ġ* ĠCopyright ĠÂ© Ġ 2 0 2 1 ĠE no ve a Ġ( fab ien . me ur isse @ en ove a . net ) Ċ Ġ* Ċ Ġ* ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* ĠĠĠĠ Ġhttp :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ*/ Ċ package Ġdil iv ia . s 2 . edge Ċ Ċ import Ġdil iv ia . math . Double Type Ċ import Ġdil iv ia . math . vectors . times Ċ import Ġdil iv ia . s 2 . S 1 Angle Ċ import Ġdil iv ia . s 2 . S 1 Angle . Companion . times Ċ import Ġdil iv ia . s 2 . S 2 Point Ċ import Ġdil iv ia . s 2 . S 2 Pred icates Ċ import Ġdil iv ia . s 2 . S 2 Random Ċ import Ġdil iv ia . s 2 . edge . S 2 Edge Cross ings . intersection Method Counter Ċ import Ġmu . Kotlin Logging Ċ import Ġorg . assertj . core . api . Assertions . assertThat Ċ import Ġorg . junit . jupiter . api . Test Ċ import Ġjava . lang . Math . pow Ċ import Ġkotlin . math . pow ĊĊ Ċ class ĠS 2 Edge Cross ings UnitTest Ġ{ ĊĊĠĠĠ Ġprivate Ġval Ġlogger Ġ= ĠKotlin Logging . logger Ġ{ Ġ} ĊĊĠĠĠ Ġfun Ġprint Intersection Stats () Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġtotal Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġtotals Ġ= ĠInt Array ( S 2 Edge Cross ings . Intersection Method . values (). size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin ĠS 2 Edge Cross ings . Intersection Method . values ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtotal Ġ+= Ġintersection Method Counter [ i ] Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtotals [ i . ordinal ] Ġ= Ġtotal ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprintln ("% 1 0 s Ġ% 1 6 s Ġ% 1 6 s Ġ Ġ% 6 s ". format (" Method ", Ġ" Suc cesses ", Ġ" Attempts ", Ġ" Rate ")) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin ĠS 2 Edge Cross ings . Intersection Method . values ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( intersection Method Counter [ i ] Ġ== Ġnull Ġ|| Ġintersection Method Counter [ i ] Ġ== Ġ 0 ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"% 1 0 s Ġ% 9 d Ġ% 5 . 1 f %% Ġ% 9 d Ġ% 5 . 1 f %% Ġ Ġ% 5 . 1 f %% ". format ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi . methodName , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġintersection Method Counter [ i ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 0 0 . 0 Ġ* Ġintersection Method Counter [ i ] !! Ġ/ Ġtotal , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtotals [ i . ordinal ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 0 0 . 0 Ġ* Ġtotals [ i . ordinal ] Ġ/ Ġtotal , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 0 0 . 0 Ġ* Ġintersection Method Counter [ i ] !! Ġ/ Ġtotals [ i . ordinal ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin ĠS 2 Edge Cross ings . Intersection Method . values ()) Ġintersection Method Counter [ i ] Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠThis Ġreturns Ġthe Ġtrue Ġintersection Ġpoint Ġof Ġtwo Ġline Ġsegments Ġ( a 0 , a 1 ) Ġand ĊĠĠĠ Ġ// Ġ( b 0 , b 1 ), Ġwith Ġa Ġrelative Ġerror Ġof Ġat Ġmost ĠDouble Type . epsilon Ġin Ġeach Ġcoordinate ĊĠĠĠ Ġ// Ġ( i . e ., Ġone Ġul p , Ġor Ġtwice Ġthe Ġdouble Ġprecision Ġrounding Ġerror ). ĊĠĠĠ Ġfun Ġget Intersection Exact ( a 0 : ĠS 2 Point , Ġa 1 : ĠS 2 Point , Ġb 0 : ĠS 2 Point , Ġb 1 : ĠS 2 Point ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= ĠS 2 Edge Cross ings . get Intersection Exact ( a 0 , Ġa 1 , Ġb 0 , Ġb 1 ) ĊĠĠĠĠĠĠĠ Ġif Ġ( x . dot Prod (( a 0 Ġ+ Ġa 1 ) Ġ+ Ġ( b 0 Ġ+ Ġb 1 )) Ġ< Ġ 0 ) Ġx Ġ= Ġ- x ĊĠĠĠĠĠĠĠ Ġreturn Ġx ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠThe Ġapproximate Ġmaximum Ġerror Ġin ĠGet Distance () Ġfor Ġsmall Ġdistances . ĊĠĠĠ Ġval Ġk Get Distance Abs Error Ġ= ĠS 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon ) ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġintersection Error () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠWe Ġrepeatedly Ġconstruct Ġtwo Ġedges Ġthat Ġcross Ġnear Ġa Ġrandom Ġpoint Ġ" p ", Ġand ĊĠĠĠĠĠĠĠ Ġ// Ġmeasure Ġthe Ġdistance Ġfrom Ġthe Ġactual Ġintersection Ġpoint Ġ" x " Ġto Ġthe ĊĠĠĠĠĠĠĠ Ġ// Ġexact Ġintersection Ġpoint Ġand Ġalso Ġto Ġthe Ġedges . ĊĊĠĠĠĠĠĠĠ Ġvar Ġmax _ point _ dist : ĠS 1 Angle Ġ= ĠS 1 Angle . zero () ĊĠĠĠĠĠĠĠ Ġvar Ġmax _ edge _ dist : ĠS 1 Angle Ġ= ĠS 1 Angle . zero () ĊĠĠĠĠĠĠĠ Ġfor Ġ( iter Ġin Ġ 0 Ġuntil Ġ 5 0 0 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġconstruct Ġtwo Ġedges ĠAB Ġand ĠCD Ġthat Ġintersect Ġnear Ġ" p ". Ġ ĠThe Ġangle ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbetween ĠAB Ġand ĠCD Ġ( exp ressed Ġas Ġa Ġslope ) Ġis Ġchosen Ġrandomly Ġbetween ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 1 e - 1 5 Ġand Ġ 1 e 1 5 Ġsuch Ġthat Ġits Ġlog arith m Ġis Ġuniform ly Ġdistributed . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSimilar ly , Ġtwo Ġedge Ġlengths Ġapproximately Ġbetween Ġ 1 e - 1 5 Ġand Ġ 1 Ġare ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġchosen . Ġ ĠThe Ġedge Ġendpoints Ġare Ġchosen Ġsuch Ġthat Ġthey Ġare Ġoften Ġvery ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġclose Ġto Ġthe Ġother Ġedge Ġ( i . e ., Ġbare ly Ġcross ing ). Ġ ĠT aken Ġtogether Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġensures Ġthat Ġwe Ġtest Ġboth Ġlong Ġand Ġvery Ġshort Ġedges Ġthat Ġintersect Ġat ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġboth Ġlarge Ġand Ġvery Ġsmall Ġangles . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSometimes Ġthe Ġedges Ġwe Ġgenerate Ġwill Ġnot Ġactually Ġcross , Ġin Ġwhich Ġcase ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġsimply Ġtry Ġagain . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġ( p , Ġd 1 , Ġd 2 ) Ġ= ĠS 2 Random . random Frame () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġslope Ġ= Ġ 1 e - 1 5 Ġ* Ġ 1 e 3 0 . pow ( S 2 Random . random Double ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd 2 Ġ= Ġ( d 1 Ġ+ Ġslope Ġ* Ġd 2 ). normalize () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġa : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġb : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġd : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġexpected : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġab Len Ġ= Ġ 1 e - 1 5 . pow ( S 2 Random . random Double ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcd Len Ġ= Ġ 1 e - 1 5 . pow ( S 2 Random . random Double ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġa Fraction Ġ= Ġ 1 e - 5 . pow ( S 2 Random . random Double ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 2 Random . one In ( 2 )) Ġa Fraction Ġ= Ġ 1 Ġ- Ġa Fraction ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc Fraction Ġ= Ġ 1 e - 5 . pow ( S 2 Random . random Double ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 2 Random . one In ( 2 )) Ġc Fraction Ġ= Ġ 1 Ġ- Ġc Fraction ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġ( p Ġ- Ġa Fraction Ġ* Ġab Len Ġ* Ġd 1 ). normalize () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġ( p Ġ+ Ġ( 1 Ġ- Ġa Fraction ) Ġ* Ġab Len Ġ* Ġd 1 ). normalize () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġ( p Ġ- Ġc Fraction Ġ* Ġcd Len Ġ* Ġd 2 ). normalize () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= Ġ( p Ġ+ Ġ( 1 Ġ- Ġc Fraction ) Ġ* Ġcd Len Ġ* Ġd 2 ). normalize () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected Ġ= ĠS 2 Edge Cross ings . get Intersection Exact ( a , Ġb , Ġc , Ġd ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( S 2 Edge Cross ings . cross ing Sign ( a , Ġb , Ġc , Ġd ) Ġ<= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ> ĠS 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ> ĠS 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠEach Ġconstructed Ġedge Ġshould Ġbe Ġat Ġmost Ġ 1 . 5 Ġ* ĠDouble Type . epsilon Ġaway Ġfrom Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġoriginal Ġpoint ĠP . ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ). is LessThan OrEqualTo ( S 1 Angle . radians ( 1 . 5 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ). is LessThan OrEqualTo ( S 1 Angle . radians ( 1 . 5 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠVerify Ġthat Ġthe Ġexpected Ġintersection Ġpoint Ġis Ġclose Ġto Ġboth Ġedges Ġand ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġalso Ġclose Ġto Ġthe Ġoriginal Ġpoint ĠP . Ġ Ġ( It Ġmight Ġnot Ġbe Ġvery Ġclose Ġto ĠP ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġangle Ġbetween Ġthe Ġedges Ġis Ġvery Ġsmall .) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ). is LessThan OrEqualTo ( S 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Dist ances . get Distance ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ). is LessThan OrEqualTo ( S 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon ) Ġ+ Ġk Get Distance Abs Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 1 Angle ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexpected , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ). is LessThan OrEqualTo ( S 1 Angle . radians ( 3 Ġ* ĠDouble Type . epsilon Ġ/ Ġslope ) Ġ+ ĠS 2 Edge Cross ings . k Intersection Error ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNow Ġwe Ġactually Ġtest Ġthe ĠGet Intersection () Ġmethod . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġactual Ġ= ĠS 2 Edge Cross ings . get Intersection ( a , Ġb , Ġc , Ġd ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdist _ ab Ġ= ĠS 2 Edge Dist ances . get Distance ( actual , Ġa , Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdist _ cd Ġ= ĠS 2 Edge Dist ances . get Distance ( actual , Ġc , Ġd ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( dist _ ab ). is LessThan OrEqualTo ( S 2 Edge Cross ings . k Intersection Error Ġ+ Ġk Get Distance Abs Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( dist _ cd ). is LessThan OrEqualTo ( S 2 Edge Cross ings . k Intersection Error Ġ+ Ġk Get Distance Abs Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax _ edge _ dist Ġ= Ġmax Of ( max _ edge _ dist , Ġmax Of ( dist _ ab , Ġdist _ cd )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint _ dist Ġ= ĠS 1 Angle ( expected , Ġactual ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( point _ dist ). is LessThan OrEqualTo ( S 2 Edge Cross ings . k Intersection Error ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax _ point _ dist Ġ= Ġmax Of ( max _ point _ dist , Ġpoint _ dist ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprint Intersection Stats () ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Max Ġdistance Ġto Ġeither Ġedge Ġbeing Ġintersect ed : Ġ${ max _ edge _ dist . radians }" Ġ} ĊĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Maximum Ġdistance Ġto Ġexpected Ġintersection Ġpoint : Ġ${ max _ point _ dist . radians }" Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠCh oo ses Ġa Ġpoint Ġin Ġthe ĠXY Ġplane Ġthat Ġis Ġseparated Ġfrom ĠX Ġby Ġat Ġleast Ġ 1 e - 1 5 ĊĠĠĠ Ġ// Ġ( to Ġavoid Ġchoosing Ġtoo Ġmany Ġduplicate Ġpoints ) Ġand Ġby Ġat Ġmost ĠPi / 2 Ġ- Ġ 1 e - 3 ĊĠĠĠ Ġ// Ġ( to Ġavoid Ġnearly - di ame tric Ġedges , Ġsince Ġthe Ġtest Ġbelow Ġis Ġnot Ġs oph istic ated ĊĠĠĠ Ġ// Ġenough Ġto Ġtest Ġsuch Ġedges ). ĊĠĠĠ Ġfun Ġchoose Sem ic ircle Point ( x : ĠS 2 Point , Ġy : ĠS 2 Point ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsign Ġ= Ġ( 2 Ġ* ĠS 2 Random . random Int ( 2 )) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġ( x Ġ+ Ġsign Ġ* Ġ 1 e 3 Ġ* Ġpow ( 1 e - 1 8 , ĠS 2 Random . random Double ()) Ġ* Ġy ). normalize () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġgr az ing Inter sections () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠThis Ġtest Ġchoose Ġ 5 Ġpoints Ġalong Ġa Ġgreat Ġcircle Ġ( i . e ., Ġas Ġcol linear Ġas ĊĠĠĠĠĠĠĠ Ġ// Ġpossible ), Ġand Ġuses Ġthem Ġto Ġconstruct Ġan Ġedge ĠAB Ġand Ġa Ġtriangle ĠC DE Ġsuch ĊĠĠĠĠĠĠĠ Ġ// Ġthat ĠCD Ġand ĠCE Ġboth Ġcross ĠAB . Ġ ĠIt Ġthen Ġchecks Ġthat Ġthe Ġintersection ĊĠĠĠĠĠĠĠ Ġ// Ġpoints Ġreturned Ġby ĠGet Intersection () Ġhave Ġthe Ġcorrect Ġrelative Ġordering ĊĠĠĠĠĠĠĠ Ġ// Ġalong ĠAB Ġ( to Ġwithin Ġk Intersection Error ). ĊĠĠĠĠĠĠĠ Ġfor Ġ( iter Ġin Ġ 0 Ġuntil Ġ 1 0 0 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( x , Ġy , Ġ_) Ġ= ĠS 2 Random . random Frame () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġa : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġb : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġd : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġe : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġab : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġchoose Sem ic ircle Point ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġchoose Sem ic ircle Point ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġchoose Sem ic ircle Point ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= Ġchoose Sem ic ircle Point ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġe Ġ= Ġchoose Sem ic ircle Point ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġab Ġ= Ġ( a Ġ- Ġb ). cross Prod ( a Ġ+ Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( ab . norm () Ġ< Ġ 5 0 Ġ* ĠDouble Type . epsilon Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Cross ings . cross ing Sign ( a , Ġb , Ġc , Ġd ) Ġ<= Ġ 0 Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Edge Cross ings . cross ing Sign ( a , Ġb , Ġc , Ġe ) Ġ<= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx cd Ġ= ĠS 2 Edge Cross ings . get Intersection ( a , Ġb , Ġc , Ġd ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx ce Ġ= ĠS 2 Edge Cross ings . get Intersection ( a , Ġb , Ġc , Ġe ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠEss entially Ġthis Ġsays Ġthat Ġif ĠC DE Ġand ĠC AB Ġhave Ġthe Ġsame Ġorientation , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthen ĠCD Ġand ĠCE Ġshould Ġintersect Ġalong ĠAB Ġin Ġthat Ġorder . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġab Ġ= Ġab . normalize () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 1 Angle ( xcd , Ġx ce ) Ġ> Ġ 2 Ġ* ĠS 2 Edge Cross ings . k Intersection Error ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( S 2 Pred icates . sign ( c , Ġd , Ġe ) Ġ== ĠS 2 Pred icates . sign ( c , Ġa , Ġb )). isEqualTo ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠS 2 Pred icates . sign ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġab , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx cd , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx ce ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ> Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprint Intersection Stats () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġexact Intersection Under flow () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠTests Ġthat Ġa Ġcorrect Ġintersection Ġis Ġcomputed Ġeven Ġwhen Ġtwo Ġedges Ġare ĊĠĠĠĠĠĠĠ Ġ// Ġexactly Ġcol linear Ġand Ġthe Ġnormals Ġof Ġboth Ġedges Ġunder flow Ġin Ġdouble ĊĠĠĠĠĠĠĠ Ġ// Ġprecision Ġwhen Ġnormalized Ġ( see ĠS 2 Point From Exact Ġfunction Ġfor Ġdetails ). ĊĠĠĠĠĠĠĠ Ġval Ġa 0 Ġ= ĠS 2 Point ( 1 , Ġ 0 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġa 1 Ġ= ĠS 2 Point ( 1 . 0 , Ġ 2 e - 3 0 0 , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġb 0 Ġ= ĠS 2 Point ( 1 . 0 , Ġ 1 e - 3 0 0 , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġb 1 Ġ= ĠS 2 Point ( 1 . 0 , Ġ 3 e - 3 0 0 , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( S 2 Edge Cross ings . get Intersection ( a 0 , Ġa 1 , Ġb 0 , Ġb 1 )). isEqualTo ( S 2 Point ( 1 . 0 , Ġ 1 e - 3 0 0 , Ġ 0 . 0 )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġget Intersection In variants () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠTest Ġthat Ġthe Ġresult Ġof ĠGet Intersection Ġdoes Ġnot Ġchange Ġwhen Ġthe Ġedges ĊĠĠĠĠĠĠĠ Ġ// Ġare Ġsw apped Ġand / or Ġreversed . Ġ ĠThe Ġnumber Ġof Ġiterations Ġis Ġhigh Ġbecause Ġit ĊĠĠĠĠĠĠĠ Ġ// Ġis Ġdifficult Ġto Ġgenerate Ġtest Ġcases Ġthat Ġshow Ġthat ĠCompare Edges () Ġis ĊĠĠĠĠĠĠĠ Ġ// Ġnecessary Ġand Ġcorrect , Ġfor Ġexample . ĊĠĠĠĠĠĠĠ Ġval Ġk Iter s Ġ= Ġ 5 0 0 0 Ġ// Ġ 5 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( iter Ġin Ġ 0 Ġuntil Ġk Iter s ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġa : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġb : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġd : ĠS 2 Point ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠGet Intersection Stable () Ġsorts Ġthe Ġtwo Ġedges Ġby Ġlength , Ġso Ġconstruct ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġedges Ġ( a , b ) Ġand Ġ( c , d ) Ġthat Ġcross Ġand Ġhave Ġexactly Ġthe Ġsame Ġlength . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġcan Ġbe Ġdone Ġby Ġsw apping Ġthe Ġ" x " Ġand Ġ" y " Ġcoordinates . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ[ Sw apping Ġother Ġcoordinate Ġpairs Ġdoesn 't Ġwork Ġbecause Ġit Ġchanges Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġorder Ġof Ġaddition Ġin ĠNorm 2 () Ġ== Ġ( x ** 2 Ġ+ Ġy ** 2 ) Ġ+ Ġz ** 2 .] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= ĠS 2 Random . random Point () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= ĠS 2 Random . random Point () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= ĠS 2 Point ( a [ 1 ], Ġa [ 0 ], Ġa [ 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= ĠS 2 Point ( b [ 1 ], Ġb [ 0 ], Ġb [ 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( S 2 Edge Cross ings . cross ing Sign ( a , Ġb , Ġc , Ġd ) Ġ<= Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat (( a Ġ- Ġb ). norm 2 ()). isEqualTo (( c Ġ- Ġd ). norm 2 ()) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNow Ġverify Ġthat ĠGet Intersection Ġreturns Ġexactly Ġthe Ġsame Ġresult Ġwhen ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġedges Ġare Ġsw apped Ġand / or Ġreversed . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠS 2 Edge Cross ings . get Intersection ( a , Ġb , Ġc , Ġd ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 2 Random . one In ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 2 Random . one In ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( S 2 Random . one In ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġtemp Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtemp Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( result ). isEqualTo ( S 2 Edge Cross ings . get Intersection ( a , Ġb , Ġc , Ġd )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ } ĊĊĊĊĊ