Morph ➿

Two regular polygons (contours of Schläfli {x/y}) morph into one another using lerp on bezier (control) points or on samples of those paths. Or you can use (a) custom polygon(s) or path(s).

Variables bezierAmplitude and bezierInserts work when method is Bezier morph and sampleShift is used otherwise.

When method is Bezier and the number of vertices of the polygons or paths do not match vertices are inserted described by bezierInserts.

For non-custom paths, y must be equal to 1 or 2 or, if larger, x must be larger than 2y (if not y is reset to 2).

When seed is set to 0, Datetime.now() is used as seed.

en.wikipedia.org/wiki/star_polygon
en.wikipedia.org/wiki/schl%c3%a4fli_symbol#regular_polygons_(plane)

Morph ➿ (variation)
Morph ➿ (variation)

Log in to post a comment.

const method = 0; //min=0 max=1 step=1 (Bezier morph, Sampled lerp)
const bezierAmplitude = .5; //min=0 max=3 step=.01, The distance of the control points bezier paths relative to the distance of the two ends. Only concerns non-custom paths.
const bezierInserts = 0; //min=0 max=4 step=1 (Random, Uniform, Alternating top and bottom, Top (or Start for path), Bottom (or Halfway for path)) Will only be used if polygon is set to regular {x/y}
const sampleShift = 0; //min=0 max=1 step=.01 Applies rotation shift to sample array
const seed=1;//min=0 max=1000 step=1
const grid = 10; //min=2 max=15 step=1
const polygonOne = 0; //min=0 max=1 step=1 (A regular polygon {x/y} using xOne and yOne, A custom shape using pathOne)
const xOne = 5;//min=2 max=30 step=1
const yOne = 2;//min=1 max=7 step=1
const pathOne  = `M0,-37 C-10,-37 -26,-22 -30,-14 C-32,-10 -38,-3 -35,2 C-28,17 -7,39 13,29
C14,28 17,30 18,29 C59,9 37,-36 -3,-36`; // type=path, Click here to redraw the path
const polygonTwo = 0; //min=0 max=1 step=1 (A regular polygon {x/y} using xTwo and yTwo, A custom shape using pathTwo)
const xTwo = 9;//min=2 max=30 step=1
const yTwo = 2;//min=1 max=7 step=1
const pathTwo = `M0,-38 C0,-16 15,-2 20,18 C21,20 28,36 28,36 L26,36 C21,34 18,28 14,25
C3,17 -7,5 -20,2 C-22,1 -33,-5 -33,-5 L-32,-5 C-27,-5 -22,-5 -17,-5 C-3,-5 11,-6 25,-6 C26,-6 38,-4 38,-4
L23,1 C11,5 -7,18 -18,25 C-22,28 -28,30 -31,33 L-35,37 C-35,36 -26,22 -25,19 C-22,13 -21,6 -18,0
C-12,-12 -2,-24 -2,-37`; // type=path, Click here to redraw the path

const padding = 3;

const sampleTwist = 1/sampleShift**2;

// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);

// Global code will be evaluated once.
const turtle = new Turtle();
const cellSize = (200 - padding - padding) / grid;
const drawSize = cellSize - padding;

