voronoi/voronoi.js

console.log('hi voronoi');

const canvas = document.getElementById('canvas'),
    canvwidth = canvas.width,
    canvheight = canvas.height,
    ctx = canvas.getContext('2d');
const minDist = 20,
    edgeBounds = 20;

function drawSite(x, y, colour = 'black') {
    ctx.save();
    ctx.beginPath();
    ctx.arc(x, y, 2, 0, Math.PI * 2, false);
    ctx.closePath();
    ctx.fillStyle = colour;
    ctx.fill();
    ctx.restore();
}
function drawLine(x1, y1, x2, y2) {
    ctx.save();
    ctx.beginPath();
    ctx.strokeStyle = 'black';
    ctx.lineWidth = 1;
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.stroke();
    ctx.restore();
}
function drawLineO(p1, p2) {
    drawLine(p1.x, p1.y, p2.x, p2.y);
}
function distance(p1, p2) {
    return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
}
function generateSites(n = 10) {
    const sites = [],
        safety = n * 2,
        randMultWidth = canvwidth - (edgeBounds * 2),
        randMultHeight = canvheight - (edgeBounds * 2),
        origin = {x:0, y:0};

    let count = 0;
    while( sites.length < n && count < safety ) {
        count += 1;
        const x = Math.floor(Math.random() * randMultWidth) + edgeBounds,
            y = Math.floor(Math.random() * randMultHeight) + edgeBounds,
            min = sites.reduce(function checkDist(minSoFar, existing) {
                const d = distance(existing, {x, y});
                if( d < minSoFar ) {
                    return d;
                }
                else {
                    return minSoFar;
                }
            }, canvwidth * canvheight);
        if( min > minDist ) {
            sites.push( {x, y} );
        }
    }

    sites.sort(function (a, b) {
        return a.y - b.y;
    });

    return sites;
}

function randIndivC(a = 0, b = 255) {
    return Math.floor(Math.random() * (b-a) + a);
}
function cts(c) {
    const r = c.r < 16 ? '0' + c.r.toString(16) : c.r.toString(16),
        g = c.g < 16 ? '0' + c.g.toString(16) : c.g.toString(16),
        b = c.b < 16 ? '0' + c.b.toString(16) : c.b.toString(16);
    return '#' + r + g + b;
}
function primaryOrSecondary() {
    const t = Math.random(),
        w = Math.floor(Math.random() * 3);
    if( t < 0.45 ) {
        const r = w === 0 ? 255 : 0,
            g = w === 1 ? 255 : 0,
            b = w === 2 ? 255 : 0;
        return {r, g, b};
    }
    else if( t < 0.9 ) {
        const r = w !== 0 ? 255 : 0,
            g = w !== 1 ? 255 : 0,
            b = w !== 2 ? 255 : 0;
        return {r, g, b};
    }
    else {
        //return {r: 255, g:255, b:255};
        const r = randIndivC(100, 255),
            g = randIndivC(100, 255),
            b = randIndivC(100, 255);
        return {r, g, b};
    }
}
function randomColor() {
    const t = Math.random(),
        w = Math.floor(Math.random() * 3);
    if( t < 0.45 ) {
        const r = w === 0 ? randIndivC(200, 255) : randIndivC(10, 100),
            g = w === 1 ? randIndivC(200, 255) : randIndivC(10, 100),
            b = w === 2 ? randIndivC(200, 255) : randIndivC(10, 100);
        return {r, g, b};
    }
    else if( t < 0.9 ) {
        const r = w !== 0 ? randIndivC(200, 255) : randIndivC(10, 100),
            g = w !== 1 ? randIndivC(200, 255) : randIndivC(10, 100),
            b = w !== 2 ? randIndivC(200, 255) : randIndivC(10, 100);
        return {r, g, b};
    }
    else {
        const r = randIndivC(100, 200),
            g = randIndivC(100, 200),
            b = randIndivC(100, 200);
        return {r, g, b};
    }
}
function mixedColor(base) {
    let randr = Math.floor(Math.random() * 200 + 55),
        randg = Math.floor(Math.random() * 200 + 55),
        randb = Math.floor(Math.random() * 200 + 55);
    if( base ) {
        randr = Math.floor((base.r + randr) / 2);
        randg = Math.floor((base.g + randg) / 2);
        randb = Math.floor((base.b + randb) / 2);
    }
    return cts({r:randr, g:randg, b:randb});
}

