sweep.js

if (typeof module !== 'undefined') module.exports = sweep;

var VERTEX_START = 0,
    VERTEX_SPLIT = 1,
    VERTEX_END = 2,
    VERTEX_MERGE = 3,
    VERTEX_REGULAR = 4;

function sweep(points) {

    var n = points.length,
        queue = [],
        i, first, last, v, prev, next;

    // put vertices in a circular doubly linked list

    first = last = makeNode(points[0], 0);

    queue.push(first);

    for (i = 1; i < n; i++) {
        v = makeNode(points[i], i);
        v.prev = last;
        last.next = v;
        last.dy = v.y - last.y;
        last = v;
        queue.push(v);
    }

    first.prev = last;
    last.next = first;
    last.dy = first.y - last.y;

    // init edges list

    var edges = [];

    for (i = 0; i < n; i++) {
        v = queue[i];
        edges.push(new Edge(v, v.next, i));
    }

    // we'll iterate through vertices from top to bottom (sweep line)
    queue.sort(compareVertices);

    // determine vertex type
    for (i = 0; i < n; i++) {
        v = queue[i];
        prev = v.prev;
        next = v.next;

        v.type =
            below(prev, v) && below(next, v) ? (isConvex(next, prev, v) ? VERTEX_START : VERTEX_SPLIT) :
            below(v, prev) && below(v, next) ? (isConvex(next, prev, v) ? VERTEX_END : VERTEX_MERGE) : VERTEX_REGULAR;
    }

    var helpers = new Array(n),
        currentEdges = [],
        k, j, m;

    for (k = 0; k < n; k++) {
        v = queue[k];
        i = v.index;

        if (v.type === VERTEX_START) {
            insertEdge(currentEdges, edges[i]);
            helpers[i] = v;

        } else if (v.type === VERTEX_END) {
            m = v.prev.index;
            if (helpers[m].type === VERTEX_MERGE) addDiagonal(v, helpers[m]);
            removeEdge(currentEdges, edges[m]);

        } else if (v.type === VERTEX_SPLIT) {

            j = lowerEdge(currentEdges, v).index;
            addDiagonal(v, helpers[j]);
            helpers[j] = v;

            insertEdge(currentEdges, edges[i]);
            helpers[i] = v;

        } else if (v.type === VERTEX_MERGE) {

            m = v.prev.index;
            if (helpers[m].type === VERTEX_MERGE) addDiagonal(v, helpers[m]);
            removeEdge(currentEdges, edges[m]);

            j = lowerEdge(currentEdges, v).index;
            if (helpers[j].type === VERTEX_MERGE) addDiagonal(v, helpers[j]);
            helpers[j] = v;

        } else {

            if (below(v, v.prev)) {
                m = v.prev.index;
                if (helpers[m].type === VERTEX_MERGE) addDiagonal(v, helpers[m]);
                removeEdge(currentEdges, edges[m]);

                insertEdge(currentEdges, edges[i]);
                helpers[i] = v;

            } else {
                j = lowerEdge(currentEdges, v).index;
                if (helpers[j].type === VERTEX_MERGE) addDiagonal(v, helpers[j]);
                helpers[j] = v;
            }
        }
    }
}

function addDiagonal(v1, v2) {
    // debugger;
    // console.log('add!');
    drawPoly([[v1.x, v1.y], [v2.x, v2.y]], 'red');
}

function compareVertices(p1, p2) {
    return (p1.y - p2.y) || (p1.x - p2.x);
}

function below(p1, p2) {
    return ((p1.y - p2.y) || (p1.x - p2.x)) > 0;
}

function isConvex(p1, p2, p3) {
    return (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y) > 0;
}

function makeNode(p, index) {
    var node = {
        x: p[0],
        y: p[1],
        index: index,
        prev: null,
        next: null,
        type: null
    };
    return node;
}


function insertEdge(edges, edge) {

    var i = 0,
        j = edges.length - 1;

    while (i <= j) {
        var mid = Math.floor((i + j) / 2);

        if (compareEdges(edge, edges[mid])) j = mid - 1;
        else i = mid + 1;
    }

    edges.splice(i, 0, edge);
}

function lowerEdge(edges, p) {

    var i = 0,
        j = edges.length - 1,
        edge = new Edge(p, p);

    while (i <= j) {
        var mid = Math.floor((i + j) / 2);

        if (compareEdges(edge, edges[mid])) j = mid - 1;
        else i = mid + 1;
    }

    return edges[i - 1];
}

function removeEdge(edges, edge) {

    var i = 0,
        j = edges.length - 1;

    while (i <= j) {
        var mid = Math.floor((i + j) / 2);

        if (edge === edges[mid]) {
            edges.splice(mid, 1);
            return;
        }

        if (compareEdges(edge, edges[mid])) j = mid - 1;
        else i = mid + 1;
    }
}

function compareEdges(e1, e2) {
    return e2.p1.y === e2.p2.y ? (e1.p1.y === e1.p2.y ? e1.p1.y < e2.p1.y : isConvex(e1.p1, e1.p2, e2.p1)) :
           e1.p1.y <= e1.p2.y ? !isConvex(e2.p1, e2.p2, e1.p1) : isConvex(e1.p1, e1.p2, e2.p1);
}

function Edge(p1, p2, index) {
    this.p1 = p1;
    this.p2 = p2;
    this.index = index;
}


// function findEdge(items, edge) {

//     var i = 0,
//         j = items.length - 1;

//     while (i <= j) {
//         var mid = Math.floor((i + j) / 2);
//         var c = compareEdges(edge, items[mid]);

//         if (c === 0) return mid;

//         if (c < 0) j = mid - 1;
//         else i = mid + 1;
//     }

//     return null;
// }

// function removeEdge(items, edge) {
//     var index = findEdge(items, edge);
//     if (index !== null) items.splice(index, 1);
// }