Voronoi study 局

My take on Voronoi diagrams using Delaunay triangulation.

(A look into debugging this thing: Voronoi study 局 (variation) and Voronoi study 局 (variation))

Log in to post a comment.

const seed = 10000; //min=10000 max=99999 step=1
const n = 200; //min=4 max=600 step=1
const padding = 0; //min=0 max=90 step=1
const mirrorEdges = 1; //min=0 max=1 step=1 (No, Yes)
const dSources = 0; //min=0 max=1 step=1 (No, Yes)
const dVoronoiLines = 1; //min=0 max=1 step=1 (No, Yes)
const drawMode = 1; //min=0 max=1 step=1 (dDelaunayX, dPolygonX)
const dDelaunayPoints = 0; //min=0 max=1 step=1 (No, Yes)
const dDelaunayCircles = 0; //min=0 max=1 step=1 (No, Yes)
const dDelaunayTriangles = 0; //min=0 max=1 step=1 (No, Yes)
const dPolygonShrink = .9; //min=0 max=1.5 step=.1
const dPolygonArtBorder = 5; //min=0 max=30 step=1
const dPolygonArtShape = 2; //min=2 max=10 step=1 (Circle, Triangle, Square, Pentagon, Hexagon, Heptagon, Octagon, Nonagon, Decagon)
const dPolygonHatching = 1; //min=0 max=5 step=1 (None, Random, Circular gradient, Circular gradient inverted, Gradient, Inverted gradient)
const dPolygonHatchDir = 0; //min=0 max=2 step=1 (Random, Centralized, Centralized othogonal)
const dPolygonHatchMin = .31; //min=.01 max=1.6 step=.05
const dPolygonHatchMax = .51; //min=.01 max=1.6 step=.05
const dPolygonBackground = 0; //min=0 max=2 step=1 (None, Gradient up, Gradient down)
const debug = false;

const dPolygonHatchMaxc = Math.max(dPolygonHatchMin, dPolygonHatchMax);

// 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 polygons = new Polygons();

function normalize2(a) { const length = len2(a); return scale2(a,length<0.0001?1:1/length); }
function len2(a) { return Math.sqrt(lensq2(a)); }
function lensq2(a) { return dot2(a,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]]; }
function scale2(a,b) { return [a[0]*b,a[1]*b]; }
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 dist2(a,b) { return Math.hypot(...sub2(a,b)); }
function lerp2(a,b,t) { return [a[0]*(1-t)+b[0]*t,a[1]*(1-t)+b[1]*t]; }
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 mulf2(v, f) { return scale2(v,f); }
function multiply2(a2x2, a) { return [(a[0]*a2x2[0])+(a[1]*a2x2[1]),(a[0]*a2x2[2])+(a[1]*a2x2[3])]; }
function segment_intersect2(a,b,d,c, inclusive = true) {
    const e=(c[1]-d[1])*(b[0]-a[0])-(c[0]-d[0])*(b[1]-a[1]);
    if(0==e)return false;
    c=((c[0]-d[0])*(a[1]-d[1])-(c[1]-d[1])*(a[0]-d[0]))/e;
    d=((b[0]-a[0])*(a[1]-d[1])-(b[1]-a[1])*(a[0]-d[0]))/e;
    const t = inclusive? 0<=c&&1>=c&&0<=d&&1>=d: 0<c&&1>c&&0<d&&1>d;
    return t?[a[0]+c*(b[0]-a[0]),a[1]+c*(b[1]-a[1])]:false;
}
function eq2(a,b) { return a[0]==b[0]&&a[1]==b[1]; }

// 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('anything here' + seed);
// Add a seed in seedrandom, then Math.random will use this seed

const randomPoint = () => [2*Math.random()*(100-padding)-(100-padding),2*Math.random()*(100-padding)-(100-padding)];

