const { abs , cos , sin , acos , atan2 , sqrt , pow } = Math ; function crt ( v ) { return v < 0 ? - pow ( - v , 1 / 3 ) : pow ( v , 1 / 3 ) ; } const pi = Math . PI , tau = 2 * pi , quart = pi / 2 , epsilon = 0.000001 , nMax = Number . MAX_SAFE_INTEGER || 9007199254740991 , nMin = Number . MIN_SAFE_INTEGER || - 9007199254740991 , ZERO = { x : 0 , y : 0 , z : 0 } ; const utils = { Tvalues : [ - 0.0640568928626056260850430826247450385909 , 0.0640568928626056260850430826247450385909 , - 0.1911188674736163091586398207570696318404 , 0.1911188674736163091586398207570696318404 , - 0.3150426796961633743867932913198102407864 , 0.3150426796961633743867932913198102407864 , - 0.4337935076260451384870842319133497124524 , 0.4337935076260451384870842319133497124524 , - 0.5454214713888395356583756172183723700107 , 0.5454214713888395356583756172183723700107 , - 0.6480936519369755692524957869107476266696 , 0.6480936519369755692524957869107476266696 , - 0.7401241915785543642438281030999784255232 , 0.7401241915785543642438281030999784255232 , - 0.8200019859739029219539498726697452080761 , 0.8200019859739029219539498726697452080761 , - 0.8864155270044010342131543419821967550873 , 0.8864155270044010342131543419821967550873 , - 0.9382745520027327585236490017087214496548 , 0.9382745520027327585236490017087214496548 , - 0.9747285559713094981983919930081690617411 , 0.9747285559713094981983919930081690617411 , - 0.9951872199970213601799974097007368118745 , 0.9951872199970213601799974097007368118745 , ] , Cvalues : [ 0.1279381953467521569740561652246953718517 , 0.1279381953467521569740561652246953718517 , 0.1258374563468282961213753825111836887264 , 0.1258374563468282961213753825111836887264 , 0.121670472927803391204463153476262425607 , 0.121670472927803391204463153476262425607 , 0.1155056680537256013533444839067835598622 , 0.1155056680537256013533444839067835598622 , 0.1074442701159656347825773424466062227946 , 0.1074442701159656347825773424466062227946 , 0.0976186521041138882698806644642471544279 , 0.0976186521041138882698806644642471544279 , 0.086190161531953275917185202983742667185 , 0.086190161531953275917185202983742667185 , 0.0733464814110803057340336152531165181193 , 0.0733464814110803057340336152531165181193 , 0.0592985849154367807463677585001085845412 , 0.0592985849154367807463677585001085845412 , 0.0442774388174198061686027482113382288593 , 0.0442774388174198061686027482113382288593 , 0.0285313886289336631813078159518782864491 , 0.0285313886289336631813078159518782864491 , 0.0123412297999871995468056670700372915759 , 0.0123412297999871995468056670700372915759 , ] , arcfn : function ( t , derivativeFn ) { const d = derivativeFn ( t ) ; let l = d . x * d . x + d . y * d . y ; if ( typeof d . z !== "undefined" ) { l += d . z * d . z ; } return sqrt ( l ) ; } , compute : function ( t , points , _3d ) { if ( t === 0 ) { points [ 0 ] . t = 0 ; return points [ 0 ] ; } const order = points . length - 1 ; if ( t === 1 ) { points [ order ] . t = 1 ; return points [ order ] ; } const mt = 1 - t ; let p = points ; if ( order === 0 ) { points [ 0 ] . t = t ; return points [ 0 ] ; } if ( order === 1 ) { const ret = { x : mt * p [ 0 ] . x + t * p [ 1 ] . x , y : mt * p [ 0 ] . y + t * p [ 1 ] . y , t : t , } ; if ( _3d ) { ret . z = mt * p [ 0 ] . z + t * p [ 1 ] . z ; } return ret ; } if ( order < 4 ) { let mt2 = mt * mt , t2 = t * t , a , b , c , d = 0 ; if ( order === 2 ) { p = [ p [ 0 ] , p [ 1 ] , p [ 2 ] , ZERO ] ; a = mt2 ; b = mt * t * 2 ; c = t2 ; } else if ( order === 3 ) { a = mt2 * mt ; b = mt2 * t * 3 ; c = mt * t2 * 3 ; d = t * t2 ; } const ret = { x : a * p [ 0 ] . x + b * p [ 1 ] . x + c * p [ 2 ] . x + d * p [ 3 ] . x , y : a * p [ 0 ] . y + b * p [ 1 ] . y + c * p [ 2 ] . y + d * p [ 3 ] . y , t : t , } ; if ( _3d ) { ret . z = a * p [ 0 ] . z + b * p [ 1 ] . z + c * p [ 2 ] . z + d * p [ 3 ] . z ; } return ret ; } const dCpts = JSON . parse ( JSON . stringify ( points ) ) ; while ( dCpts . length > 1 ) { for ( let i = 0 ; i < dCpts . length - 1 ; i ++ ) { dCpts [ i ] = { x : dCpts [ i ] . x + ( dCpts [ i + 1 ] . x - dCpts [ i ] . x ) * t , y : dCpts [ i ] . y + ( dCpts [ i + 1 ] . y - dCpts [ i ] . y ) * t , } ; if ( typeof dCpts [ i ] . z !== "undefined" ) { dCpts [ i ] = dCpts [ i ] . z + ( dCpts [ i + 1 ] . z - dCpts [ i ] . z ) * t ; } } dCpts . splice ( dCpts . length - 1 , 1 ) ; } dCpts [ 0 ] . t = t ; return dCpts [ 0 ] ; } , computeWithRatios : function ( t , points , ratios , _3d ) { const mt = 1 - t , r = ratios , p = points ; let f1 = r [ 0 ] , f2 = r [ 1 ] , f3 = r [ 2 ] , f4 = r [ 3 ] , d ; f1 *= mt ; f2 *= t ; if ( p . length === 2 ) { d = f1 + f2 ; return { x : ( f1 * p [ 0 ] . x + f2 * p [ 1 ] . x ) / d , y : ( f1 * p [ 0 ] . y + f2 * p [ 1 ] . y ) / d , z : ! _3d ? false : ( f1 * p [ 0 ] . z + f2 * p [ 1 ] . z ) / d , t : t , } ; } f1 *= mt ; f2 *= 2 * mt ; f3 *= t * t ; if ( p . length === 3 ) { d = f1 + f2 + f3 ; return { x : ( f1 * p [ 0 ] . x + f2 * p [ 1 ] . x + f3 * p [ 2 ] . x ) / d , y : ( f1 * p [ 0 ] . y + f2 * p [ 1 ] . y + f3 * p [ 2 ] . y ) / d , z : ! _3d ? false : ( f1 * p [ 0 ] . z + f2 * p [ 1 ] . z + f3 * p [ 2 ] . z ) / d , t : t , } ; } f1 *= mt ; f2 *= 1.5 * mt ; f3 *= 3 * mt ; f4 *= t * t * t ; if ( p . length === 4 ) { d = f1 + f2 + f3 + f4 ; return { x : ( f1 * p [ 0 ] . x + f2 * p [ 1 ] . x + f3 * p [ 2 ] . x + f4 * p [ 3 ] . x ) / d , y : ( f1 * p [ 0 ] . y + f2 * p [ 1 ] . y + f3 * p [ 2 ] . y + f4 * p [ 3 ] . y ) / d , z : ! _3d ? false : ( f1 * p [ 0 ] . z + f2 * p [ 1 ] . z + f3 * p [ 2 ] . z + f4 * p [ 3 ] . z ) / d , t : t , } ; } } , derive : function ( points , _3d ) { const dpoints = [ ] ; for ( let p = points , d = p . length , c = d - 1 ; d > 1 ; d -- , c -- ) { const list = [ ] ; for ( let j = 0 , dpt ; j < c ; j ++ ) { dpt = { x : c * ( p [ j + 1 ] . x - p [ j ] . x ) , y : c * ( p [ j + 1 ] . y - p [ j ] . y ) , } ; if ( _3d ) { dpt . z = c * ( p [ j + 1 ] . z - p [ j ] . z ) ; } list . push ( dpt ) ; } dpoints . push ( list ) ; p = list ; } return dpoints ; } , between : function ( v , m , M ) { return ( ( m <= v && v <= M ) || utils . approximately ( v , m ) || utils . approximately ( v , M ) ) ; } , approximately : function ( a , b , precision ) { return abs ( a - b ) <= ( precision || epsilon ) ; } , length : function ( derivativeFn ) { const z = 0.5 , len = utils . Tvalues . length ; let sum = 0 ; for ( let i = 0 , t ; i < len ; i ++ ) { t = z * utils . Tvalues [ i ] + z ; sum += utils . Cvalues [ i ] * utils . arcfn ( t , derivativeFn ) ; } return z * sum ; } , map : function ( v , ds , de , ts , te ) { const d1 = de - ds , d2 = te - ts , v2 = v - ds , r = v2 / d1 ; return ts + d2 * r ; } , lerp : function ( r , v1 , v2 ) { const ret = { x : v1 . x + r * ( v2 . x - v1 . x ) , y : v1 . y + r * ( v2 . y - v1 . y ) , } ; if ( ! ! v1 . z && ! ! v2 . z ) { ret . z = v1 . z + r * ( v2 . z - v1 . z ) ; } return ret ; } , pointToString : function ( p ) { let s = p . x + "/" + p . y ; if ( typeof p . z !== "undefined" ) { s += "/" + p . z ; } return s ; } , pointsToString : function ( points ) { return "[" + points . map ( utils . pointToString ) . join ( ", " ) + "]" ; } , copy : function ( obj ) { return JSON . parse ( JSON . stringify ( obj ) ) ; } , angle : function ( o , v1 , v2 ) { const dx1 = v1 . x - o . x , dy1 = v1 . y - o . y , dx2 = v2 . x - o . x , dy2 = v2 . y - o . y , cross = dx1 * dy2 - dy1 * dx2 , dot = dx1 * dx2 + dy1 * dy2 ; return atan2 ( cross , dot ) ; } , round : function ( v , d ) { const s = "" + v ; const pos = s . indexOf ( "." ) ; return parseFloat ( s . substring ( 0 , pos + 1 + d ) ) ; } , dist : function ( p1 , p2 ) { const dx = p1 . x - p2 . x , dy = p1 . y - p2 . y ; return sqrt ( dx * dx + dy * dy ) ; } , closest : function ( LUT , point ) { let mdist = pow ( 2 , 63 ) , mpos , d ; LUT . forEach ( function ( p , idx ) { d = utils . dist ( point , p ) ; if ( d < mdist ) { mdist = d ; mpos = idx ; } } ) ; return { mdist : mdist , mpos : mpos } ; } , abcratio : function ( t , n ) { if ( n !== 2 && n !== 3 ) { return false ; } if ( typeof t === "undefined" ) { t = 0.5 ; } else if ( t === 0 || t === 1 ) { return t ; } const bottom = pow ( t , n ) + pow ( 1 - t , n ) , top = bottom - 1 ; return abs ( top / bottom ) ; } , projectionratio : function ( t , n ) { if ( n !== 2 && n !== 3 ) { return false ; } if ( typeof t === "undefined" ) { t = 0.5 ; } else if ( t === 0 || t === 1 ) { return t ; } const top = pow ( 1 - t , n ) , bottom = pow ( t , n ) + top ; return top / bottom ; } , lli8 : function ( x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 ) { const nx = ( x1 * y2 - y1 * x2 ) * ( x3 - x4 ) - ( x1 - x2 ) * ( x3 * y4 - y3 * x4 ) , ny = ( x1 * y2 - y1 * x2 ) * ( y3 - y4 ) - ( y1 - y2 ) * ( x3 * y4 - y3 * x4 ) , d = ( x1 - x2 ) * ( y3 - y4 ) - ( y1 - y2 ) * ( x3 - x4 ) ; if ( d == 0 ) { return false ; } return { x : nx / d , y : ny / d } ; } , lli4 : function ( p1 , p2 , p3 , p4 ) { const x1 = p1 . x , y1 = p1 . y , x2 = p2 . x , y2 = p2 . y , x3 = p3 . x , y3 = p3 . y , x4 = p4 . x , y4 = p4 . y ; return utils . lli8 ( x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 ) ; } , lli : function ( v1 , v2 ) { return utils . lli4 ( v1 , v1 . c , v2 , v2 . c ) ; } , makeline : function ( p1 , p2 ) { const x1 = p1 . x , y1 = p1 . y , x2 = p2 . x , y2 = p2 . y , dx = ( x2 - x1 ) / 3 , dy = ( y2 - y1 ) / 3 ; return new Bezier ( x1 , y1 , x1 + dx , y1 + dy , x1 + 2 * dx , y1 + 2 * dy , x2 , y2 ) ; } , findbbox : function ( sections ) { let mx = nMax , my = nMax , MX = nMin , MY = nMin ; sections . forEach ( function ( s ) { const bbox = s . bbox ( ) ; if ( mx > bbox . x . min ) mx = bbox . x . min ; if ( my > bbox . y . min ) my = bbox . y . min ; if ( MX < bbox . x . max ) MX = bbox . x . max ; if ( MY < bbox . y . max ) MY = bbox . y . max ; } ) ; return { x : { min : mx , mid : ( mx + MX ) / 2 , max : MX , size : MX - mx } , y : { min : my , mid : ( my + MY ) / 2 , max : MY , size : MY - my } , } ; } , shapeintersections : function ( s1 , bbox1 , s2 , bbox2 , curveIntersectionThreshold ) { if ( ! utils . bboxoverlap ( bbox1 , bbox2 ) ) return [ ] ; const intersections = [ ] ; const a1 = [ s1 . startcap , s1 . forward , s1 . back , s1 . endcap ] ; const a2 = [ s2 . startcap , s2 . forward , s2 . back , s2 . endcap ] ; a1 . forEach ( function ( l1 ) { if ( l1 . virtual ) return ; a2 . forEach ( function ( l2 ) { if ( l2 . virtual ) return ; const iss = l1 . intersects ( l2 , curveIntersectionThreshold ) ; if ( iss . length > 0 ) { iss . c1 = l1 ; iss . c2 = l2 ; iss . s1 = s1 ; iss . s2 = s2 ; intersections . push ( iss ) ; } } ) ; } ) ; return intersections ; } , makeshape : function ( forward , back , curveIntersectionThreshold ) { const bpl = back . points . length ; const fpl = forward . points . length ; const start = utils . makeline ( back . points [ bpl - 1 ] , forward . points [ 0 ] ) ; const end = utils . makeline ( forward . points [ fpl - 1 ] , back . points [ 0 ] ) ; const shape = { startcap : start , forward : forward , back : back , endcap : end , bbox : utils . findbbox ( [ start , forward , back , end ] ) , } ; shape . intersections = function ( s2 ) { return utils . shapeintersections ( shape , shape . bbox , s2 , s2 . bbox , curveIntersectionThreshold ) ; } ; return shape ; } , getminmax : function ( curve , d , list ) { if ( ! list ) return { min : 0 , max : 0 } ; let min = nMax , max = nMin , t , c ; if ( list . indexOf ( 0 ) === - 1 ) { list = [ 0 ] . concat ( list ) ; } if ( list . indexOf ( 1 ) === - 1 ) { list . push ( 1 ) ; } for ( let i = 0 , len = list . length ; i < len ; i ++ ) { t = list [ i ] ; c = curve . get ( t ) ; if ( c [ d ] < min ) { min = c [ d ] ; } if ( c [ d ] > max ) { max = c [ d ] ; } } return { min : min , mid : ( min + max ) / 2 , max : max , size : max - min } ; } , align : function ( points , line ) { const tx = line . p1 . x , ty = line . p1 . y , a = - atan2 ( line . p2 . y - ty , line . p2 . x - tx ) , d = function ( v ) { return { x : ( v . x - tx ) * cos ( a ) - ( v . y - ty ) * sin ( a ) , y : ( v . x - tx ) * sin ( a ) + ( v . y - ty ) * cos ( a ) , } ; } ; return points . map ( d ) ; } , roots : function ( points , line ) { line = line || { p1 : { x : 0 , y : 0 } , p2 : { x : 1 , y : 0 } } ; const order = points . length - 1 ; const aligned = utils . align ( points , line ) ; const reduce = function ( t ) { return 0 <= t && t <= 1 ; } ; if ( order === 2 ) { const a = aligned [ 0 ] . y , b = aligned [ 1 ] . y , c = aligned [ 2 ] . y , d = a - 2 * b + c ; if ( d !== 0 ) { const m1 = - sqrt ( b * b - a * c ) , m2 = - a + b , v1 = - ( m1 + m2 ) / d , v2 = - ( - m1 + m2 ) / d ; return [ v1 , v2 ] . filter ( reduce ) ; } else if ( b !== c && d === 0 ) { return [ ( 2 * b - c ) / ( 2 * b - 2 * c ) ] . filter ( reduce ) ; } return [ ] ; } const pa = aligned [ 0 ] . y , pb = aligned [ 1 ] . y , pc = aligned [ 2 ] . y , pd = aligned [ 3 ] . y ; let d = - pa + 3 * pb - 3 * pc + pd , a = 3 * pa - 6 * pb + 3 * pc , b = - 3 * pa + 3 * pb , c = pa ; if ( utils . approximately ( d , 0 ) ) { if ( utils . approximately ( a , 0 ) ) { if ( utils . approximately ( b , 0 ) ) { return [ ] ; } return [ - c / b ] . filter ( reduce ) ; } const q = sqrt ( b * b - 4 * a * c ) , a2 = 2 * a ; return [ ( q - b ) / a2 , ( - b - q ) / a2 ] . filter ( reduce ) ; } a /= d ; b /= d ; c /= d ; const p = ( 3 * b - a * a ) / 3 , p3 = p / 3 , q = ( 2 * a * a * a - 9 * a * b + 27 * c ) / 27 , q2 = q / 2 , discriminant = q2 * q2 + p3 * p3 * p3 ; let u1 , v1 , x1 , x2 , x3 ; if ( discriminant < 0 ) { const mp3 = - p / 3 , mp33 = mp3 * mp3 * mp3 , r = sqrt ( mp33 ) , t = - q / ( 2 * r ) , cosphi = t < - 1 ? - 1 : t > 1 ? 1 : t , phi = acos ( cosphi ) , crtr = crt ( r ) , t1 = 2 * crtr ; x1 = t1 * cos ( phi / 3 ) - a / 3 ; x2 = t1 * cos ( ( phi + tau ) / 3 ) - a / 3 ; x3 = t1 * cos ( ( phi + 2 * tau ) / 3 ) - a / 3 ; return [ x1 , x2 , x3 ] . filter ( reduce ) ; } else if ( discriminant === 0 ) { u1 = q2 < 0 ? crt ( - q2 ) : - crt ( q2 ) ; x1 = 2 * u1 - a / 3 ; x2 = - u1 - a / 3 ; return [ x1 , x2 ] . filter ( reduce ) ; } else { const sd = sqrt ( discriminant ) ; u1 = crt ( - q2 + sd ) ; v1 = crt ( q2 + sd ) ; return [ u1 - v1 - a / 3 ] . filter ( reduce ) ; } } , droots : function ( p ) { if ( p . length === 3 ) { const a = p [ 0 ] , b = p [ 1 ] , c = p [ 2 ] , d = a - 2 * b + c ; if ( d !== 0 ) { const m1 = - sqrt ( b * b - a * c ) , m2 = - a + b , v1 = - ( m1 + m2 ) / d , v2 = - ( - m1 + m2 ) / d ; return [ v1 , v2 ] ; } else if ( b !== c && d === 0 ) { return [ ( 2 * b - c ) / ( 2 * ( b - c ) ) ] ; } return [ ] ; } if ( p . length === 2 ) { const a = p [ 0 ] , b = p [ 1 ] ; if ( a !== b ) { return [ a / ( a - b ) ] ; } return [ ] ; } return [ ] ; } , curvature : function ( t , d1 , d2 , _3d , kOnly ) { let num , dnm , adk , dk , k = 0 , r = 0 ; const d = utils . compute ( t , d1 ) ; const dd = utils . compute ( t , d2 ) ; const qdsum = d . x * d . x + d . y * d . y ; if ( _3d ) { num = sqrt ( pow ( d . y * dd . z - dd . y * d . z , 2 ) + pow ( d . z * dd . x - dd . z * d . x , 2 ) + pow ( d . x * dd . y - dd . x * d . y , 2 ) ) ; dnm = pow ( qdsum + d . z * d . z , 3 / 2 ) ; } else { num = d . x * dd . y - d . y * dd . x ; dnm = pow ( qdsum , 3 / 2 ) ; } if ( num === 0 || dnm === 0 ) { return { k : 0 , r : 0 } ; } k = num / dnm ; r = dnm / num ; if ( ! kOnly ) { const pk = utils . curvature ( t - 0.001 , d1 , d2 , _3d , true ) . k ; const nk = utils . curvature ( t + 0.001 , d1 , d2 , _3d , true ) . k ; dk = ( nk - k + ( k - pk ) ) / 2 ; adk = ( abs ( nk - k ) + abs ( k - pk ) ) / 2 ; } return { k : k , r : r , dk : dk , adk : adk } ; } , inflections : function ( points ) { if ( points . length < 4 ) return [ ] ; const p = utils . align ( points , { p1 : points [ 0 ] , p2 : points . slice ( - 1 ) [ 0 ] } ) , a = p [ 2 ] . x * p [ 1 ] . y , b = p [ 3 ] . x * p [ 1 ] . y , c = p [ 1 ] . x * p [ 2 ] . y , d = p [ 3 ] . x * p [ 2 ] . y , v1 = 18 * ( - 3 * a + 2 * b + 3 * c - d ) , v2 = 18 * ( 3 * a - b - 3 * c ) , v3 = 18 * ( c - a ) ; if ( utils . approximately ( v1 , 0 ) ) { if ( ! utils . approximately ( v2 , 0 ) ) { let t = - v3 / v2 ; if ( 0 <= t && t <= 1 ) return [ t ] ; } return [ ] ; } const trm = v2 * v2 - 4 * v1 * v3 , sq = Math . sqrt ( trm ) , d2 = 2 * v1 ; if ( utils . approximately ( d2 , 0 ) ) return [ ] ; return [ ( sq - v2 ) / d2 , - ( v2 + sq ) / d2 ] . filter ( function ( r ) { return 0 <= r && r <= 1 ; } ) ; } , bboxoverlap : function ( b1 , b2 ) { const dims = [ "x" , "y" ] , len = dims . length ; for ( let i = 0 , dim , l , t , d ; i < len ; i ++ ) { dim = dims [ i ] ; l = b1 [ dim ] . mid ; t = b2 [ dim ] . mid ; d = ( b1 [ dim ] . size + b2 [ dim ] . size ) / 2 ; if ( abs ( l - t ) >= d ) return false ; } return true ; } , expandbox : function ( bbox , _bbox ) { if ( _bbox . x . min < bbox . x . min ) { bbox . x . min = _bbox . x . min ; } if ( _bbox . y . min < bbox . y . min ) { bbox . y . min = _bbox . y . min ; } if ( _bbox . z && _bbox . z . min < bbox . z . min ) { bbox . z . min = _bbox . z . min ; } if ( _bbox . x . max > bbox . x . max ) { bbox . x . max = _bbox . x . max ; } if ( _bbox . y . max > bbox . y . max ) { bbox . y . max = _bbox . y . max ; } if ( _bbox . z && _bbox . z . max > bbox . z . max ) { bbox . z . max = _bbox . z . max ; } bbox . x . mid = ( bbox . x . min + bbox . x . max ) / 2 ; bbox . y . mid = ( bbox . y . min + bbox . y . max ) / 2 ; if ( bbox . z ) { bbox . z . mid = ( bbox . z . min + bbox . z . max ) / 2 ; } bbox . x . size = bbox . x . max - bbox . x . min ; bbox . y . size = bbox . y . max - bbox . y . min ; if ( bbox . z ) { bbox . z . size = bbox . z . max - bbox . z . min ; } } , pairiteration : function ( c1 , c2 , curveIntersectionThreshold ) { const c1b = c1 . bbox ( ) , c2b = c2 . bbox ( ) , r = 100000 , threshold = curveIntersectionThreshold || 0.5 ; if ( c1b . x . size + c1b . y . size < threshold && c2b . x . size + c2b . y . size < threshold ) { return [ ( ( ( r * ( c1 . _t1 + c1 . _t2 ) ) / 2 ) | 0 ) / r + "/" + ( ( ( r * ( c2 . _t1 + c2 . _t2 ) ) / 2 ) | 0 ) / r , ] ; } let cc1 = c1 . split ( 0.5 ) , cc2 = c2 . split ( 0.5 ) , pairs = [ { left : cc1 . left , right : cc2 . left } , { left : cc1 . left , right : cc2 . right } , { left : cc1 . right , right : cc2 . right } , { left : cc1 . right , right : cc2 . left } , ] ; pairs = pairs . filter ( function ( pair ) { return utils . bboxoverlap ( pair . left . bbox ( ) , pair . right . bbox ( ) ) ; } ) ; let results = [ ] ; if ( pairs . length === 0 ) return results ; pairs . forEach ( function ( pair ) { results = results . concat ( utils . pairiteration ( pair . left , pair . right , threshold ) ) ; } ) ; results = results . filter ( function ( v , i ) { return results . indexOf ( v ) === i ; } ) ; return results ; } , getccenter : function ( p1 , p2 , p3 ) { const dx1 = p2 . x - p1 . x , dy1 = p2 . y - p1 . y , dx2 = p3 . x - p2 . x , dy2 = p3 . y - p2 . y , dx1p = dx1 * cos ( quart ) - dy1 * sin ( quart ) , dy1p = dx1 * sin ( quart ) + dy1 * cos ( quart ) , dx2p = dx2 * cos ( quart ) - dy2 * sin ( quart ) , dy2p = dx2 * sin ( quart ) + dy2 * cos ( quart ) , mx1 = ( p1 . x + p2 . x ) / 2 , my1 = ( p1 . y + p2 . y ) / 2 , mx2 = ( p2 . x + p3 . x ) / 2 , my2 = ( p2 . y + p3 . y ) / 2 , mx1n = mx1 + dx1p , my1n = my1 + dy1p , mx2n = mx2 + dx2p , my2n = my2 + dy2p , arc = utils . lli8 ( mx1 , my1 , mx1n , my1n , mx2 , my2 , mx2n , my2n ) , r = utils . dist ( arc , p1 ) ; let s = atan2 ( p1 . y - arc . y , p1 . x - arc . x ) , m = atan2 ( p2 . y - arc . y , p2 . x - arc . x ) , e = atan2 ( p3 . y - arc . y , p3 . x - arc . x ) , _ ; if ( s < e ) { if ( s > m || m > e ) { s += tau ; } if ( s > e ) { _ = e ; e = s ; s = _ ; } } else { if ( e < m && m < s ) { _ = e ; e = s ; s = _ ; } else { e += tau ; } } arc . s = s ; arc . e = e ; arc . r = r ; return arc ; } , numberSort : function ( a , b ) { return a - b ; } , } ; param { [ type ] } curves class PolyBezier { constructor ( curves ) { this . curves = [ ] ; this . _3d = false ; if ( ! ! curves ) { this . curves = curves ; this . _3d = this . curves [ 0 ] . _3d ; } } valueOf ( ) { return this . toString ( ) ; } toString ( ) { return ( "[" + this . curves . map ( function ( curve ) { return utils . pointsToString ( curve . points ) ; } ) . join ( ", " ) + "]" ) ; } addCurve ( curve ) { this . curves . push ( curve ) ; this . _3d = this . _3d || curve . _3d ; } length ( ) { return this . curves . map ( function ( v ) { return v . length ( ) ; } ) . reduce ( function ( a , b ) { return a + b ; } ) ; } curve ( idx ) { return this . curves [ idx ] ; } bbox ( ) { const c = this . curves ; var bbox = c [ 0 ] . bbox ( ) ; for ( var i = 1 ; i < c . length ; i ++ ) { utils . expandbox ( bbox , c [ i ] . bbox ( ) ) ; } return bbox ; } offset ( d ) { const offset = [ ] ; this . curves . forEach ( function ( v ) { offset . push ( ... v . offset ( d ) ) ; } ) ; return new PolyBezier ( offset ) ; } } /**
  A javascript Bezier curve library by Pomax.

  Based on http://pomax.github.io/bezierinfo

  This code is MIT licensed.
**/ const { abs : abs$1 , min , max , cos : cos$1 , sin : sin$1 , acos : acos$1 , sqrt : sqrt$1 } = Math ; const pi$1 = Math . PI ; /**
 * Bezier curve constructor.
 *
 * ...docs pending...
 */ class Bezier { constructor ( coords ) { let args = coords && coords . forEach ? coords : Array . from ( arguments ) . slice ( ) ; let coordlen = false ; if ( typeof args [ 0 ] === "object" ) { coordlen = args . length ; const newargs = [ ] ; args . forEach ( function ( point ) { [ "x" , "y" , "z" ] . forEach ( function ( d ) { if ( typeof point [ d ] !== "undefined" ) { newargs . push ( point [ d ] ) ; } } ) ; } ) ; args = newargs ; } let higher = false ; const len = args . length ; if ( coordlen ) { if ( coordlen > 4 ) { if ( arguments . length !== 1 ) { throw new Error ( "Only new Bezier(point[]) is accepted for 4th and higher order curves" ) ; } higher = true ; } } else { if ( len !== 6 && len !== 8 && len !== 9 && len !== 12 ) { if ( arguments . length !== 1 ) { throw new Error ( "Only new Bezier(point[]) is accepted for 4th and higher order curves" ) ; } } } const _3d = ( this . _3d = ( ! higher && ( len === 9 || len === 12 ) ) || ( coords && coords [ 0 ] && typeof coords [ 0 ] . z !== "undefined" ) ) ; const points = ( this . points = [ ] ) ; for ( let idx = 0 , step = _3d ? 3 : 2 ; idx < len ; idx += step ) { var point = { x : args [ idx ] , y : args [ idx + 1 ] , } ; if ( _3d ) { point . z = args [ idx + 2 ] ; } points . push ( point ) ; } const order = ( this . order = points . length - 1 ) ; const dims = ( this . dims = [ "x" , "y" ] ) ; if ( _3d ) dims . push ( "z" ) ; this . dimlen = dims . length ; const aligned = utils . align ( points , { p1 : points [ 0 ] , p2 : points [ order ] } ) ; this . _linear = ! aligned . some ( ( p ) => abs$1 ( p . y ) > 0.0001 ) ; this . _lut = [ ] ; this . _t1 = 0 ; this . _t2 = 1 ; this . update ( ) ; } static quadraticFromPoints ( p1 , p2 , p3 , t ) { if ( typeof t === "undefined" ) { t = 0.5 ; } if ( t === 0 ) { return new Bezier ( p2 , p2 , p3 ) ; } if ( t === 1 ) { return new Bezier ( p1 , p2 , p2 ) ; } const abc = Bezier . getABC ( 2 , p1 , p2 , p3 , t ) ; return new Bezier ( p1 , abc . A , p3 ) ; } static cubicFromPoints ( S , B , E , t , d1 ) { if ( typeof t === "undefined" ) { t = 0.5 ; } const abc = Bezier . getABC ( 3 , S , B , E , t ) ; if ( typeof d1 === "undefined" ) { d1 = utils . dist ( B , abc . C ) ; } const d2 = ( d1 * ( 1 - t ) ) / t ; const selen = utils . dist ( S , E ) , lx = ( E . x - S . x ) / selen , ly = ( E . y - S . y ) / selen , bx1 = d1 * lx , by1 = d1 * ly , bx2 = d2 * lx , by2 = d2 * ly ; const e1 = { x : B . x - bx1 , y : B . y - by1 } , e2 = { x : B . x + bx2 , y : B . y + by2 } , A = abc . A , v1 = { x : A . x + ( e1 . x - A . x ) / ( 1 - t ) , y : A . y + ( e1 . y - A . y ) / ( 1 - t ) } , v2 = { x : A . x + ( e2 . x - A . x ) / t , y : A . y + ( e2 . y - A . y ) / t } , nc1 = { x : S . x + ( v1 . x - S . x ) / t , y : S . y + ( v1 . y - S . y ) / t } , nc2 = { x : E . x + ( v2 . x - E . x ) / ( 1 - t ) , y : E . y + ( v2 . y - E . y ) / ( 1 - t ) , } ; return new Bezier ( S , nc1 , nc2 , E ) ; } static getUtils ( ) { return utils ; } getUtils ( ) { return Bezier . getUtils ( ) ; } static get PolyBezier ( ) { return PolyBezier ; } valueOf ( ) { return this . toString ( ) ; } toString ( ) { return utils . pointsToString ( this . points ) ; } toSVG ( ) { if ( this . _3d ) return false ; const p = this . points , x = p [ 0 ] . x , y = p [ 0 ] . y , s = [ "M" , x , y , this . order === 2 ? "Q" : "C" ] ; for ( let i = 1 , last = p . length ; i < last ; i ++ ) { s . push ( p [ i ] . x ) ; s . push ( p [ i ] . y ) ; } return s . join ( " " ) ; } setRatios ( ratios ) { if ( ratios . length !== this . points . length ) { throw new Error ( "incorrect number of ratio values" ) ; } this . ratios = ratios ; this . _lut = [ ] ; } verify ( ) { const print = this . coordDigest ( ) ; if ( print !== this . _print ) { this . _print = print ; this . update ( ) ; } } coordDigest ( ) { return this . points . map ( function ( c , pos ) { return "" + pos + c . x + c . y + ( c . z ? c . z : 0 ) ; } ) . join ( "" ) ; } update ( ) { this . _lut = [ ] ; this . dpoints = utils . derive ( this . points , this . _3d ) ; this . computedirection ( ) ; } computedirection ( ) { const points = this . points ; const angle = utils . angle ( points [ 0 ] , points [ this . order ] , points [ 1 ] ) ; this . clockwise = angle > 0 ; } length ( ) { return utils . length ( this . derivative . bind ( this ) ) ; } static getABC ( order = 2 , S , B , E , t = 0.5 ) { const u = utils . projectionratio ( t , order ) , um = 1 - u , C = { x : u * S . x + um * E . x , y : u * S . y + um * E . y , } , s = utils . abcratio ( t , order ) , A = { x : B . x + ( B . x - C . x ) / s , y : B . y + ( B . y - C . y ) / s , } ; return { A , B , C , S , E } ; } getABC ( t , B ) { B = B || this . get ( t ) ; let S = this . points [ 0 ] ; let E = this . points [ this . order ] ; return Bezier . getABC ( this . order , S , B , E , t ) ; } getLUT ( steps ) { this . verify ( ) ; steps = steps || 100 ; if ( this . _lut . length === steps ) { return this . _lut ; } this . _lut = [ ] ; steps -- ; for ( let i = 0 , p , t ; i < steps ; i ++ ) { t = i / ( steps - 1 ) ; p = this . compute ( t ) ; p . t = t ; this . _lut . push ( p ) ; } return this . _lut ; } on ( point , error ) { error = error || 5 ; const lut = this . getLUT ( ) , hits = [ ] ; for ( let i = 0 , c , t = 0 ; i < lut . length ; i ++ ) { c = lut [ i ] ; if ( utils . dist ( c , point ) < error ) { hits . push ( c ) ; t += i / lut . length ; } } if ( ! hits . length ) return false ; return ( t /= hits . length ) ; } project ( point ) { const LUT = this . getLUT ( ) , l = LUT . length - 1 , closest = utils . closest ( LUT , point ) , mpos = closest . mpos , t1 = ( mpos - 1 ) / l , t2 = ( mpos + 1 ) / l , step = 0.1 / l ; let mdist = closest . mdist , t = t1 , ft = t , p ; mdist += 1 ; for ( let d ; t < t2 + step ; t += step ) { p = this . compute ( t ) ; d = utils . dist ( point , p ) ; if ( d < mdist ) { mdist = d ; ft = t ; } } ft = ft < 0 ? 0 : ft > 1 ? 1 : ft ; p = this . compute ( ft ) ; p . t = ft ; p . d = mdist ; return p ; } get ( t ) { return this . compute ( t ) ; } point ( idx ) { return this . points [ idx ] ; } compute ( t ) { if ( this . ratios ) { return utils . computeWithRatios ( t , this . points , this . ratios , this . _3d ) ; } return utils . compute ( t , this . points , this . _3d , this . ratios ) ; } raise ( ) { const p = this . points , np = [ p [ 0 ] ] , k = p . length ; for ( let i = 1 , pi , pim ; i < k ; i ++ ) { pi = p [ i ] ; pim = p [ i - 1 ] ; np [ i ] = { x : ( ( k - i ) / k ) * pi . x + ( i / k ) * pim . x , y : ( ( k - i ) / k ) * pi . y + ( i / k ) * pim . y , } ; } np [ k ] = p [ k - 1 ] ; return new Bezier ( np ) ; } derivative ( t ) { return utils . compute ( t , this . dpoints [ 0 ] ) ; } dderivative ( t ) { return utils . compute ( t , this . dpoints [ 1 ] ) ; } align ( ) { let p = this . points ; return new Bezier ( utils . align ( p , { p1 : p [ 0 ] , p2 : p [ p . length - 1 ] } ) ) ; } curvature ( t ) { return utils . curvature ( t , this . dpoints [ 0 ] , this . dpoints [ 1 ] , this . _3d ) ; } inflections ( ) { return utils . inflections ( this . points ) ; } normal ( t ) { return this . _3d ? this . __normal3 ( t ) : this . __normal2 ( t ) ; } __normal2 ( t ) { const d = this . derivative ( t ) ; const q = sqrt$1 ( d . x * d . x + d . y * d . y ) ; return { x : - d . y / q , y : d . x / q } ; } __normal3 ( t ) { const r1 = this . derivative ( t ) , r2 = this . derivative ( t + 0.01 ) , q1 = sqrt$1 ( r1 . x * r1 . x + r1 . y * r1 . y + r1 . z * r1 . z ) , q2 = sqrt$1 ( r2 . x * r2 . x + r2 . y * r2 . y + r2 . z * r2 . z ) ; r1 . x /= q1 ; r1 . y /= q1 ; r1 . z /= q1 ; r2 . x /= q2 ; r2 . y /= q2 ; r2 . z /= q2 ; const c = { x : r2 . y * r1 . z - r2 . z * r1 . y , y : r2 . z * r1 . x - r2 . x * r1 . z , z : r2 . x * r1 . y - r2 . y * r1 . x , } ; const m = sqrt$1 ( c . x * c . x + c . y * c . y + c . z * c . z ) ; c . x /= m ; c . y /= m ; c . z /= m ; const R = [ c . x * c . x , c . x * c . y - c . z , c . x * c . z + c . y , c . x * c . y + c . z , c . y * c . y , c . y * c . z - c . x , c . x * c . z - c . y , c . y * c . z + c . x , c . z * c . z , ] ; const n = { x : R [ 0 ] * r1 . x + R [ 1 ] * r1 . y + R [ 2 ] * r1 . z , y : R [ 3 ] * r1 . x + R [ 4 ] * r1 . y + R [ 5 ] * r1 . z , z : R [ 6 ] * r1 . x + R [ 7 ] * r1 . y + R [ 8 ] * r1 . z , } ; return n ; } hull ( t ) { let p = this . points , _p = [ ] , q = [ ] , idx = 0 ; q [ idx ++ ] = p [ 0 ] ; q [ idx ++ ] = p [ 1 ] ; q [ idx ++ ] = p [ 2 ] ; if ( this . order === 3 ) { q [ idx ++ ] = p [ 3 ] ; } while ( p . length > 1 ) { _p = [ ] ; for ( let i = 0 , pt , l = p . length - 1 ; i < l ; i ++ ) { pt = utils . lerp ( t , p [ i ] , p [ i + 1 ] ) ; q [ idx ++ ] = pt ; _p . push ( pt ) ; } p = _p ; } return q ; } split ( t1 , t2 ) { if ( t1 === 0 && ! ! t2 ) { return this . split ( t2 ) . left ; } if ( t2 === 1 ) { return this . split ( t1 ) . right ; } const q = this . hull ( t1 ) ; const result = { left : this . order === 2 ? new Bezier ( [ q [ 0 ] , q [ 3 ] , q [ 5 ] ] ) : new Bezier ( [ q [ 0 ] , q [ 4 ] , q [ 7 ] , q [ 9 ] ] ) , right : this . order === 2 ? new Bezier ( [ q [ 5 ] , q [ 4 ] , q [ 2 ] ] ) : new Bezier ( [ q [ 9 ] , q [ 8 ] , q [ 6 ] , q [ 3 ] ] ) , span : q , } ; result . left . _t1 = utils . map ( 0 , 0 , 1 , this . _t1 , this . _t2 ) ; result . left . _t2 = utils . map ( t1 , 0 , 1 , this . _t1 , this . _t2 ) ; result . right . _t1 = utils . map ( t1 , 0 , 1 , this . _t1 , this . _t2 ) ; result . right . _t2 = utils . map ( 1 , 0 , 1 , this . _t1 , this . _t2 ) ; if ( ! t2 ) { return result ; } t2 = utils . map ( t2 , t1 , 1 , 0 , 1 ) ; return result . right . split ( t2 ) . left ; } extrema ( ) { const result = { } ; let roots = [ ] ; this . dims . forEach ( function ( dim ) { let mfn = function ( v ) { return v [ dim ] ; } ; let p = this . dpoints [ 0 ] . map ( mfn ) ; result [ dim ] = utils . droots ( p ) ; if ( this . order === 3 ) { p = this . dpoints [ 1 ] . map ( mfn ) ; result [ dim ] = result [ dim ] . concat ( utils . droots ( p ) ) ; } result [ dim ] = result [ dim ] . filter ( function ( t ) { return t >= 0 && t <= 1 ; } ) ; roots = roots . concat ( result [ dim ] . sort ( utils . numberSort ) ) ; } . bind ( this ) ) ; result . values = roots . sort ( utils . numberSort ) . filter ( function ( v , idx ) { return roots . indexOf ( v ) === idx ; } ) ; return result ; } bbox ( ) { const extrema = this . extrema ( ) , result = { } ; this . dims . forEach ( function ( d ) { result [ d ] = utils . getminmax ( this , d , extrema [ d ] ) ; } . bind ( this ) ) ; return result ; } overlaps ( curve ) { const lbbox = this . bbox ( ) , tbbox = curve . bbox ( ) ; return utils . bboxoverlap ( lbbox , tbbox ) ; } offset ( t , d ) { if ( typeof d !== "undefined" ) { const c = this . get ( t ) , n = this . normal ( t ) ; const ret = { c : c , n : n , x : c . x + n . x * d , y : c . y + n . y * d , } ; if ( this . _3d ) { ret . z = c . z + n . z * d ; } return ret ; } if ( this . _linear ) { const nv = this . normal ( 0 ) , coords = this . points . map ( function ( p ) { const ret = { x : p . x + t * nv . x , y : p . y + t * nv . y , } ; if ( p . z && nv . z ) { ret . z = p . z + t * nv . z ; } return ret ; } ) ; return [ new Bezier ( coords ) ] ; } return this . reduce ( ) . map ( function ( s ) { if ( s . _linear ) { return s . offset ( t ) [ 0 ] ; } return s . scale ( t ) ; } ) ; } simple ( ) { if ( this . order === 3 ) { const a1 = utils . angle ( this . points [ 0 ] , this . points [ 3 ] , this . points [ 1 ] ) ; const a2 = utils . angle ( this . points [ 0 ] , this . points [ 3 ] , this . points [ 2 ] ) ; if ( ( a1 > 0 && a2 < 0 ) || ( a1 < 0 && a2 > 0 ) ) return false ; } const n1 = this . normal ( 0 ) ; const n2 = this . normal ( 1 ) ; let s = n1 . x * n2 . x + n1 . y * n2 . y ; if ( this . _3d ) { s += n1 . z * n2 . z ; } return abs$1 ( acos$1 ( s ) ) < pi$1 / 3 ; } reduce ( ) { let i , t1 = 0 , t2 = 0 , step = 0.01 , segment , pass1 = [ ] , pass2 = [ ] ; let extrema = this . extrema ( ) . values ; if ( extrema . indexOf ( 0 ) === - 1 ) { extrema = [ 0 ] . concat ( extrema ) ; } if ( extrema . indexOf ( 1 ) === - 1 ) { extrema . push ( 1 ) ; } for ( t1 = extrema [ 0 ] , i = 1 ; i < extrema . length ; i ++ ) { t2 = extrema [ i ] ; segment = this . split ( t1 , t2 ) ; segment . _t1 = t1 ; segment . _t2 = t2 ; pass1 . push ( segment ) ; t1 = t2 ; } pass1 . forEach ( function ( p1 ) { t1 = 0 ; t2 = 0 ; while ( t2 <= 1 ) { for ( t2 = t1 + step ; t2 <= 1 + step ; t2 += step ) { segment = p1 . split ( t1 , t2 ) ; if ( ! segment . simple ( ) ) { t2 -= step ; if ( abs$1 ( t1 - t2 ) < step ) { return [ ] ; } segment = p1 . split ( t1 , t2 ) ; segment . _t1 = utils . map ( t1 , 0 , 1 , p1 . _t1 , p1 . _t2 ) ; segment . _t2 = utils . map ( t2 , 0 , 1 , p1 . _t1 , p1 . _t2 ) ; pass2 . push ( segment ) ; t1 = t2 ; break ; } } } if ( t1 < 1 ) { segment = p1 . split ( t1 , 1 ) ; segment . _t1 = utils . map ( t1 , 0 , 1 , p1 . _t1 , p1 . _t2 ) ; segment . _t2 = p1 . _t2 ; pass2 . push ( segment ) ; } } ) ; return pass2 ; } scale ( d ) { const order = this . order ; let distanceFn = false ; if ( typeof d === "function" ) { distanceFn = d ; } if ( distanceFn && order === 2 ) { return this . raise ( ) . scale ( distanceFn ) ; } const clockwise = this . clockwise ; const r1 = distanceFn ? distanceFn ( 0 ) : d ; const r2 = distanceFn ? distanceFn ( 1 ) : d ; const v = [ this . offset ( 0 , 10 ) , this . offset ( 1 , 10 ) ] ; const points = this . points ; const np = [ ] ; const o = utils . lli4 ( v [ 0 ] , v [ 0 ] . c , v [ 1 ] , v [ 1 ] . c ) ; if ( ! o ) { throw new Error ( "cannot scale this curve. Try reducing it first." ) ; } [ 0 , 1 ] . forEach ( function ( t ) { const p = ( np [ t * order ] = utils . copy ( points [ t * order ] ) ) ; p . x += ( t ? r2 : r1 ) * v [ t ] . n . x ; p . y += ( t ? r2 : r1 ) * v [ t ] . n . y ; } ) ; if ( ! distanceFn ) { [ 0 , 1 ] . forEach ( ( t ) => { if ( order === 2 && ! ! t ) return ; const p = np [ t * order ] ; const d = this . derivative ( t ) ; const p2 = { x : p . x + d . x , y : p . y + d . y } ; np [ t + 1 ] = utils . lli4 ( p , p2 , o , points [ t + 1 ] ) ; } ) ; return new Bezier ( np ) ; } [ 0 , 1 ] . forEach ( function ( t ) { if ( order === 2 && ! ! t ) return ; var p = points [ t + 1 ] ; var ov = { x : p . x - o . x , y : p . y - o . y , } ; var rc = distanceFn ? distanceFn ( ( t + 1 ) / order ) : d ; if ( distanceFn && ! clockwise ) rc = - rc ; var m = sqrt$1 ( ov . x * ov . x + ov . y * ov . y ) ; ov . x /= m ; ov . y /= m ; np [ t + 1 ] = { x : p . x + rc * ov . x , y : p . y + rc * ov . y , } ; } ) ; return new Bezier ( np ) ; } outline ( d1 , d2 , d3 , d4 ) { d2 = typeof d2 === "undefined" ? d1 : d2 ; const reduced = this . reduce ( ) , len = reduced . length , fcurves = [ ] ; let bcurves = [ ] , p , alen = 0 , tlen = this . length ( ) ; const graduated = typeof d3 !== "undefined" && typeof d4 !== "undefined" ; function linearDistanceFunction ( s , e , tlen , alen , slen ) { return function ( v ) { const f1 = alen / tlen , f2 = ( alen + slen ) / tlen , d = e - s ; return utils . map ( v , 0 , 1 , s + f1 * d , s + f2 * d ) ; } ; } reduced . forEach ( function ( segment ) { const slen = segment . length ( ) ; if ( graduated ) { fcurves . push ( segment . scale ( linearDistanceFunction ( d1 , d3 , tlen , alen , slen ) ) ) ; bcurves . push ( segment . scale ( linearDistanceFunction ( - d2 , - d4 , tlen , alen , slen ) ) ) ; } else { fcurves . push ( segment . scale ( d1 ) ) ; bcurves . push ( segment . scale ( - d2 ) ) ; } alen += slen ; } ) ; bcurves = bcurves . map ( function ( s ) { p = s . points ; if ( p [ 3 ] ) { s . points = [ p [ 3 ] , p [ 2 ] , p [ 1 ] , p [ 0 ] ] ; } else { s . points = [ p [ 2 ] , p [ 1 ] , p [ 0 ] ] ; } return s ; } ) . reverse ( ) ; const fs = fcurves [ 0 ] . points [ 0 ] , fe = fcurves [ len - 1 ] . points [ fcurves [ len - 1 ] . points . length - 1 ] , bs = bcurves [ len - 1 ] . points [ bcurves [ len - 1 ] . points . length - 1 ] , be = bcurves [ 0 ] . points [ 0 ] , ls = utils . makeline ( bs , fs ) , le = utils . makeline ( fe , be ) , segments = [ ls ] . concat ( fcurves ) . concat ( [ le ] ) . concat ( bcurves ) ; return new PolyBezier ( segments ) ; } outlineshapes ( d1 , d2 , curveIntersectionThreshold ) { d2 = d2 || d1 ; const outline = this . outline ( d1 , d2 ) . curves ; const shapes = [ ] ; for ( let i = 1 , len = outline . length ; i < len / 2 ; i ++ ) { const shape = utils . makeshape ( outline [ i ] , outline [ len - i ] , curveIntersectionThreshold ) ; shape . startcap . virtual = i > 1 ; shape . endcap . virtual = i < len / 2 - 1 ; shapes . push ( shape ) ; } return shapes ; } intersects ( curve , curveIntersectionThreshold ) { if ( ! curve ) return this . selfintersects ( curveIntersectionThreshold ) ; if ( curve . p1 && curve . p2 ) { return this . lineIntersects ( curve ) ; } if ( curve instanceof Bezier ) { curve = curve . reduce ( ) ; } return this . curveintersects ( this . reduce ( ) , curve , curveIntersectionThreshold ) ; } lineIntersects ( line ) { const mx = min ( line . p1 . x , line . p2 . x ) , my = min ( line . p1 . y , line . p2 . y ) , MX = max ( line . p1 . x , line . p2 . x ) , MY = max ( line . p1 . y , line . p2 . y ) ; return utils . roots ( this . points , line ) . filter ( ( t ) => { var p = this . get ( t ) ; return utils . between ( p . x , mx , MX ) && utils . between ( p . y , my , MY ) ; } ) ; } selfintersects ( curveIntersectionThreshold ) { const reduced = this . reduce ( ) , len = reduced . length - 2 , results = [ ] ; for ( let i = 0 , result , left , right ; i < len ; i ++ ) { left = reduced . slice ( i , i + 1 ) ; right = reduced . slice ( i + 2 ) ; result = this . curveintersects ( left , right , curveIntersectionThreshold ) ; results . push ( ... result ) ; } return results ; } curveintersects ( c1 , c2 , curveIntersectionThreshold ) { const pairs = [ ] ; c1 . forEach ( function ( l ) { c2 . forEach ( function ( r ) { if ( l . overlaps ( r ) ) { pairs . push ( { left : l , right : r } ) ; } } ) ; } ) ; let intersections = [ ] ; pairs . forEach ( function ( pair ) { const result = utils . pairiteration ( pair . left , pair . right , curveIntersectionThreshold ) ; if ( result . length > 0 ) { intersections = intersections . concat ( result ) ; } } ) ; return intersections ; } arcs ( errorThreshold ) { errorThreshold = errorThreshold || 0.5 ; return this . _iterate ( errorThreshold , [ ] ) ; } _error ( pc , np1 , s , e ) { const q = ( e - s ) / 4 , c1 = this . get ( s + q ) , c2 = this . get ( e - q ) , ref = utils . dist ( pc , np1 ) , d1 = utils . dist ( pc , c1 ) , d2 = utils . dist ( pc , c2 ) ; return abs$1 ( d1 - ref ) + abs$1 ( d2 - ref ) ; } _iterate ( errorThreshold , circles ) { let t_s = 0 , t_e = 1 , safety ; do { safety = 0 ; t_e = 1 ; let np1 = this . get ( t_s ) , np2 , np3 , arc , prev_arc ; let curr_good = false , prev_good = false , done ; let t_m = t_e , prev_e = 1 ; do { prev_good = curr_good ; prev_arc = arc ; t_m = ( t_s + t_e ) / 2 ; np2 = this . get ( t_m ) ; np3 = this . get ( t_e ) ; arc = utils . getccenter ( np1 , np2 , np3 ) ; arc . interval = { start : t_s , end : t_e , } ; let error = this . _error ( arc , np1 , t_s , t_e ) ; curr_good = error <= errorThreshold ; done = prev_good && ! curr_good ; if ( ! done ) prev_e = t_e ; if ( curr_good ) { if ( t_e >= 1 ) { arc . interval . end = prev_e = 1 ; prev_arc = arc ; if ( t_e > 1 ) { let d = { x : arc . x + arc . r * cos$1 ( arc . e ) , y : arc . y + arc . r * sin$1 ( arc . e ) , } ; arc . e += utils . angle ( { x : arc . x , y : arc . y } , d , this . get ( 1 ) ) ; } break ; } t_e = t_e + ( t_e - t_s ) / 2 ; } else { t_e = t_m ; } } while ( ! done && safety ++ < 100 ) ; if ( safety >= 100 ) { break ; } prev_arc = prev_arc ? prev_arc : arc ; circles . push ( prev_arc ) ; t_s = prev_e ; } while ( t_e < 1 ) ; return circles ; } } export { Bezier } ;