// Seedable random number generator by David Bau: http://davidbau.com/archives/2010/01/30/random_seeds_coded_hints_and_quintillions.html
!function(a,b,c,d,e,f,g,h,i){function j(a){var b,c=a.length,e=this,f=0,g=e.i=e.j=0,h=e.S=[];for(c||(a=[c++]);d>f;)h[f]=f++;for(f=0;d>f;f++)h[f]=h[g=s&g+a[f%c]+(b=h[f])],h[g]=b;(e.g=function(a){for(var b,c=0,f=e.i,g=e.j,h=e.S;a--;)b=h[f=s&f+1],c=c*d+h[s&(h[f]=h[g=s&g+b])+(h[g]=b)];return e.i=f,e.j=g,c})(d)}function k(a,b){var c,d=[],e=typeof a;if(b&&"object"==e)for(c in a)try{d.push(k(a[c],b-1))}catch(f){}return d.length?d:"string"==e?a:a+"\0"}function l(a,b){for(var c,d=a+"",e=0;e<d.length;)b[s&e]=s&(c^=19*b[s&e])+d.charCodeAt(e++);return n(b)}function m(c){try{return o?n(o.randomBytes(d)):(a.crypto.getRandomValues(c=new Uint8Array(d)),n(c))}catch(e){return[+new Date,a,(c=a.navigator)&&c.plugins,a.screen,n(b)]}}function n(a){return String.fromCharCode.apply(0,a)}var o,p=c.pow(d,e),q=c.pow(2,f),r=2*q,s=d-1,t=c["seed"+i]=function(a,f,g){var h=[];f=1==f?{entropy:!0}:f||{};var o=l(k(f.entropy?[a,n(b)]:null==a?m():a,3),h),s=new j(h);return l(n(s.S),b),(f.pass||g||function(a,b,d){return d?(c[i]=a,b):a})(function(){for(var a=s.g(e),b=p,c=0;q>a;)a=(a+c)*d,b*=d,c=s.g(1);for(;a>=r;)a/=2,b/=2,c>>>=1;return(a+c)/b},o,"global"in f?f.global:this==c)};if(l(c[i](),b),g&&g.exports){g.exports=t;try{o=require("crypto")}catch(u){}}else h&&h.amd&&h(function(){return t})}(this,[],Math,256,6,52,"object"==typeof module&&module,"function"==typeof define&&define,"random");
Math.seedrandom(''+(seed === 0? Date.now(): seed));
// Add a seed in seedrandom, then Math.random will use this seed

const [topLeftTokens,     topLeftPolygon,     topLeftTokenCount]     = populatePath(polygonOne, xOne, yOne, pathOne, drawSize);
const [bottomRightTokens, bottomRightPolygon, bottomRightTokenCount] = populatePath(polygonTwo, xTwo, yTwo, pathTwo, drawSize);

const [pathMatchTokens, pathTargetTokens] = (() => {
    if(topLeftTokenCount === bottomRightTokenCount) return [topLeftTokens, bottomRightTokens];
    if(topLeftTokenCount < bottomRightTokenCount) return [
        topLeftPolygon === null? fixVertexCountForPath   (topLeftTokens,  bottomRightTokenCount - topLeftTokenCount)
                               : fixVertexCountForPolygon(topLeftPolygon, bottomRightTokenCount - topLeftTokenCount), bottomRightTokens
    ];
    return [topLeftTokens,
        bottomRightPolygon === null? fixVertexCountForPath   (bottomRightTokens,  topLeftTokenCount - bottomRightTokenCount)
                                   : fixVertexCountForPolygon(bottomRightPolygon, topLeftTokenCount - bottomRightTokenCount)
    ];
})();

// The walk function will be called until it returns false.
function walk(i) {
    const row = (grid / 2) - (i / grid | 0) - .5;
    const col = (grid / 2) - (i % grid) - .5;

    const t = 1 - i / (grid**2 - 1);

    switch(method) {
        case 0:
            const intermediatePath = new Path(lerpTokens(pathMatchTokens, pathTargetTokens, t));
            for(let j = 0, max = intermediatePath.length(); j <= max * 2 + 1; j++) {
                turtle[j == 0? 'jump': 'goto'](add2( intermediatePath.p(j/(max * 2)), [col*cellSize, row*cellSize]));
            }
            break;
        case 1:
            const lerped = lerpPaths(sourcePts, targetPts, t);
            const bb = lerped.reduce((p, c) => [[Math.min(p[0][0], c[0]), Math.min(p[0][1], c[1])],[Math.max(p[1][0], c[0]), Math.max(p[1][1], c[1])]], [[Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER], [Number.MIN_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]]);
            const ratio = (cellSize - padding) / Math.max(bb[1][0] - bb[0][0], bb[1][1] - bb[0][1]);
            drawPath(turtle, lerped.map(pt => add2(scale2(pt, ratio), [col*cellSize, row*cellSize])));
            break;
    }

    return i < grid**2 - 1;
}