//We start with one randomly chosen point in our points list
const pts = [randomPoint()];
//While there are not yet a certain number of points chosen
while(pts.length < n) {
    //add a point to the list
    pts.push(
        //using [length] candidate points
        Array.apply(null,{length: 10})
             //which are random points
             .map(i => randomPoint())
             //then add a distance to that candidate
             .map(i => [i[0], i[1], pts.map(j => [j[0], j[1], dist2(i, j)])
                                       //so that it is the smallest distance from the
                                       //candidate to any of the already chosen points
                                       .reduce((prev, current) => (current[2] < prev[2])? current: prev, [0,0,500])[2]
                ])
             //then pick the candidate that has the largest minimum distance from the group of candidates
             .reduce((prev, current) => (current[2] > prev[2])? current: prev, [0,0,0])
             //and remove the distance before promoting the candidate
             .filter((i, k) => k < 2)
    );

}

/*
turtle.jump([0,-100]);
turtle.goto([0, 100]);
turtle.jump([-100, 0]);
turtle.goto([100, 0]);
*/

/////////----------------- TEST CASES ------------------////////
//two outside circles
//const pts = [[0, -20], [70, 0], [0, 20], [-60, 20], [0, 50]];

//one inside circle, outside hull
//const pts = [[0, -20], [70, 0], [-30, 50], [30, 50]];
//one inside circle outside another, outside hull
//const pts = [[0, -10], [50, 0], [0, 25], [-50, 50], [25, 34]];

//point inside triangle, once circle
//const pts = [[0, -20], [70, 0], [0, 20], [25, 0]];
//point inside triangle, two circles
//const pts = [[0, -20], [70, 0], [0, 20], [25, 0], [20, 10]];
//point on a non-shared edge
//const pts = [[0, 50], [50, 50], [0, -50], [0,0]];

//point on a non-shared edge, but in 'another' circle
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30]];
//pts.push(add2(pts[0], scale2(sub2(pts[1], pts[0]), .8)));

//point on a shared edge
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30], [30, 0]];

//point on a shared edge and in 'another' circle
//const pts = [[20, -70], [70, 0], [0, 0], [20, 30], [0, 20], [30, 0]];
/////////----------------- END TEST CASES ------------------////////

