// Poisson-disc Grow Patterns. Created by Reinder Nijhoff 2019
// @reindernijhoff
//
// https://turtletoy.net/turtle/b5510898dc
//
// Grow pattern based on Poisson-disc Sampling. Based on work by @FogleBird: 
// https://medium.com/@fogleman/pen-plotter-programming-the-basics-ec0407ab5929
//

const growFromCenter = true;
const randomGrowOrder = 0.1; // [0,1]
const loosePacking = 0.1; // [0,1)
const maxGrowIterations = 80000;

//
// Code
//

Canvas.setpenopacity(.75);
const turtle = new Turtle();
const growPoints = [];

if (growFromCenter) {
    growPoints.push([0,0]);
} else {
    const radius = 45; // spawn growpoints on circle
    for(let a=0; a<2*Math.PI; a+=1/radius) {
    	growPoints.push([radius*Math.cos(a), radius*Math.sin(a)]);
    }
}

const points = createPoissonDiscSamples([-100,-100], [100,100], growPoints, .75, 32);

function walk(i) {
    if (points[i][2]) {
        turtle.penup();
        turtle.goto(points[i]);
        turtle.pendown();
        turtle.goto(points[i][2]);
    }
    return i < points.length-1;
}

// Poisson-disc sampling:
// https://github.com/fogleman/poissondisc
// https://www.jasondavies.com/poisson-disc
// https://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3
function createPoissonDiscSamples(lb, rt, growPoints, radius, tries = 4) {
    const result = [];
    const active = [];
    
	const grid = Grid(lb, rt, radius);
    
    for (let i=0; i<growPoints.length; i++) {
        const p = growPoints[i];
    	grid.insert(p);
    	active.push(p);
    	result.push(p);
    }
    
    let iteration = 0;
    
	while (active.length > 0 && iteration++ < maxGrowIterations) {
		const index = (Math.random() * active.length * randomGrowOrder) | 0;
		const point = active[index];
		let ok = false;

		for (let i = 0; i < tries; i++) {
			const a = Math.random() * 2 * Math.PI;
			const d = (Math.random()*loosePacking + 1) * radius;
			const x = point[0] + Math.cos(a)*d;
			const y = point[1] + Math.sin(a)*d;
			if (x < lb[0] || y < lb[1] || x > rt[0] || y > rt[1]) {
				continue;
			}
			const p = [x, y, point];
			if (!grid.insert(p)) {
				continue;
			}
			result.push(p);
			active.push(p);
			ok = true;
			break;
		}

		if (!ok) {
		    active.splice(index, 1);
		}
	}

	return result
}

function Grid(lb, rt, r) {
    const GridClass = class {
        constructor(lb, rt, r) {
            this.radius = r;
            this.radius2 = r*r;
        	this.size = r / Math.sqrt(2);
        
        	this.i0 = Math.floor(Math.floor(lb[0] / this.size));
        	this.j0 = Math.floor(Math.floor(lb[1] / this.size));
        	const i1 = Math.floor(Math.floor(rt[0] / this.size));
        	const j1 = Math.floor(Math.floor(rt[1] / this.size));
        
        	this.gw = i1 - this.i0 + 1;
        	this.gh = j1 - this.j0 + 1;
        
        	this.cells = [];
        }
        insert(p) {
        	const ci = Math.floor(p[0]/this.size) - this.i0
        	const cj = Math.floor(p[1]/this.size) - this.j0
        
        	let q = this.cells[cj*this.gw+ci];
        	if (q && (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1]) < this.radius2) {
        		return false;
        	}
        
        	const i0 = Math.max(0, ci-2);
        	const j0 = Math.max(0, cj-2);
        	const i1 = Math.min(this.gw, ci+3);
        	const j1 = Math.min(this.gh, cj+3);
        	for (let j = j0; j < j1; j++) {
        		for (let i = i0; i < i1; i++) {
        			q = this.cells[j*this.gw+i];
        			if  (q && (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1]) < this.radius2) {
        				return false;
        			}
        		}
        	}
        
        	this.cells[cj*this.gw+ci] = p;
        	return true;
        }
    }
    return new GridClass(lb, rt, r);
}