function populatePath(polygonMode, x, y, path, squareToFitInSize) {
    y = y < 3? y: (x <= 2 * y? 2: y);
    if(polygonMode == 0) {
        const polygon = [getSchlafliRegularPolygonPoints(squareToFitInSize / 2, x, y)].map(v => v.concat([v[0]])).pop();
        const pathTokens = getBezierSvgFromPoints(polygon).match(/([0-9.-]+|[MLC])/g);
        return [pathTokens, polygon, polygon.length];
    }
    
    let tokens = transformLTokensToC(path.match(/([0-9.-]+|[MLC])/g));

    const bb = (new Path(tokens)).bb(.001);
    const ratio = squareToFitInSize / Math.max(bb[1][0] - bb[0][0], bb[1][1] - bb[0][1]);
    const cp = scale2(lerp2(bb[0], bb[1], .5), -1);
    return [scaleTokens(transposeTokens(tokens, cp), ratio), null, tokens.filter(v => v == 'M' || v == 'L' || v == 'C').length];
}

//used for method = bezier
function fixVertexCountForPolygon(polygon, count) {
    let ol = polygon.length;
    const polygonMatch = Array.from({length: count}).reduce((a, c, i, oa) => {
        switch(bezierInserts) {
            //Random, Uniform, Opposite, Top, Bottom
            //uniform inserts are 'uniform' on point index, not on actual distance
            case 0: return addPointOnPath(a);
            case 1: return addPointOnPath(a, (oa.length-i)*(ol-2)/oa.length|0, (oa.length-i)*(ol-2)/oa.length%1);
            case 2: return addPointOnPath(a, i % 2 == 0? 0: ol/2|0, ++ol/2%1);
            case 3: return addPointOnPath(a, 0, 0);
            case 4: return addPointOnPath(a, ol/2|0, ol/2%1);
        }
    }, polygon);
    return getBezierSvgFromPoints(polygonMatch, bezierAmplitude).match(/([0-9.-]+|[MLC])/g);
}
function fixVertexCountForPath(pathTokens, count) { //this assumes path contains one M token at start, and then only C tokens
    let bezierCurveCount = pathTokens.filter(t => t == 'C').length;

    const testPath = new Path(pathTokens);
    const randomAndUniformInserts = Array.from({length: count})
        .map((v, i) => bezierInserts == 0? Math.random(): (i + 1) / (count + 1))
        .sort((a,b) => a-b)
        .map(v => testPath.getSegmentIndexAndRelativeTAt(v).reduce((a,c) => a+c, 0))
        .map((v, i) => v - 1 + i); // - 1 for offset with token manipulation and + i because every loop there's an index shift of 1 for the next
    //const randomAndUniformInserts = Array.from({length: count}).map((v, i, a) => bezierInserts == 0? bezierCurveCount * Math.random(): bezierCurveCount * i / a.length).sort((a,b) => a-b).map((v, i) => v + i);

    for(let i = 0; i < count; i++) {
        switch(bezierInserts) {
            //Random, Uniform, Opposite, Top, Bottom
            //uniform inserts are 'uniform' on point index, not on actual distance
            case 0: //throw new Error('Need to implement that...');
            case 1: insertBezierInPathTokens(pathTokens, randomAndUniformInserts[i] | 0, randomAndUniformInserts[i] % 1); break;
            case 2: insertBezierInPathTokens(pathTokens, i%2 == 0? 0: (bezierCurveCount / 2|0)); break;
            case 3: insertBezierInPathTokens(pathTokens, 0); break;
            case 4: insertBezierInPathTokens(pathTokens, bezierCurveCount / 2|0); break;
        }
        bezierCurveCount++;
    }
    return pathTokens;
}
//end used for method = bezier

//used for method = samples
const sourcePath = new Path(topLeftTokens);
const targetPath = new Path(bottomRightTokens);
const samples = Math.max(sourcePath.length(), targetPath.length()) * 2 | 0;
const sourcePts = Array.from({length: samples + 1}).map((v, i) => sourcePath.p(i/samples));
const targetPts = Array.from({length: samples + 1}).map((v, i) => targetPath.p(i/samples)).map((v, i, a) => a[(i+(samples/(sampleTwist + 1)|0))%a.length]);
//end used for method = samples