const sites = generateSites(50).map(function assignRandomColour(site) {
    //site.color = cts(randomColor());
    //site.color = cts(primaryOrSecondary());
    site.color = mixedColor(primaryOrSecondary());
    site.sectors = [];
    return site;
});

//sites.forEach(function renderSites(site) {
//    drawSite(site.x, site.y);
//});


function bruteForceRow(row, sites) {
    sites = sites.map(function addNewRow(site) {
        site.sectors[row] = [];
        return site;
    })
    for( let i = 0; i < canvwidth; i += 1 ) {
        const point = {x:i, y:row},
            cind = sites.slice(1).reduce(function check(closest, site, ind) {
                const d = distance(site, point);
                if( d < closest.d ) {
                    return {c:(ind + 1), d};
                }
                return closest;
            }, {c:0, d:distance(sites[0], point)});
        sites[cind.c].sectors[row].push(point);
    }
    return sites;
}
function spot(x, y, colour) {
    ctx.save();
    ctx.fillStyle = colour;
    ctx.fillRect(x, y, 1, 1);
    ctx.restore();
}

function goRow(i, sites) {
    const newSites = bruteForceRow(i, sites);
    newSites.filter(x => x.sectors[i].length)
        .forEach(function parse(leader) {
            leader.sectors[i].forEach(function draw(place) {
                spot(place.x, place.y, leader.color);
            })
        });
    if( i < canvheight ) {
        setTimeout(goRow, 10, i + 1, newSites);
    }
    else {
        setTimeout(function action() {
            // temp redraw sites
            sites.forEach(function renderSites(site) {
                drawSite(site.x, site.y);
            });
        }, 100);
    }
}
//goRow(0, sites);

function parabola(focus, directrixY) {
    // http://jtauber.com/blog/2008/11/08/from_focus_and_directrix_to_bezier_curve_parameters/
    const a = Math.sqrt(Math.pow(directrixY, 2) - Math.pow(focus.y, 2)),
        start = {x: (focus.x - a), y: 0},
        control = {x: focus.x, y: (focus.y + directrixY)},
        end = {x: (focus.x + a), y: 0};

    ctx.save();
    ctx.lineWidth = 1;
    ctx.strokeStyle = '#aaa';
    //ctx.fillStyle = 'rgba(255,0,0,0.5)';
    //ctx.fillStyle = 'white';
    ctx.beginPath();
    ctx.moveTo(start.x, start.y);
    ctx.quadraticCurveTo(control.x, control.y, end.x, end.y);
    ctx.stroke();
    //ctx.fill();
    ctx.closePath()
    ctx.restore();
}

function demo(dirY) {
    ctx.clearRect(0,0,canvwidth,canvheight);
    //ctx.save();
    //ctx.fillStyle = 'rgba(255,0,0,0.5)';
    //ctx.fillRect(0,0,canvwidth,canvheight);
    //ctx.restore();
    sites.forEach(function parabolas(site) {
        if( site.y < dirY ) {
            parabola(site, dirY);
        }
    })
    sites.forEach(function renderSites(site) {
        drawSite(site.x, site.y);
    });
    drawLine(0,dirY,canvwidth,dirY);
    if( dirY < canvheight + 1000 ) {
        setTimeout(demo, 10, dirY + 1)
    }
    else {
        console.log('done!');
    }
}
//demo(0);

//TODO
// http://hotmath.com/hotmath_help/topics/finding-the-equation-of-a-parabola-given-focus-and-directrix.html
// http://www.ams.org/samplings/feature-column/fcarc-voronoi
// interactive: https://rosettacode.org/wiki/Voronoi_diagram#JavaScript
// cell growth: http://www.raymondhill.net/voronoi/rhill-voronoi-demo5.html


