// LL 2021

const split_frequency = 0.4; // min=0.01 max=1 step=0.01
const iterations = 3000; // min=0 max=20000 step=100

const turtle = new Turtle();

const canvas_size = 90;
const push_distance = 7; // min=0.1 max=10 step=0.1

Canvas.setpenopacity(1);

const init_size = 10 + Math.random();
const max_ndistance = 0.01;
const bin_size = Math.max(1, push_distance - 1);

var enable_progress_bar = true;

const camera_angle = 0.14; /// min=0 max=1 step=0.01
const camera_height = 150; /// min=0 max=500 step=50
const camera_distance = 400;
const exaggeration = 1; // min=0 max=5 step=0.1
const layers = 50 / exaggeration;

var style = 1; /// min=0 max=1 step=1 (Polygons (fast),Polygons (slow))
let polygons;

let points;
let bins;

let shapes;

function walk(i, t) {
    if (i == 0) {
        if (t < 1) enable_progress_bar = false;
        polygons = new Polygons();
        cameraPos = [camera_distance * Math.cos(Math.PI * 2 * (camera_angle + t)), camera_height, camera_distance * Math.sin(Math.PI * 2 * (camera_angle + t))];
        viewProjectionMatrix = setupCamera(cameraPos, cameraLookAt);
        shapes = [];
        init_shape();
        bin_shape();
    }
    else
    {
        if ((i % Math.round(1 / split_frequency)) == 0) {
            split_shape();
        }
    }
    
    const iterations_t = iterations; //Math.floor(iterations * t);
    draw_progress_bar(Math.min(i, iterations_t), iterations_t);
    
    const period = Math.floor(iterations / layers);
    
    if (i < iterations_t) {
        move_shape();
        bin_shape();
        if (((i+1) % period) == 0) save_shape();
        return true;
    }

    if (shapes.length > 0) {
        points = shapes.pop();
        // points = shapes.shift();
        draw_shape(iterations_t / period - shapes.length);
        return true;
    }

    return false;
}

function save_shape(i) {
    const dpoints = [];
    points.forEach(p => dpoints.push([p[0], p[1]]));
    shapes.push(dpoints);
}

function draw_progress_bar(i, max) {
    if (i > 0 && enable_progress_bar) {
        const i0 = i -1;
        turtle.down();
        const x0 = (i0 / max) * 190 - 95;
        const x1 = (i  / max) * 190 - 95;
        const y = 95;
        turtle.jump(x0, y);
        turtle.goto(x1, y);
    }
}

function get_bin_index(x, y) {
    //return 1;
    return Math.floor(x / bin_size) + Math.floor(y / bin_size) * Math.ceil(canvas_size / bin_size);
}

function bin_shape() {
    bins = {};
    
    points.forEach((p, id) => {
       const bin_index = get_bin_index(p[0], p[1]);
       if (!(bin_index in bins)) bins[bin_index] = [];
       bins[bin_index].push(id);
    });
}

function split_shape() {
    if (points.length < 2) return;
    var best_pair = 0;
    var best_distance = Math.hypot(points[0][0] - points[1][0], points[0][1] - points[1][1]);
    for (var pair = 1; pair < points.length; pair++) {
        let point0 = points[pair];
        let point1 = points[(pair+1) % points.length];
        const distance = Math.hypot(point0[0] - point1[0], point0[1] - point1[1]);
        if (distance > best_distance) {
            best_distance = distance;
            best_pair = pair;
        }
    }

    const new_points = [[...points[0]]];
    for (var pair = 0; pair < points.length; pair++) {
        let point0 = points[pair];
        let point1 = points[(pair+1) % points.length];
        if (pair == best_pair) {
            const x = (point0[0] + point1[0]) / 2;
            const y = (point0[1] + point1[1]) / 2;
            const new_point = [x, y];
            new_points.push(new_point);
        }
        if (pair < points.length -1) new_points.push(point1);
    }
    points = new_points;
}