// Some token modification functions - Jurgen 2024
function lerpTokens(a, b, p) {
    return a.map((token, index) => {
        if (isNumber(token)) {
            return token * (1-p) + b[index] * p;
        } else return token;
    });
}
function transposeTokens(tokens, v) {
    const round = (x,d=3) => Math.round(x*(10**d))/(10**d);
    for(let i = 0; i < tokens.length;) {
        const transpose = () => {
            tokens[i] = round(1*tokens[i++] + v[0]);
            tokens[i] = round(1*tokens[i++] + v[1]);
        }

        switch(tokens[i++]) {
            case 'C':
                transpose();
                transpose();
            case 'M':
            case 'L':
                transpose();
        }
    }
    return tokens;
}
function scaleTokens(tokens, s) {
    const round = (x,d=3) => Math.round(x*(10**d))/(10**d);
    for(let i = 0; i < tokens.length;) {
        const scale = () => {
            tokens[i] = round(1*tokens[i++] * s);
            tokens[i] = round(1*tokens[i++] * s);
        }

        switch(tokens[i++]) {
            case 'C':
                scale();
                scale();
            case 'M':
            case 'L':
                scale();
        }
    }
    return tokens;
}

function insertBezierInPathTokens (pathTokens, index, segmentLength = 0) {
    const round = (x,d=3) => Math.round(x*(10**d))/(10**d);
    const insertAtIndex = 3 + index * 7; //assuming [M, C, C, C, C, ...]
    const newBeziers = splitBezier(
        [pathTokens[insertAtIndex - 2], pathTokens[insertAtIndex - 1]],
        [pathTokens[insertAtIndex + 1], pathTokens[insertAtIndex + 2]],
        [pathTokens[insertAtIndex + 3], pathTokens[insertAtIndex + 4]],
        [pathTokens[insertAtIndex + 5], pathTokens[insertAtIndex + 6]],
        segmentLength
    );
    pathTokens.splice(insertAtIndex, 7,
        'C', ...newBeziers[0].filter((v, i) => i != 0).flatMap(v => v.map(v => round(v))),
        'C', ...newBeziers[1].filter((v, i) => i != 0).flatMap(v => v.map(v => round(v)))
    );
    return pathTokens;
}

function getSvgFromPoints(pts) {
    if(pts.length == 0) return 'M0,0';
    return pts.map((v, i) => (i == 0? 'M':'L')+v.map(x => Math.round(x*1000)/1000).join(',')).join(' ');
}
function getBezierSvgFromPoints(pts, cpLength = .5) {
    if(pts.length == 0) return 'M0,0';
    
    const round = (pt,d=3) => pt.map(x => Math.round(x*(10**d))/(10**d));
    const scale = (a,s) => [a[0]*s, a[1]*s];
    const add = (a,b) => [a[0]+b[0],a[1]+b[1]]
    const subtract = (a,b) => [a[0]-b[0],a[1]-b[1]];
    return pts.map((v, i, a) => (i == 0? 'M'+round(v).join(','):'C'+[
        round(add(a[i-1], scale(subtract(v, a[i-1]), cpLength))).join(','),
        round(add(a[i-1], scale(subtract(v, a[i-1]), 1 - cpLength))).join(','),
        round(v).join(',')].join(' ')
    )).join(' ');
}
function transformLTokensToC(tokens) {
    const result = [];

    const round = (pt,d=3) => pt.map(x => Math.round(x*(10**d))/(10**d));
    const scale = (a,s) => [a[0]*s, a[1]*s];
    const add = (a,b) => [a[0]+b[0],a[1]+b[1]]
    const subtract = (a,b) => [a[0]-b[0],a[1]-b[1]];

    for(let i = 0; i < tokens.length; i++) {
        if(tokens[i] != 'L') {
            result.push(tokens[i]);
            continue;
        }
        // Since path only supports MCL (not lowercase), I can assume the last 2 digits are last location
        const lastPos = [tokens[i-2], tokens[i-1]];
        const destPos = [tokens[++i], tokens[++i]];

        result.push(
            'C',
            ...round(add(scale(lastPos, 1), scale(subtract(destPos, lastPos), .3))),
            ...round(add(scale(lastPos, 1), scale(subtract(destPos, lastPos), .7))),
            ...destPos
        );
    }
    return result;
    result.forEach(v => console.log(v));
}