class DelaunayTriangulation {
    constructor(pts) {
        if(pts.length < 3) {
            throw new Error('What u do?');
        }
        this.points = pts.filter((i, k) => k < 3);
        this.log('init points 1, 2, 3', ...this.points);
        this.circles = [];
        this.convexHullEdges = [[0, 1], [1, 2], [0, 2]];
        
        this.addCircle(0, 1, 2);

        pts.filter((i, k) => k > 2).forEach(i => this.add(i));
    }
    log(...msg) {
        if(debug) {
            console.log(...msg);
        }
    }
    addCircle(...idxs) {
        this.circles.push(this.getCircle(...idxs));
        return this.circles.length - 1;
    }
    getCircle(...idxs) {
        if(idxs.length != 3) throw new Error('Expecting 3 arguments at getCircle()');
        idxs.sort();
        const cc = this.getSmallestCircumscribedCircleCenter(...idxs.map(i => this.points[i]));
        const r = lensq2(sub2(cc, this.points[idxs[0]]));
        return [cc, r, [...idxs]];
    }
    // https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_2
    getSmallestCircumscribedCircleCenter(pt1, pt2, pt3) {
        const D = 2 * (
            (pt1[0] * (pt2[1] - pt3[1])) + 
            (pt2[0] * (pt3[1] - pt1[1])) + 
            (pt3[0] * (pt1[1] - pt2[1]))
        );
        
        return [(
                ((pt1[0]**2 + pt1[1]**2) * (pt2[1] - pt3[1])) +
                ((pt2[0]**2 + pt2[1]**2) * (pt3[1] - pt1[1])) +
                ((pt3[0]**2 + pt3[1]**2) * (pt1[1] - pt2[1]))
            ) / D,
            (
                ((pt1[0]**2 + pt1[1]**2) * (pt3[0] - pt2[0])) +
                ((pt2[0]**2 + pt2[1]**2) * (pt1[0] - pt3[0])) +
                ((pt3[0]**2 + pt3[1]**2) * (pt2[0] - pt1[0]))
            ) / D
        ];
    }
    // https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle#2049593
    isPointContainedInTriangle(trianglePointIndices, pt) {
        const sign = (p1, p2, p3) => (p1[0]-p3[0]) * (p2[1]-p3[1]) - (p2[0]-p3[0]) * (p1[1]-p3[1]);
        
        const d = trianglePointIndices.map(i => this.points[i]).map((p, idx, src) => sign(pt, p, src[(idx+1)%src.length]));
        
        return !(d.reduce((p, c) => p || (c < 0), false) && d.reduce((p, c) => p || (c > 0), false));
    }
    drawTriangles(t) {
        //const edges = this.circles.map((c, i) => [c[2][i], c[2][(i+1)%3]]);
        this.circles.forEach(c => {
            const edges = c[2].map((p, i) => [p, c[2][(i+1)%3]]).map(e => [e, this.edgeIsPartOfConvexHull(e)]);
            
            edges.forEach(e => {
                const pts = [this.points[e[0][0]], this.points[e[0][1]]];
                t.jump(pts[0]); t.goto(pts[1]);
                if(e[1]) {
                    [[1, 0], [0, 1], [-1, 0], [0, -1]].map(i => scale2(i, .2)).forEach(d => {
                        t.jump(add2(pts[0], d));
                        t.goto(add2(pts[1], d));
                    });
                }
            })
        });
    }
    drawCircles(t) {
        this.circles.forEach(c => {
            t.jump(c[0][0], c[0][1] - Math.sqrt(c[1]));
            t.circle(Math.sqrt(c[1]));
        });
    }
    drawPoints(t) {
        this.circles.forEach(c => {
            drawPoint(t, c[0], .5);
        });
    }
    edgeIsPartOfConvexHull(edge) {
        edge = edge[0] < edge[1]? [edge[0], edge[1]]: [edge[1], edge[0]];//sort();
        return this.convexHullEdges.filter(che => eq2(che, edge)).length > 0;
    }
    add(pt) {
        const arrayIntersection = (array1, array2) => array1.filter(value => array2.includes(value));
        const arrayDifference = (array1, array2) => array1.filter(value => !array2.includes(value)).concat(array2.filter(value => !array1.includes(value)));
        const flip = (idx1, idx2) => {
            const intersect = arrayIntersection(this.circles[idx1][2], this.circles[idx2][2])
            const uniques = [
                arrayDifference(this.circles[idx1][2], intersect)[0],
                arrayDifference(this.circles[idx2][2], intersect)[0]
            ];
            this.circles[idx1] = this.getCircle(intersect[0], ...uniques);
            this.circles[idx2] = this.getCircle(intersect[1], ...uniques);
            
            return this.edgeIsPartOfConvexHull(intersect);
        }

        //add the point to the list
        this.points.push(pt);
        let convexHullUpdateNeeded = false;
        
        const inCircleIndices = this.circles.map((i, idx) => [idx, i]).filter(c => lensq2(sub2(c[1][0], pt)) <= c[1][1]).map(i => i[0]);
        const inTriangleIndices = inCircleIndices.filter(c => this.isPointContainedInTriangle(this.circles[c][2], pt));
        if(inTriangleIndices.length == 0) {
            //the new point is outside of circles and by definition outside convex hull
            //   find convexhull edges that are not connecting to p that intersect pt-p
            //   and if there are, return false (exclude that point)
            const connectToPoints = this.points.filter((p, pIdx) => this.convexHullEdges
                .filter(che => che[0] != pIdx && che[1] != pIdx)
                .filter(che => false !== segment_intersect2(pt, p, this.points[che[0]], this.points[che[1]])).length === 0
            ).map(i => this.points.indexOf(i));

            //so because the new point is outside circles we can just add it to all convex hull edges where their points are all in the connectToPoints

            //get the combinations (length 2) of all points to connect to internally sorted by index in this.points
            const possibleEdges = connectToPoints.flatMap((i, idx) =>
                connectToPoints.filter((ii, iidx) => iidx > idx).map(ii => [i, ii])
            );
            
            //get all convex hull edges associated with the points (valid combinations)
            const hullEdges = this.convexHullEdges.filter(i => possibleEdges.filter(ii => eq2(ii, i)).length > 0);

            //create new circles for every new triangle
            hullEdges.forEach((he, idx) => {
                this.addCircle(...he, this.points.length - 1);
            });
            
            convexHullUpdateNeeded = true;
        } else {
            //is the point on an edge?
            const edge = [[0, 1], [1, 2], [0, 2]].map(i =>
                [this.circles[inTriangleIndices[0]][2][i[0]], this.circles[inTriangleIndices[0]][2][i[1]]]
            ).filter(edge => len2(sub2(this.points[edge[0]], this.points[edge[1]]))
                ==
                len2(sub2(this.points[edge[0]], this.points[this.points.length - 1])) +
                len2(sub2(this.points[edge[1]], this.points[this.points.length - 1]))
            );
            const onEdge = edge.length == 0? false: (
                edge[0][0] < edge[0][1]? [edge[0][0], edge[0][1]]: [edge[0][1], edge[0][0]]
            );
            
            if(onEdge === false) {
                [[0, 1], [1, 2], [0, 2]].map(i =>
                    [this.circles[inTriangleIndices[0]][2][i[0]], this.circles[inTriangleIndices[0]][2][i[1]], this.points.length - 1]
                ).forEach((i, k) => {
                    k == 0? this.circles[inTriangleIndices[0]] = this.getCircle(...i): this.addCircle(...i);
                });
            } else {
                convexHullUpdateNeeded = this.edgeIsPartOfConvexHull(onEdge);
                
                inTriangleIndices.forEach(iti => {
                    const unique = arrayDifference(this.circles[iti][2], onEdge)[0];
                    this.circles[iti] = this.getCircle(onEdge[0], unique, this.points.length - 1);
                    this.addCircle(onEdge[1], unique, this.points.length - 1);
                });
            }
        }

        while (true) {
            const inCircleIdxs = this.circles.map((i, idx) => [idx, i]).filter(c => lensq2(sub2(c[1][0], pt)) <= c[1][1]).map(i => i[0]);
            const ownCircleIdxs = this.circles.map((i, idx) => [idx, i]).filter(i => i[1][2].includes(this.points.length - 1)).map(i => i[0]);
            const otherCircleIdxs = inCircleIdxs.filter(i => !ownCircleIdxs.includes(i));

            if(otherCircleIdxs.length == 0) break;

            otherCircleIdxs.forEach(c => {
                const commonCircleIndex = ownCircleIdxs
                    .map(i => [i, arrayIntersection(this.circles[i][2], this.circles[c][2])])
                    .filter(i => i[1].length == 2)[0];

                if(commonCircleIndex === undefined) return;

                //switch triangles
                convexHullUpdateNeeded = flip(c, commonCircleIndex[0]) || convexHullUpdateNeeded;
            });
        };

        this.log('added point ' + this.points.length, this.points[this.points.length - 1]);

        //reset the convex hull
        if(convexHullUpdateNeeded) {
            this.refreshConvexHull();
        }
    }
    refreshConvexHull() {
        //get all the edges from triangles;
        const edges = this.circles.flatMap(c => [[c[2][0], c[2][1]], [c[2][1], c[2][2]], [c[2][0],c[2][2]]]).map(i => i[0] < i[1]? [i[0], i[1]]: [i[1], i[0]]);
        //see which are shared
        const duplicates = edges.filter((e, i) => edges.filter((ee, ii) => ii > i && eq2(ee, e)).length > 0);
        //the ones that are not shared make up the hull
        this.convexHullEdges = edges.filter(e => duplicates.filter(d => eq2(e, d)).length == 0).map(e => e[0] < e[1]? [e[0], e[1]]: [e[1], e[0]]);
    }
    finalize(width, height) {
        //get the unique points that are part of the convex hull
        const pts = this.points.filter(
            (p, i) => this.convexHullEdges.flatMap(i => i)
                          .filter((p, ii, s) => s.indexOf(p) === ii).includes(i)
        );
        //add those points mirrored in the edges of the canvas
        [
            ...pts.filter(p => p[0] < 0).map(p => [-p[0] - width - 5, p[1]]), //mirror left
            ...pts.filter(p => p[0] > 0).map(p => [-p[0] + width + 5, p[1]]), //mirror right
            ...pts.filter(p => p[1] < 0).map(p => [p[0], -p[1] - height - 5]), //mirror top
            ...pts.filter(p => p[1] > 0).map(p => [p[0], -p[1] + height + 5]), //mirror bottom
        ].forEach(p => this.add(p));
    }
}