function move_shape() {
    points.forEach((p, id) => {
        movep = [0, 0];
        bin_index = get_bin_index(p[0], p[1]);
        const di = Math.max(1, Math.ceil(push_distance / 2 / bin_size));
        for (var dx=-di; dx<=di; dx++) {
            for (var dy=-di; dy<=di; dy++) {
                const bi = bin_index + dx + dy * Math.ceil(canvas_size / bin_size);
                if (bi in bins) {
                    bins[bi].forEach(bid => {
                        const dir = [p[0] - points[bid][0], p[1] - points[bid][1]];
                        const distance = Math.hypot(dir[0], dir[1]);
                        if (distance < push_distance) {
                            const push = 0.05 / distance;
                            const EPS = 0.1;
                            if (distance > EPS) {
                                movep[0] += dir[0] * push;
                                movep[1] += dir[1] * push;
                            }
                        }
                    });
                }
            }
        }
        
        p[0] += movep[0];
        p[1] += movep[1];
        
        for (var did=-1; did<=1; did+=2) {
            const id0 = (id + points.length + did) % points.length;
            const dir = [p[0] - points[id0][0], p[1] - points[id0][1]];
            const distance = Math.hypot(dir[0], dir[1]);
            if (distance > max_ndistance) {
                const np = [ points[id0][0] + dir[0] / distance * max_ndistance, points[id0][1] + dir[1] / distance * max_ndistance];
                p[0] = p[0] + (np[0] - p[0]) / 10;
                p[1] = p[1] + (np[1] - p[1]) / 10;
            }
        }
    });
    
    check_bounds();
}

function check_bounds() {
    points.forEach(p => {
        // if (p[0] >  canvas_size) p[0] =  canvas_size;
        // if (p[0] < -canvas_size) p[0] = -canvas_size;
        // if (p[1] >  canvas_size) p[1] =  canvas_size;
        // if (p[1] < -canvas_size) p[1] = -canvas_size;
        const distance = Math.hypot(p[0], p[1]);
        if (distance > canvas_size) {
            p[0] *= canvas_size / distance;
            p[1] *= canvas_size / distance;
        }
    });
}

function init_shape() {
    points = [];
    
    // Square
    points = [ [-init_size, -init_size], [init_size, -init_size], [init_size, init_size], [-init_size, init_size]];
}

function draw_shape(h) {
    const dpoints = [];
    points.forEach(p => {
        const xy = project(p[0], p[1], h);
        dpoints.push(xy);
    });
    drawPoints(dpoints);
}

function project(x, y, z) {
    const p = transform4([x, z * -exaggeration, y, 1], viewProjectionMatrix);
    const s = 50;
    return [p[0]/p[3]*s, -p[1]/p[3]*s];
}

function drawPoints(dpoints) {
    if (style == 0) {
        turtle.jump(dpoints[dpoints.length-1]);
        dpoints.forEach(p=>turtle.goto(p));
    } else {
        const p1 = polygons.create();
        p1.addPoints(...dpoints);
        p1.addOutline();
        //p1.addHatching(-Math.PI / 4, 1);
        polygons.draw(turtle, p1, true);
    }
}

