// Poisson-Disc Grow Patterns. Created by Reinder Nijhoff 2019 - @reindernijhoff
// The MIT License
//
// 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 = 35000;

//
// Code
//

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

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

const points = new PoissonDisc(startPoints, .75).addPoints(maxGrowIterations, 32, loosePacking, randomGrowOrder);

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

////////////////////////////////////////////////////////////////
// Poisson-Disc utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/b5510898dc
////////////////////////////////////////////////////////////////
function PoissonDisc(startPoints, radius) {
    class PoissonDiscGrid {
        constructor(sp, radius) {
            this.cellSize = 1/Math.sqrt(2)/radius;
            this.radius2 = radius*radius;
            this.cells = [];
            sp.forEach( p => this.insert(p) );
        }
        insert(p) {
            const x = p[0]*this.cellSize|0, y=p[1]*this.cellSize|0;
            for (let xi = x-1; xi<=x+1; xi++) {
                for (let yi = y-1; yi<=y+1; yi++) {
                    const ps = this.cell(xi,yi);
                    for (let i=0; i<ps.length; i++) {
                        if ((ps[i][0]-p[0])**2 + (ps[i][1]-p[1])**2 < this.radius2) {
                            return false;
                        }
                    }
                }       
            }
            this.cell(x, y).push(p);
            return true;
        }
        cell(x,y) {
            const c = this.cells;
            return (c[x]?c[x]:c[x]=[])[y]?c[x][y]:c[x][y]=[];
        }
    }
    class PoissonDisc {
        constructor(sp, radius) {
            this.result = [...sp];
            this.active = [...sp];
            this.grid = new PoissonDiscGrid(sp, radius);
        }
        addPoints(count, maxTries=16, loosePacking=0, randomGrowOrder=0) {
        	mainLoop: while (this.active.length > 0 && count > 0) {
        		const index = (Math.random() * this.active.length * randomGrowOrder) | 0;
        		const point = this.active[index];
        		for (let i=0; i < maxTries; i++) {
        			const a = Math.random() * 2 * Math.PI;
        			const d = (Math.random()*loosePacking + 1) * radius;
        			const p = [point[0] + Math.cos(a)*d, point[1] + Math.sin(a)*d, point];
        			if (this.grid.insert(p)) {
            			this.result.push(p);
            			this.active.push(p);
            			count--;
            			continue mainLoop;
        			}
        		}
    		    this.active.splice(index, 1);
        	}
        	return this.result;
        }
    }
    return new PoissonDisc(startPoints, radius);
}