// Polygon Utility. Created by Reinder Nijhoff 2022 - @reindernijhoff
// The MIT License
//
// https://turtletoy.net/turtle/108305d431
//

let seed = 1; // min=1, max=100, step=1
const drawMode = 0; // min=0, max=1, step=1 (Circles, Polygons)

Canvas.setpenopacity(drawMode == 1 ? 1 : .3);

const turtle = new Turtle();
const ps = [];

// create random polygons
for (let i=0; i<9; i++) {
    const w = 50 + 50 * random(), h = 50 + 50 * random(), x = 200 * random() - 100, y = 200 * random() - 100;
    // create random polygon p
    let p = [[x-w, y-h], [x-w, y+h], [x+w, y+h], [x+w, y-h]];
    // split edges. After the split, all edges will have a lenth of ~ 2
    p = pSplitEdges(p, 2); 
    // transform the polygon by adding sin(y) to the x-coordinate of all vertices
    p = pTransform(p, c => [c[0] + Math.sin(c[1]*.1)*2, c[1]]);
    // smooth polygon
    p = pSmooth(p, 50*(random()**2) | 0 + 1);
    
    if (drawMode == 1) {
        pDraw(p, turtle);
    }   
    
    ps.push(p);
}

function walk(i) {
    if (drawMode == 1) {
        return false;
    }
    
    // create a random point
    const [x,y] = [Math.random()*200-100, Math.random()*200-100];

    let dist = 1000;
    let inside = 0;
    
    ps.forEach(p => { 
        // find minimal distance from point to nearest polygon
        dist = Math.min(dist, pDistance(p, [x,y]));
        
        // check if point is inside polygon
        if (pPointInPolygon(p, [x,y])) {
            inside++; 
        }
    });
    
    // draw a circle with a radius equal to the nearest distance to a polygon
    if (Math.random() > 0.5 * Math.sqrt(dist / 25) + (inside % 2 ? .5 : 0)) {
        turtle.jump(x, y-dist);
        turtle.circle(dist);
    }
    
    return i < 20000;
}

function random() {
    let r = 1103515245 * (((seed+=12345) >> 1) ^ (seed));
    r = 1103515245 * (r ^ (r >> 3));
    r = r ^ (r >> 16);
    const mod = 1 << 20;
    return (r % mod) / mod;
}

////////////////////////////////////////////////////////////////
// Polygon Utility code
// https://turtletoy.net/turtle/108305d431
//
// A collection of functions that can be used to work with polygons.
// A polygon is defined by an array of vertices [v0, v1, v2, v3, ...].
// 
////////////////////////////////////////////////////////////////

// draw a polygon p using turtle t
function pDraw(p, t) {
    t.jump(p[p.length-1]);
    p.forEach(c => t.goto(c));
}

// smooth a polygon by averaging all vertices with its neighbors. Repeat r times.
function pSmooth(p, r=1) {
    let smooth = [];
    
    for(;r;r--) {
        smooth = [];
        for (let i=0; i<p.length; i++) {
            const pm = p[(i-1+p.length) % p.length];
            const p0 = p[(i+0) % p.length];
            const pp = p[(i+1) % p.length];
         
            smooth.push(lrp2(lrp2(pm, pp, .5), p0, 1/3));  
        }
        p = [...smooth];
    }
    return smooth;
}

// split all edges of polygon in segments with length ~ d
function pSplitEdges(p, d = 2) {
    const sub = [];
    
    for (let i=0; i<p.length; i++) {
        const p0 = p[(i+0) % p.length];
        const p1 = p[(i+1) % p.length];
        const l = Math.ceil(dist2(p0, p1)/d);
        
        for (let j=0; j<l; j++) {
            sub.push(lrp2(p0, p1, j/l));
        }
    }
    
    return sub;
}

