Minimum enclosing circle scroll

by Matthew Vasallo

HTML

<canvas width="300" height="3000" id="canvas" style="background-color:yellow"></canvas>

JavaScript

function makeCircle(points) {
    // Clone list to preserve the caller's data, do Knuth shuffle
    var shuffled = points.slice(0);
    for (var i = points.length - 1; i >= 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        j = Math.max(Math.min(j, i), 0);
        var temp = shuffled[i];
        shuffled[i] = shuffled[j];
        shuffled[j] = temp;
    }

    // Progressively add points to circle or recompute circle
    var c = null;
    for (var i = 0; i < shuffled.length; i++) {
        var p = shuffled[i];
        if (c == null || !isInCircle(c, p)) c = makeCircleOnePoint(shuffled.slice(0, i + 1), p);
    }
    return c;
}


// One boundary point known
function makeCircleOnePoint(points, p) {
    var c = {
        x: p.x,
        y: p.y,
        r: 0
    };
    for (var i = 0; i < points.length; i++) {
        var q = points[i];
        if (!isInCircle(c, q)) {
            if (c.r == 0) c = makeDiameter(p, q);
            else c = makeCircleTwoPoints(points.slice(0, i + 1), p, q);
        }
    }
    return c;
}


// Two boundary points known
function makeCircleTwoPoints(points, p, q) {
    var temp = makeDiameter(p, q);
    var containsAll = true;
    for (var i = 0; i < points.length; i++)
    containsAll = containsAll && isInCircle(temp, points[i]);
    if (containsAll) return temp;

    var left = null;
    var right = null;
    for (var i = 0; i < points.length; i++) {
        var r = points[i];
        var cross = crossProduct(p.x, p.y, q.x, q.y, r.x, r.y);
        var c = makeCircumcircle(p, q, r);
        if (c == null) continue;
        else if (cross > 0 && (left == null || crossProduct(p.x, p.y, q.x, q.y, c.x, c.y) > crossProduct(p.x, p.y, q.x, q.y, left.x, left.y))) left = c;
        else if (cross < 0 && (right == null || crossProduct(p.x, p.y, q.x, q.y, c.x, c.y) < crossProduct(p.x, p.y, q.x, q.y, right.x, right.y))) right = c;
    }
    return right == null || left != null && left.r <= right.r ? left : right;
}


function...