const drawPoint = (t, p, r = 1) => { t.jump(p[0], p[1] - (r/2)); t.circle(r); }

class VoronoiDiagram {
    constructor(delaunayTriangulation) {
        this.dt = delaunayTriangulation;
        this.dtMap = this.dt.circles.
            map(c => [c[0], [[0, 1], [1, 2], [0, 2]].map(vte => [c[2][vte[0]], c[2][vte[1]]])]);
    }
    draw(t) {
        this.dtMap.forEach((s, ks) => {
            this.dtMap
                .filter((c, kc) => kc < ks) // not the same as source or previous
                .filter(c => //find any edge of c[2] in s[2]
                    c[1].filter(cc => s[1].filter(ss => eq2(ss, cc)).length > 0).length > 0
                )
                .forEach(c => {
                    t.jump(s[0]);
                    t.goto(c[0]);
                })
        });
    }
    getPolygonPoints(withPointIndex = false) {
        const arrayIntersection = (array1, array2) => array1.filter(value => array2.includes(value));

        //find all circles associated with each point [[pointIndex, [circles]], ...]
        const circlesPerPoint = this.dt.points.map(
            (p, i) => [i, this.dt.circles.filter(c => c[2].includes(i))]
        ).filter(p => p[1].length > 2); // for a complete polygon, it should at least have 3 edges
        
        //find all indices of circles that have a completed polygon
        // e.g. from the first circle, find circles that have an edge in common until the last one connects to the first one again
        // in other words, each circle should have two other circles that each have a Delaunay Triangle edge in common with it
        const pointIndicesWithFullVoronoiPolygon = circlesPerPoint.map(cpp => [cpp[0], cpp[1].map(cs => 
            cpp[1].filter(cppc => arrayIntersection(cs[2], cppc[2]).length == 2).length == 2
        ).reduce((p, c) => p && c, true)]).filter(c => c[1] == true).map(c => c[0]);

        // then order the points in such a way that that the path 'rotates' around the source point.
        return circlesPerPoint.filter(p => pointIndicesWithFullVoronoiPolygon.includes(p[0])).map(p => {
            return [p[0], p[1].map(c => [c[0], Math.atan2(...sub2(c[0], this.dt.points[p[0]]))])
                       .sort((a, b) => a[1] < b[1]? -1: 1)
                       .map(c => c[0])];
        }).map(p => withPointIndex? p: p[1]);
    }
}