// expand polygon p with distance d
function pExpand(p, d = 1) {
    const lines = [];
    const scaled = [];
    
    for (let i=0; i<p.length; i++) {
        const i0 = (i+0) % p.length;
        const i1 = (i+1) % p.length;

        const p0 = p[i0];
        const p1 = p[i1];
        
        let   n = nrm2(sub2(p1, p0));
        n = [-n[1], n[0]];
        
        lines.push([...n, -dot2(n, sub2(p0, scl2(n, -d)))]);
    }
    
    // find intersection points
    
    for (let i=0; i<lines.length; i++) {
        const i0 = (i+0) % lines.length;
        const i1 = (i+1) % lines.length;
        
        const pp = cross3(lines[i0], lines[i1]);
        scaled[i] = Math.abs(pp[2]) < 0.0001 ? add2(p[i], scl2(lines[i], d)) : scl2(pp, 1/pp[2]);
    }
    
    return scaled;
}

// calculate bouding box (aabb) of p
function pAABB(p) {
    let min = [...p[0]], max = [...p[0]];
    p.forEach(c => {
       min = [ Math.min(min[0],c[0]), Math.min(min[1],c[1]) ];
       max = [ Math.max(max[0],c[0]), Math.max(max[1],c[1]) ];
    });
    return [min, max];
}

// point in aabb ? 
function pointInAABB(p, aabb) {
    const [min, max] = aabb;
    return min[0] <= p[0] && max[0] >= p[0] && min[1] <= p[1] && max[1] >= p[1];
}

// check if point is inside polygon p
function pPointInPolygon(p, point, aabb = undefined) {
    if (aabb && !pointInAABB(point, aabb || pAABB(p))) return false;
    
	let int = 0; // find number of i ntersection points from p to far away
	for (let i = 0, l = p.length; i < l; i++) {
		if (segmentIntersect(point, [0.1, -1000], p[i], p[(i + 1) % l])) {
			int++;
		}
	}
	return int & 1; // if even your outside
}

// check if sphere ([x,y,radius]) is inside polygon p
function pSphereInPolygon(p, sphere, aabb = undefined) {
    if (!pPointInPolygon(p, sphere, aabb || pAABB(p))) return false;
    return pDistance(p, sphere) > sphere[2];
}

// find distance from point to polygon p
function pDistance(p, point) {
    let dist = 100000;
    for (let i=0; i<p.length; i++) {
        const a = p[i], b = p[(i+1) % p.length];
        const ba = sub2(b, a);
        const pa = sub2(point, a);
        const h = Math.max(0, Math.min(1, dot2(pa,ba)/dot2(ba,ba)));
        dist = Math.min(dist, dist2(pa, scl2(ba, h)));
    }
    return dist;
}

// transform vertices of polygon p by function t
function pTransform(p, t) {
    const ret = [];
    for (let i=0; i<p.length; i++) {
        ret.push(t(p[i]));
    }
    return ret;
}

//port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs
function segmentIntersect(l1p1, l1p2, l2p1, l2p2) {
	const d   = (l2p2[1] - l2p1[1]) * (l1p2[0] - l1p1[0]) - (l2p2[0] - l2p1[0]) * (l1p2[1] - l1p1[1]);
	if (d === 0) return false;
	const n_a = (l2p2[0] - l2p1[0]) * (l1p1[1] - l2p1[1]) - (l2p2[1] - l2p1[1]) * (l1p1[0] - l2p1[0]);
	const n_b = (l1p2[0] - l1p1[0]) * (l1p1[1] - l2p1[1]) - (l1p2[1] - l1p1[1]) * (l1p1[0] - l2p1[0]);
	const ua = n_a / d;
	const ub = n_b / d;
	if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
		return [l1p1[0] + ua * (l1p2[0] - l1p1[0]), l1p1[1] + ua * (l1p2[1] - l1p1[1])];
	}
	return false;
}

//
// math functions
//
function scl2(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 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 len2(a)     { return Math.sqrt(a[0]**2 + a[1]**2); }
function dist2(a, b) { return len2(sub2(a,b)); }
function nrm2(a)     { return scl2(a, 1/len2(a)); }
function lrp2(b,a,f) { return f = Math.max(0, Math.min(1, f)), [a[0]*f+b[0]*(1-f), a[1]*f+b[1]*(1-f)]; }

function cross3(a, b) { return [a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]; }