// modified from: http://stackoverflow.com/a/32863775
// TODO: handle the situation where the two chosen points have the same Y
function calculateCircleCenter(a, b, c) {
    const yDelta_a = b.y - a.y,
        xDelta_a = b.x - a.x,
        yDelta_b = c.y - b.y,
        xDelta_b = c.x - b.x;

    const center = {};

    const aSlope = yDelta_a / xDelta_a,
        bSlope = yDelta_b / xDelta_b;

    center.x = (aSlope*bSlope*(a.y - c.y) + bSlope*(a.x + b.x) - aSlope*(b.x+c.x) )/(2* (bSlope-aSlope) );
    center.y = -1*(center.x - (a.x+b.x)/2)/aSlope +  (a.y+b.y)/2;
    return center;
}

function circleEvent(a, b, c) {
    const center = calculateCircleCenter(a, b, c),
        radius = distance(center, a);
    return {
        center,
        radius,
        event: {
            x: center.x,
            y: center.y + radius,
        },
    };
}

//const circle = circleEvent(...circlePoints);
//console.log('circle center', circle.center);
//console.log('circle radius', circle.radius);
//console.log('circle event', circle.event);
//
//ctx.save();
//ctx.beginPath();
//ctx.arc(circle.center.x, circle.center.y, circle.radius, 0, Math.PI * 2, false);
//ctx.closePath();
//ctx.fillStyle = 'rgba(255, 0, 0, 0.5)';
//ctx.fill();
//ctx.restore();
//
//drawSite(circle.center.x, circle.center.y, 'black');
//drawSite(circle.event.x, circle.event.y, 'blue');

const ss = generateSites(2),
    directrix = Math.max(ss[0].y, ss[1].y) + Math.floor(Math.random() * 30) + 1;

ss.forEach(function renderSites(site) {
    drawSite(site.x, site.y);
});
drawLine(0, directrix, canvwidth, directrix);
parabola(ss[0], directrix);
parabola(ss[1], directrix);

function incorrectParabolaIntersections(site1, site2, directrix) {
    const a = directrix,
        b = directrix,
        X = site1.x - site2.x,
        Y = site1.y - site2.y,
        denom = 8 * a * (Math.pow(b, 2) - a);
    if( denom === 0 ) {
        console.log('zero!');
        return [];
    }
    const a2 = Math.pow(a, 2),
        a4 = Math.pow(a, 4),
        b2 = Math.pow(b, 2),
        Y2 = Math.pow(Y, 2),
        first = -4 * a2 * Y,
        second = Math.sqrt((16 * a4 * Y2) - (16 * a * (b2 - a) * ((4 * b2 * X) - (a * Y2))));

    const option1 = (first - second) / denom,
        option2 = (first + second) / denom;

    console.log('a (d)', a, b);
    console.log('X', X);
    console.log('Y', Y);
    console.log('1', (a * Y2));
    console.log('2', (16 * a4 * Y2));
    console.log('3', (16 * a * (b2 - a) * ((4 * b2 * X) - (a * Y2))));
    console.log('4', ((16 * a4 * Y2) - (16 * a * (b2 - a) * ((4 * b2 * X) - (a * Y2)))));
    console.log('first', first);
    console.log('second', second);
    console.log('denom', denom);
    console.log('option1', option1);
    console.log('option2', option2);
}
function parabolaIntersections(site1, site2, directrix) {
    const a = site1.x,
        b = site1.y,
        c = site2.x,
        e = site2.y,
        d = directrix;
    const denom = b - e;
    if( denom === 0 ) {
        console.log('zero.');
        return [];
    }
    const a2 = Math.pow(a, 2),
        b2 = Math.pow(b, 2),
        c2 = Math.pow(c, 2),
        e2 = Math.pow(e, 2),
        d2 = Math.pow(d, 2),
        first = (-b*d+b*e+d2-d*e),
        second = a2 - 2*a*c + b2 - 2*b*e + c2 + e2,
        fs = Math.sqrt(first * second),
        third = a*d - a*e + b*c - c*d;
    const option1 = (-fs + third) / denom,
        option2 = (fs + third) / denom;
    console.log('option1', option1);
    console.log('option2', option2);
    if( option1 === option2 ) {
        return [option1];
    }
    return [option1, option2];
}



const inter = parabolaIntersections(...ss, directrix);
inter.forEach(function (x) {
    drawLine(x, 0, x, canvheight);
});