////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){let t=[];const s=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,h=1e5,i=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),h=Math.min(h,t[1]),i=Math.max(i,t[1])}),this.aabb=[(s+e)/2,(h+i)/2,(e-s)/2,(i-h)/2]}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,e){const h=new s;h.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const i=Math.sin(t)*e,n=Math.cos(t)*e,a=200*Math.sin(t),p=200*Math.cos(t);for(let t=.5;t<150/e;t++)h.dp.push([i*t+p,n*t-a],[i*t-p,n*t+a]),h.dp.push([-i*t+p,-n*t-a],[-i*t-p,-n*t+a]);h.boolean(this,!1),this.dp=[...this.dp,...h.dp]}inside(t){let s=0;for(let e=0,h=this.cp.length;e<h;e++)this.segment_intersect(t,[.13,-1e3],this.cp[e],this.cp[(e+1)%h])&&s++;return 1&s}boolean(t,s=!0){if(s&&Math.abs(this.aabb[0]-t.aabb[0])-(t.aabb[2]+this.aabb[2])>=0&&Math.abs(this.aabb[1]-t.aabb[1])-(t.aabb[3]+this.aabb[3])>=0)return this.dp.length>0;const e=[];for(let h=0,i=this.dp.length;h<i;h+=2){const i=this.dp[h],n=this.dp[h+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const h=this.segment_intersect(i,n,t.cp[s],t.cp[(s+1)%e]);!1!==h&&a.push(h)}if(0===a.length)s===!t.inside(i)&&e.push(i,n);else{a.push(i,n);const h=n[0]-i[0],p=n[1]-i[1];a.sort((t,s)=>(t[0]-i[0])*h+(t[1]-i[1])*p-(s[0]-i[0])*h-(s[1]-i[1])*p);for(let h=0;h<a.length-1;h++)(a[h][0]-a[h+1][0])**2+(a[h][1]-a[h+1][1])**2>=.001&&s===!t.inside([(a[h][0]+a[h+1][0])/2,(a[h][1]+a[h+1][1])/2])&&e.push(a[h],a[h+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,h){const i=(h[1]-e[1])*(s[0]-t[0])-(h[0]-e[0])*(s[1]-t[1]);if(0===i)return!1;const n=((h[0]-e[0])*(t[1]-e[1])-(h[1]-e[1])*(t[0]-e[0]))/i,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/i;return n>=0&&n<=1&&a>=0&&a<=1&&[t[0]+n*(s[0]-t[0]),t[1]+n*(s[1]-t[1])]}};return{list:()=>t,create:()=>new s,draw:(s,e,h=!0)=>{for(let s=0;s<t.length&&e.boolean(t[s]);s++);e.draw(s),h&&t.push(e)}}}

////////////////////////////////////////////////////////////////
// Projection from reinder's https://turtletoy.net/turtle/b3acf08303
let cameraPos, viewProjectionMatrix;
const cameraLookAt = [0,0,0];
function setupCamera(t,e){const m=lookAt4m(t,e,[0,1,0]),n=perspective4m(.25,1);return multiply4m(n,m)}
function lookAt4m(o,n,r){const s=new Float32Array(16);n=normalize3(sub3(o,n)),r=normalize3(cross3(r,n));const t=normalize3(cross3(n,r));return s[0]=r[0],s[1]=t[0],s[2]=n[0],s[3]=0,s[4]=r[1],s[5]=t[1],s[6]=n[1],s[7]=0,s[8]=r[2],s[9]=t[2],s[10]=n[2],s[11]=0,s[12]=-(r[0]*o[0]+r[1]*o[1]+r[2]*o[2]),s[13]=-(t[0]*o[0]+t[1]*o[1]+t[2]*o[2]),s[14]=-(n[0]*o[0]+n[1]*o[1]+n[2]*o[2]),s[15]=1,s}
function perspective4m(t,n){const e=new Float32Array(16).fill(0,0);return e[5]=1/Math.tan(t/2),e[0]=e[5]/n,e[10]=e[11]=-1,e}
function multiply4m(t,r){const l=new Float32Array(16);for(let n=0;16>n;n+=4)for(let o=0;4>o;o++)l[n+o]=r[n+0]*t[0+o]+r[n+1]*t[4+o]+r[n+2]*t[8+o]+r[n+3]*t[12+o];return l}
function transform4(r,n){const t=new Float32Array(4);for(let o=0;4>o;o++)t[o]=n[o]*r[0]+n[o+4]*r[1]+n[o+8]*r[2]+n[o+12];return t}
function normalize3(a) { return scale3(a,1/len3(a)); }
function scale3(a,b) { return [a[0]*b,a[1]*b,a[2]*b]; }
function len3(a) { return Math.sqrt(dot3(a,a)); }
function sub3(a,b) { return [a[0]-b[0],a[1]-b[1],a[2]-b[2]]; }
function dot3(a,b) { return a[0]*b[0]+a[1]*b[1]+a[2]*b[2]; }
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]]; }