function isNumber(n) {
    return !isNaN(parseFloat(n)) && isFinite(n);
}


/// Below is the standard lib I just copy paste under almost all my turtles

function approx1(a,b,delta=0.0001) { return -delta < a-b && a-b < delta }

////////////////////////////////////////////////////////////////
// 2D Vector Math utility code - Created by several Turtletoy users
////////////////////////////////////////////////////////////////
function norm2(a) { return scale2(a, 1/len2(a)); }
function add2(a, b) { return [a[0]+b[0], a[1]+b[1]]; }
function sub2(a, b) { return [a[0]-b[0], a[1]-b[1]]; }
function mul2(a, b) { return [a[0]*b[0], a[1]*b[1]]; }
function scale2(a, s) { return [a[0]*s,a[1]*s]; }
function lerp2(a,b,t) { return [a[0]*(1-t) + b[0]*t, a[1]*(1-t) + b[1]*t]; }
function lenSq2(a) { return a[0]**2+a[1]**2; }
function len2(a) { return Math.sqrt(lenSq2(a)); }
function rot2(a) { return [Math.cos(a), -Math.sin(a), Math.sin(a), Math.cos(a)]; }
function trans2(m, a) { return [m[0]*a[0]+m[2]*a[1], m[1]*a[0]+m[3]*a[1]]; } //Matrix(2x1) x Matrix(2x2)
function dist2(a,b) { return Math.hypot(...sub2(a,b)); }
function dot2(a,b) { return a[0]*b[0]+a[1]*b[1]; }
function cross2(a,b) { return a[0]*b[1] - a[1]*b[0]; }
function multiply2(a2x2, a) { return [(a[0]*a2x2[0])+(a[1]*a2x2[1]),(a[0]*a2x2[2])+(a[1]*a2x2[3])]; } //Matrix(2x2) x Matrix(1x2)
function intersect_info2(as, ad, bs, bd) {
    const d = [bs[0] - as[0], bs[1] - as[1]];
    const det = bd[0] * ad[1] - bd[1] * ad[0];
    if(det === 0) return false;
    const res = [(d[1] * bd[0] - d[0] * bd[1]) / det, (d[1] * ad[0] - d[0] * ad[1]) / det];
    return [...res, add2(as, scale2(ad, res[0]))];
}
function intersect_ray2(a, b, c, d) {
    const i = intersect_info2(a, b, c, d);
    return i === false? i: i[2];
}
function segment_intersect2(a,b,c,d, inclusive = true) {
    const i = intersect_info2(a, sub2(b, a), c, sub2(d, c));
    if(i === false) return false;
    const t = inclusive? 0<=i[0]&&i[0]<=1&&0<=i[1]&&i[1]<=1: 0<i[0]&&i[0]<1&&0<i[1]&&i[1]<1;
    return t?i[2]:false;
}
function approx2(a,b,delta=0.0001) { return len2(sub2(a,b)) < delta }
function eq2(a,b) { return a[0]==b[0]&&a[1]==b[1]; }
function clamp2(a, tl, br) { return [Math.max(Math.min(br[0], a[0]), tl[0]), Math.max(Math.min(br[1], a[1]), tl[1])]; }
function nearSq2(test, near, delta = .0001) {
    return near[0] - delta < test[0] && test[0] < near[0] + delta &&
           near[1] - delta < test[1] && test[1] < near[1] + delta;
}