const tri = new DelaunayTriangulation(pts);

if(mirrorEdges) tri.finalize(200, 200);

const vd = new VoronoiDiagram(tri);

const modClip = (val, lowerBound, upperBound) => { const diff = upperBound - lowerBound; while(val < lowerBound) val += diff; while(val > upperBound) val -= diff; return val; }
const regularPolygonPoint = (theta, polygonEdgeCount) => scale2([Math.cos(theta * Math.PI * 2), Math.sin(theta * Math.PI * 2)], Math.cos(Math.PI / polygonEdgeCount) / Math.cos(modClip(theta * Math.PI * 2, 0, Math.PI * 2 / polygonEdgeCount) - (Math.PI / polygonEdgeCount)))


if(drawMode === 0) {
    if(dDelaunayTriangles) tri.drawTriangles(turtle);
    if(dDelaunayPoints) tri.drawPoints(turtle);
    if(dDelaunayCircles) tri.drawCircles(turtle);
    if(dVoronoiLines) vd.draw(turtle);
    if(dSources) pts.forEach(i => drawPoint(turtle, i));
} else if(drawMode == 1) {
    if(dPolygonArtBorder > 0) {
        [
            [91, 92],
            [93, 95],
            [96, 99],
            [100, 400 + dPolygonArtBorder],
        ].map(i => i.map(ii => ii - dPolygonArtBorder)).forEach(r => {
            const pts = [];
            const max =  dPolygonArtShape == 2? 120: dPolygonArtShape;
            r.forEach((rr, rrIdx) => {
                Array.from({length: max + 1}).forEach((d, j) => {
                    let pt;
                    switch(dPolygonArtShape) {
                        case 2:
                            const u = (-rrIdx * 2) + 1;
                             pt = [rr * Math.sin(u * 2 * Math.PI * j / max),
                                   rr * Math.cos(u * 2 * Math.PI * j / max)];
                            break;
                        default:
                            pt = scale2(regularPolygonPoint(j/max, dPolygonArtShape), rr);
                    }
                    pts.push([pt[0], pt[1]]);
                    turtle[j==0?'jump':'goto']([pt[0], pt[1]]);
                });
            });
    
            const p = polygons.create();
            p.addPoints(...pts);
            polygons.draw(turtle, p);
        });
    }
    
    if(dSources) pts.forEach(pt => {
        const p = polygons.create();
        p.addPoints(...Array.from({length: 15}).map((p, i, a) => [.8 * Math.sin(2 * Math.PI * i / a.length), .8 * Math.cos(2 * Math.PI * i / a.length),]).map(i => add2(pt, i)));
        p.addHatching(0, .3);
        polygons.draw(turtle, p);
    });

    vd.getPolygonPoints(true).forEach(pts => {
        const p = polygons.create();
        if(dPolygonShrink > 0) {
            let shrunkPts = pts[1].map((p, i, a) =>
                add2(p, 
                    scale2(normalize2(
                        add2(
                            normalize2(sub2(pts[1][(i-1+a.length)%a.length], p)),
                            normalize2(sub2(pts[1][(i+1)%a.length], p))
                        )
                    ), dPolygonShrink)
                )
            );
            
            //the shrunken points may intersect now... that needs clearing.
            //for now, a naive check if edges from adjacent points intersect at the same point
            for(let i = 0; shrunkPts.length > 3 && i < shrunkPts.length; i++) {
                const iTarget = (i - 1 + shrunkPts.length) % shrunkPts.length;
                const next = (i + 1) % shrunkPts.length;
                const nextTarget = (i + 2) % shrunkPts.length;
                
                const intersect = segment_intersect2(shrunkPts[i], shrunkPts[iTarget], shrunkPts[next], shrunkPts[nextTarget], false);
                if(intersect !== false) {
                    shrunkPts[i] = intersect;
                    shrunkPts.splice(next, 1);
                }
            }
            
            p.addPoints(...shrunkPts);
        } else {
            p.addPoints(...pts[1]);
        }
        if(dPolygonHatching) {
            let hatchDistance = .15;
            let hatchDirection = 0;
            switch(dPolygonHatching) {
                case 1:
                    hatchDistance = dPolygonHatchMin + (Math.random() * (dPolygonHatchMaxc - dPolygonHatchMin));
                    break;
                case 2:
                case 3:
                    const maxx = ((100 - dPolygonArtBorder) * 2**.5)**2;
                    hatchDistance = dPolygonHatchMin + (
                        (dPolygonHatching == 2? lensq2(vd.dt.points[pts[0]]) / maxx: 1 - (lensq2(vd.dt.points[pts[0]]) / maxx)) 
                        
                        * (dPolygonHatchMaxc - dPolygonHatchMin)
                    );
                    break;
                case 4:
                case 5:
                    const maxxx = 200;
                    hatchDistance = dPolygonHatchMin + (
                        (dPolygonHatching == 4? (vd.dt.points[pts[0]][1] + 100) / maxxx: 1 - ((vd.dt.points[pts[0]][1] + 100) / maxxx) ) 
                        
                        * (dPolygonHatchMaxc - dPolygonHatchMin)
                    );
                    break;
                default:
            }
            switch(dPolygonHatchDir) {
                case 0:
                    hatchDirection = Math.random() * Math.PI;
                    break;
                case 1:
                    hatchDirection += Math.PI / 2;
                case 2:
                    hatchDirection += Math.atan2(...vd.dt.points[pts[0]]);
            }
            p.addHatching(hatchDirection, hatchDistance)
        }
        if(dVoronoiLines) p.addOutline();
        polygons.draw(turtle, p);
    });
    
    if(dPolygonBackground) {
        const grad = 75;
        for(let i = 1; i <= grad; i++) {
            const pp = polygons.create();
            pp.addPoints(
                [-100, 100 - (i * 200 / grad)], [100, 100 - (i * 200 / grad)],
                [100, 100], [-100, 100]
            );
            pp.addHatching(1, dPolygonHatchMin + (
                (dPolygonBackground == 1? (i/grad): 1 - (i/grad))
                
                * (dPolygonHatchMaxc - dPolygonHatchMin)
            ));
            polygons.draw(turtle, pp);
        }
    }
}