////////////////////////////////////////////////////////////////
// Start of some path utility code - Created by Jurgen Westerhof 2023
////////////////////////////////////////////////////////////////
function circlePoints(radius, extend = 2 * Math.PI, clockWiseStart = 0, steps = null, includeLast = false) { return [steps == null? (radius*extend+1)|0: steps].map(steps => Array.from({length: steps}).map((v, i, a) => [radius * Math.cos(clockWiseStart + extend*i/(a.length-(includeLast?1:0))), radius * Math.sin(clockWiseStart + extend*i/(a.length-(includeLast?1:0)))])).pop(); }
function pts2Edges(pts) { return pts.map((v, i, a) => [v, a[(i+1)%a.length]]); }
function drawPath(turtle, pts) { return pts.forEach((pt, i) => turtle[i == 0? 'jump':'goto'](pt)); }
function drawTour(turtle, pts) { return drawPath(turtle, pts.concat([pts[0]])); }
function drawPoint(turtle, pt) { return drawTour(turtle, circlePoints(.5).map(p => add2(p, pt))); }
function isInPolygon(edges, pt) { return edges.map(edge => intersect_info2(edge[0], sub2(edge[1], edge[0]), pt, [0, 300])).filter(ii => ii !== false && 0 <= ii[0] && ii[0] <= 1 && 0 < ii[1]).length % 2 == 1; }
function isInVectorTour(vectors, pt) { return vectors.map(v => intersect_info2(...v, pt[0], pt[1])).filter(ii => ii !== false && 0 <= ii[0] && ii[0] < 1 && 0 <= ii[1]).length % 2 == 1; }
function tourToVectors(path) { return path.map((v, i, a) => [v, sub2(a[(i+1)%a.length], v)]); }
function thickLinePaths(from, to, thickness) { return [trans2(rot2(Math.atan2(...sub2(to, from))), [thickness/2, 0])].map(v => [[add2(from, v), add2(to, v)], [sub2(from, v), sub2(to, v)]]).pop();}
function toursIntersect(path1, path2) { return path1.some((pt1, i1) => path2.some((pt2, i2) => segment_intersect2(pt1, path1[(i1 + 1) % path1.length], pt2, path2[(i2 + 1) % path2.length]) !== false)); }

function pathsIntersect(path1, path2) { return path1.some((pt1, i1) => 
        i1 == path1.length - 1? false: path2.some((pt2, i2) => 
            i2 == path2.length - 1? false: 
            segment_intersect2(pt1, path1[i1 + 1], pt2, path2[i2 + 1]) !== false
        )
    );
}
function pathsIntersections(path1, path2) { return path1.flatMap((pt1, i1) => 
        i1 == path1.length - 1? [[false]]: path2.map((pt2, i2) => 
            i2 == path2.length - 1? [false]: 
            [segment_intersect2(pt1, path1[i1 + 1], pt2, path2[i2 + 1]), i1, i2]
        )
    ).filter(v => v[0] !== false);
}

function addPointOnPath(pts, atIndex = null, atSegmentLength = null) {
    const lerp = (a,b,t) => [a[0]*(1-t) + b[0]*t, a[1]*(1-t) + b[1]*t];
    const index = atIndex === null? Math.random() * (pts.length - 1) | 0: atIndex;
    const copy = pts.map(pt => [...pt]);
    copy.splice(index + 1, 0, lerp(pts[index], pts[index+1], atSegmentLength === null? Math.random(): atSegmentLength))
    return copy;
}
function lerpPaths(a, b, p) { return a.map((pt, i) => lerp2(pt, b[i], p)); }

function getSchlafliRegularPolygonPoints(outerRadius, x, y = 2) {
    if(x == 1) return [0,0];
    const ptsOne = circlePoints(outerRadius, 2 * Math.PI, -Math.PI/2, x);
    const ptsTwo = circlePoints(getInnerRadiusForPolyStar(outerRadius, x, y), 2 * Math.PI, Math.PI / x - Math.PI/2, x);
    
    return ptsOne.flatMap((v, i) => [v, ptsTwo[i]]);
}

function getInnerRadiusForPolyStar(outerRadius, x, y = 2) {
    if(x < 3) return 0;
    const pts = circlePoints(outerRadius, 2 * Math.PI, 0, x);
    if(y == 1) return len2(add2(pts[0], scale2(sub2(pts[1], pts[0]), .5)));
    if(x < 5) return 0;
    return len2(segment_intersect2(pts[0], pts[y], pts[1], pts[y + 1]));
}