// The walk function will be called until it returns false.
function walk(i) {
    return false;
}


////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// (Polygon binning by Lionel Lemarie 2021)
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){const t=[],s=25,e=Array.from({length:s**2},t=>[]),n=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,n=1e5,h=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),n=Math.min(n,t[1]),h=Math.max(h,t[1])}),this.aabb=[s,n,e,h]}addSegments(...t){t.forEach(t=>this.dp.push(t))}addOutline(){for(let t=0,s=this.cp.length;t<s;t++)this.dp.push(this.cp[t],this.cp[(t+1)%s])}draw(t){for(let s=0,e=this.dp.length;s<e;s+=2)t.jump(this.dp[s]),t.goto(this.dp[s+1])}addHatching(t,s){const e=new n;e.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const h=Math.sin(t)*s,o=Math.cos(t)*s,a=200*Math.sin(t),i=200*Math.cos(t);for(let t=.5;t<150/s;t++)e.dp.push([h*t+i,o*t-a],[h*t-i,o*t+a]),e.dp.push([-h*t+i,-o*t-a],[-h*t-i,-o*t+a]);e.boolean(this,!1),this.dp=[...this.dp,...e.dp]}inside(t){let s=0;for(let e=0,n=this.cp.length;e<n;e++)this.segment_intersect(t,[.1,-1e3],this.cp[e],this.cp[(e+1)%n])&&s++;return 1&s}boolean(t,s=!0){const e=[];for(let n=0,h=this.dp.length;n<h;n+=2){const h=this.dp[n],o=this.dp[n+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const n=this.segment_intersect(h,o,t.cp[s],t.cp[(s+1)%e]);!1!==n&&a.push(n)}if(0===a.length)s===!t.inside(h)&&e.push(h,o);else{a.push(h,o);const n=o[0]-h[0],i=o[1]-h[1];a.sort((t,s)=>(t[0]-h[0])*n+(t[1]-h[1])*i-(s[0]-h[0])*n-(s[1]-h[1])*i);for(let n=0;n<a.length-1;n++)(a[n][0]-a[n+1][0])**2+(a[n][1]-a[n+1][1])**2>=.001&&s===!t.inside([(a[n][0]+a[n+1][0])/2,(a[n][1]+a[n+1][1])/2])&&e.push(a[n],a[n+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,n){const h=(n[1]-e[1])*(s[0]-t[0])-(n[0]-e[0])*(s[1]-t[1]);if(0===h)return!1;const o=((n[0]-e[0])*(t[1]-e[1])-(n[1]-e[1])*(t[0]-e[0]))/h,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/h;return o>=0&&o<=1&&a>=0&&a<=1&&[t[0]+o*(s[0]-t[0]),t[1]+o*(s[1]-t[1])]}};return{list:()=>t,create:()=>new n,draw:(n,h,o=!0)=>{reducedPolygonList=function(n){const h={},o=200/s;for(var a=0;a<s;a++){const c=a*o-100,r=[0,c,200,c+o];if(!(n[3]<r[1]||n[1]>r[3]))for(var i=0;i<s;i++){const c=i*o-100;r[0]=c,r[2]=c+o,n[0]>r[2]||n[2]<r[0]||e[i+a*s].forEach(s=>{const e=t[s];n[3]<e.aabb[1]||n[1]>e.aabb[3]||n[0]>e.aabb[2]||n[2]<e.aabb[0]||(h[s]=1)})}}return Array.from(Object.keys(h),s=>t[s])}(h.aabb);for(let t=0;t<reducedPolygonList.length&&h.boolean(reducedPolygonList[t]);t++);h.draw(n),o&&function(n){t.push(n);const h=t.length-1,o=200/s;e.forEach((t,e)=>{const a=e%s*o-100,i=(e/s|0)*o-100,c=[a,i,a+o,i+o];c[3]<n.aabb[1]||c[1]>n.aabb[3]||c[0]>n.aabb[2]||c[2]<n.aabb[0]||t.push(h)})}(h)}}}