function splitBezier(a, b, c, d, t) { // https://stackoverflow.com/questions/18655135/divide-bezier-curve-into-two-equal-halves#18681336
    const e = lerp2(a, b, t);
    const f = lerp2(b, c, t);
    const g = lerp2(c, d, t);
    const h = lerp2(e, f, t);
    const j = lerp2(f, g, t);
    const k = lerp2(h, j, t);
    return [[a, e, h, k], [k, j, g, d]];
}

////////////////////////////////////////////////////////////////
// Modified path utility code. Created by Reinder Nijhoff 2023
//
// Added a distance method
//
// Parses a single SVG path (only M, C and L statements are
// supported). The p-method will return
// [...position, ...derivative] for a normalized point t.
//
// https://turtletoy.net/turtle/46adb0ad70
//
// Modified by Jurgen Westerhof 2024
// - added bb() to get boundingBox [[topLeft], [bottomRight]]
// - added size() to get [width, height] of boundingBox
// - changed Path argument to also accept pre-tokenized string
// - added draw(turtle) which treats non-first M tokens as L
////////////////////////////////////////////////////////////////
function Path(svg) {
    function lenSquare(a) { return a[0]**2 + a[1]**2; }
    function dot(a, b) { return a[0]*b[0]+a[1]*b[1]; }
    function distSegmentSquare(p, a, b ) {
    	const pa = [p[0]-a[0], p[1]-a[1]], ba = [b[0]-a[0], b[1]-a[1]];
	    const h = Math.max(0, Math.min(1, dot(pa,ba)/dot(ba,ba)));
	    return lenSquare( [pa[0] - ba[0]*h, pa[1] - ba[1]*h] );
    }
    
    class MoveTo {
        constructor(p) { this.p0 = p; }
        p(t, s) { return [...this.p0, 1, 0]; }
        length() { return 0; }
        distSquare(p, res) { return lenSquare([p[0]-this.p0[0], p[1]-this.p0[1]]); }
    }
    class LineTo {
        constructor(p0, p1) { this.p0 = p0, this.p1 = p1; }
        p(t, s = 1) {
            const nt = 1 - t, p0 = this.p0, p1 = this.p1;
            return [ 
                nt*p0[0] + t*p1[0],
                nt*p0[1] + t*p1[1],
                (p1[0] - p0[0]) * s,
                (p1[1] - p0[1]) * s,
            ];
        }
        length() { 
            const p0 = this.p0, p1 = this.p1;
            return Math.hypot(p0[0]-p1[0], p0[1]-p1[1]);
        }
        distSquare(p, res) {
            return distSegmentSquare(p, this.p0, this.p1);
        }
    }
    class BezierTo {
        constructor(p0, c0, c1, p1) { this.p0 = p0, this.c0 = c0, this.c1 = c1, this.p1 = p1; }
        p(t, s = 1) {
            const nt = 1 - t, p0 = this.p0, c0 = this.c0, c1 = this.c1, p1 = this.p1;
            return [ 
                nt*nt*nt*p0[0] + 3*t*nt*nt*c0[0] + 3*t*t*nt*c1[0] + t*t*t*p1[0],
                nt*nt*nt*p0[1] + 3*t*nt*nt*c0[1] + 3*t*t*nt*c1[1] + t*t*t*p1[1],
                (3*nt*nt*(c0[0]-p0[0]) + 6*t*nt*(c1[0]-c0[0]) + 3*t*t*(p1[0]-c1[0])) * s,
                (3*nt*nt*(c0[1]-p0[1]) + 6*t*nt*(c1[1]-c0[1]) + 3*t*t*(p1[1]-c1[1])) * s,
            ];
        }
        length() {
            return this._length || (
                this._length = Array.from({length:25}, (x, i) => this.p(i/25)).reduce( 
                    (a,c,i,v) => i > 0 ? a + Math.hypot(c[0]-v[i-1][0], c[1]-v[i-1][1]) : a, 0));
        }
        distSquare(p, res) {
            // super slow, probably better to use an analytical solution if exists
            const segments = Math.max(1, this.length()/res | 0);
            const p0 = this.p0, c0 = this.c0, c1 = this.c1, p1 = this.p1;
            
            let a = [...p0];
            let dist = 1e10;
            
            for (let i=1; i<=segments; i++) {
                const t = i/segments, nt = 1 - t;
                const b = [
                    nt*nt*nt*p0[0] + 3*t*nt*nt*c0[0] + 3*t*t*nt*c1[0] + t*t*t*p1[0],
                    nt*nt*nt*p0[1] + 3*t*nt*nt*c0[1] + 3*t*t*nt*c1[1] + t*t*t*p1[1]
                ];
                dist = Math.min(dist, distSegmentSquare(p, a, b));
                a = [...b];
            }
            return dist;
        }
    }
    class Path {
        constructor(svg) {
            this.segments = [];
            this.parsePath(svg);
        }
        parsePath(svg) {
            this.tokens = typeof(svg) == 'string'? svg.match(/([0-9.-]+|[MLC])/g): svg;
            for (let s, i=0; i<this.tokens.length;) {
                switch (this.tokens[i++]) {
                    case 'M': this.add(new MoveTo(s=[this.tokens[i++],this.tokens[i++]]));
                              break;
                    case 'L': this.add(new LineTo(s, s=[this.tokens[i++],this.tokens[i++]]));
                              break;
                    case 'C': this.add(new BezierTo(s, [this.tokens[i++],this.tokens[i++]], [this.tokens[i++],this.tokens[i++]], s=[this.tokens[i++],this.tokens[i++]]));
                              break;
                    default:  i++;
                }
            }
        }
        getTokens() {
            return this.tokens;
        }
        add(segment) {
            this.segments.push(segment);
            this._length = 0;
            
            this._bb = undefined;
            this._size = undefined;
        }
        length() {
            return this._length || (this._length = this.segments.reduce((a,c) => a + c.length(), 0));
        }
        getSegmentIndexAndRelativeTAt(t) {
            t = Math.max(Math.min(t, 1), 0) * this.length();
            for (let l=0, i=0, sl=0; i<this.segments.length; i++, l+=sl) {
                sl = this.segments[i].length();
                if (t > l && t <= l + sl) {
                    return [i, (t-l)/sl];
                }
            }
            return [this.segments.length-1, 1];
        }
        p(t) {
            t = Math.max(Math.min(t, 1), 0) * this.length();
            for (let l=0, i=0, sl=0; i<this.segments.length; i++, l+=sl) {
                sl = this.segments[i].length();
                if (t > l && t <= l + sl) {
                    return this.segments[i].p((t-l)/sl, sl/this.length());
                }
            }
            return this.segments[Math.min(1, this.segments.length-1)].p(0);
        }
        distance(p, res = 3) {
            return Math.sqrt(this.segments.reduce((a,c) => Math.min(a, c.distSquare(p, res)), 1e10));
        }
        bb(sampleRate = null) {
            if(sampleRate === null) {
                sampleRate = 1/this.length();
            }
            if(this._bb === undefined) {
                this._bb = Array.from({length: 1 / sampleRate + 1})
                                .map((v, i) => this.p(i * sampleRate))
                                .reduce((p, c) => [[Math.min(p[0][0], c[0]), Math.min(p[0][1], c[1])],[Math.max(p[1][0], c[0]), Math.max(p[1][1], c[1])]], [[Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER], [Number.MIN_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]]);
            }
            return this._bb;
        }
        size(sampleRate = null) {
            if(this._size === undefined) {
                this._size = [this.bb(sampleRate)].map(v => [v[1][0] - v[0][0], v[1][1] - v[0][1]]).pop();
            }
            return this._size;
        }
        draw(turtle) { //this does not support M tokens because the turtle only jumps when i == 0
            for(let i = 0, max = this.length() * 2; i <= max; i++) {
                turtle[i == 0? 'jump': 'goto'](this.p(i/max));
            }
        }
    }
    return new Path(svg);
}