ls.js

// Incremetal Line sweep for line intersection only
function lineSweep(bst, pq, sweepLine) {
    var output = [];
    var p, lineAbove, lineBelow;
    
    // Line sweep
    if (!pq.empty()) {
        p = pq.extract();
        drawSweepLine(p, sweepLine);
        
        // Line end point
        if (p.line) {
            if (p.left) {
                // Left point hit, Insert p.line into BST
                bst.insert(p.line.data.y, p.line);
                p.line.strokeColor = 'orange';
                
                // Get intersection point of p.line with the line above and below
                getIntersectPoint(pq, output, p.line, bst.pred(p.line.data.y));
                getIntersectPoint(pq, output, p.line, bst.succ(p.line.data.y));
            }
            else {
                // Right point hit, get intersection of line above and below p.line
                getIntersectPoint(pq, output, bst.succ(p.line.data.y), bst.pred(p.line.data.y));
                
                // Remove p.line as its right point has been processed
                bst.remove(p.line.data.y);
                p.line.strokeColor = 'black';
            }
        }
        // Intersection point
        else if (p.intersect) {
            // Swap position of the lines above and below in BST, if both exist
            swap(bst, p.intersect[0], p.intersect[1]);
            
            // Get intersection of the lines with their new neighbors after swap
            getIntersectPoint(pq, output, p.intersect[0], bst.pred(p.intersect[0].data.y));
            getIntersectPoint(pq, output, p.intersect[1], bst.succ(p.intersect[1].data.y));
        }
    }
    return output;
}

function drawSweepLine(p, sweepLine) {
    sweepLine.position = new Point(p.x, sweepLine.position.y);
}

// Returns intersection point of line AB and CD
function intersectPoint(a, b, c, d) {
    // line1 = p1 + k1 [p2-p1]
    // line2 = p3 + k2 [p3-p4]
    var line1 = { x: b.x - a.x, y: b.y - a.y };
    var kd = (b.x - a.x) * (d.y - c.y) - (d.x - c.x) * (b.y - a.y);
    
    if (kd != 0) {
        var k1 = ((d.x - c.x) * (a.y - c.y) - (a.x - c.x) * (d.y - c.y)) / kd;
        var k2 = ((b.x - a.x) * (a.y - c.y) - (a.x - c.x) * (b.y - a.y)) / kd;
        
        if (k1 >= 0 && k1 <= 1 && k2 >= 0 && k2 <= 1) {
            // solve for x, y with any point (p1), line 1
            return { x: a.x + k1 * line1.x, y: a.y + k1 * line1.y };
        }
    }
    return null;
}

// Get intersection point if exists, add to output and PQ
function getIntersectPoint(pq, output, line1, line2) {
    if (line1 && line2) {
        var intersect = intersectPoint(line1.segments[0].point, line1.segments[1].point, line2.segments[0].point, line2.segments[1].point);
        if (intersect && !pq.exists([intersect.x, intersect.y])) {
            line1.strokeColor = line2.strokeColor = 'blue';
            setTimeout(function () {
                line1.strokeColor = line2.strokeColor = 'orange';
            }, 500);
            var p = new LSPoint(intersect.x, intersect.y);
            p.intersect = (line1.data.y > line2.data.y) ? [line1, line2] : [line2, line1];    // [0] above (higher Y), [1] below
            pq.insert([intersect.x, intersect.y], p);
            output.push(p);
        }
    }
}

// Swap y position of the lines, re-insert into BST
function swap(bst, line1, line2) {
    var y1 = line1.data.y;
    var y2 = line2.data.y;
    line1.data.y = y2;
    line2.data.y = y1;
    bst.remove(y1);
    bst.remove(y2);
    bst.insert(y2, line1);
    bst.insert(y1, line2);
}

// Point
LSPoint = function(x, y, id = '') {
    this.id = id;
    this.left = 0;
    this.x = x;
    this.y = y;
    this.line = '';
    this.intersect = '';
}
// Line
LSLine = function(p1, p2, id = '') {
    var dx = p1.x - p2.x;
    var dy = p1.y - p2.y;
    this.id = id;
    // Assign left point of line, breaks ties with y
    if (dx < 0 || (dx == 0 && dy < 0)) {
        this.point = [p1, p2];
        this.y = p1.y;
        p1.left = 1;
    }
    else if (dx > 0 || (dx == 0 && dy > 0)) {
        this.point = [p2, p1];
        this.y = p2.y;
        p2.left = 1;
    }
    // Circular reference with line and point, no JSON.stringify for now
    p1.line = this;
    p2.line = this;
}

// Data structures
// Tree node
// Numeric / Array of numeric keys only
TNode = function(k, v) {
    this.value = v;
    this.key = k;
    this.left = '';
    this.right = '';
    this.parent = '';
    this.index = -1;
}
TNode.prototype.compare = function(a) {
    var t;
    if (!this.key)
        t = 1;
    else if (!a.key)
        t = -1;
    else if (Array.isArray(this.key) && Array.isArray(a.key)) {
        for (var i = 0; i < a.key.length; i++) {
            t = Math.sign(Number(this.key[i]) - Number(a.key[i]));
            if (t != 0)
                break;
        }
    }
    else
        t = Math.sign(Number(this.key) - Number(a.key));
    return t;
}

// Binary search tree
BST = function() {
    this.root = '';
    this.size = 0;
}
BST.prototype.insert = function(k, v) {
    var nNew = new TNode(k, v);
    if (!this.root)
        this.root = nNew;
    else {
        var n = this.root;
        while (1) {
            if (nNew.compare(n) < 0) {
                if (n.left)
                    n = n.left;
                else {
                    n.left = nNew;
                    nNew.parent = n;
                    break;
                }
            }
            else {
                if (n.right)
                    n = n.right;
                else {
                    n.right = nNew;
                    nNew.parent = n;
                    break;
                }
            }
        }
    }
    this.size++;
}
BST.prototype.remove = function(k) {
    var nDelete = this.find(k);
    if (nDelete) {
        this.removeRecursive(nDelete);
        this.size--;
    }
}
BST.prototype.removeRecursive = function(nDelete) {
    if (nDelete.left && !nDelete.right)             // Has left
        this.replaceParent(nDelete.left, nDelete);
    else if (!nDelete.left && nDelete.right)        // Has right
        this.replaceParent(nDelete.right, nDelete);
    else if (!nDelete.left && !nDelete.right)       // No child
        this.replaceParent(null, nDelete);
    else {                                          // Has 2 children
        // Find min in right subtree
        var nMin = this.findMin(nDelete.right);
        
        // Copy min node to the node to delete
        nDelete.value = nMin.value;
        nDelete.key = nMin.key;
        
        // Delete old min node
        this.removeRecursive(nMin);
    }
}
BST.prototype.find = function(k) {
    return this.findRecursive(this.root, new TNode(k));
}
BST.prototype.findRecursive = function(nCurrent, nFind) {
    if (!nCurrent)
        return null;
    if (nFind.compare(nCurrent) == 0)
        return nCurrent;
    else if (nFind.compare(nCurrent) < 0)
        return this.findRecursive(nCurrent.left, nFind);
    else
        return this.findRecursive(nCurrent.right, nFind);
}
BST.prototype.succ = function(k) {
    var n = this.find(k);
    if (n.right)
        return this.findMin(n.right).value;
    while (n.parent) {
        if (n.parent.left == n)
            return n.parent.value;
        else
            n = n.parent;
    }
    return null;
}
BST.prototype.pred = function(k) {
    var n = this.find(k);
    if (n.left)
        return this.findMax(n.left).value;
    while (n.parent) {
        if (n.parent.right == n)
            return n.parent.value;
        else
            n = n.parent;
    }
    return null;
}
BST.prototype.findMin = function(n) {
    while (n.left) {
        n = n.left;
    }
    return n;
}
BST.prototype.findMax = function(n) {
    while (n.right) {
        n = n.right;
    }
    return n;
}
BST.prototype.replaceParent = function(nChild, nParent) {
    if (nChild) {
        nParent.left = nChild.left;
        nParent.right = nChild.right;
        nParent.value = nChild.value;
        nParent.key = nChild.key;
        if (nChild.left)
            nChild.left.parent = nParent;
        if (nChild.right)
            nChild.right.parent = nParent;
    }
    else {
        if (!nParent.parent) {
            this.root = null;
        }
        else {
            if (nParent.parent.left == nParent)
                nParent.parent.left = null;
            else if (nParent.parent.right == nParent)
                nParent.parent.right = null;
        }
    }
}
// data structures should preferably be independent of its node value
BST.prototype.print = function(n) {
    // In-order traversal
    var s = '';
    if (n) {
        if (n.left)
            s += this.print(n.left);
        s += n.value.name + '\n';
        if (n.right)
            s += this.print(n.right);
    }
    return s;
}

// Priority Queue, Heap implementation
PriorityQueue = function(a) {
    this.capacity = Math.pow(2, Math.floor(Math.log2(a) + 1));
    this.length = 0;
    this.queue = [];
    this.unique = {};
    for (var i = 0; i < this.capacity; i++) {
        this.queue[i] = new TNode();   // null, placeholder node
    }
}
PriorityQueue.prototype.empty = function() {
    return this.length == 0;
}
PriorityQueue.prototype.exists = function(k) {
    if (this.unique[this.roundKey(k)])
        return true;
    else
        return false;
}
PriorityQueue.prototype.insert = function(k, v) {
    this.queue[this.length] = new TNode(k, v);
    this.queue[this.length].index = this.length;
    this.unique[this.roundKey(k)] = this.queue[this.length];
    this.incPriority(this.length);
    this.length++;
}
PriorityQueue.prototype.extract = function(iIndex = 0) {
    var objMin = null;
    if (this.length > 0) {
        objMin = this.queue[iIndex].value;
        this.unique[this.roundKey(this.queue[iIndex].key)] = 'deleted';
        this.queue[iIndex] = this.queue[this.length - 1];
        this.queue[this.length - 1] = new TNode();
        this.decPriority(iIndex);
        this.length--;
    }
    return objMin;
}
PriorityQueue.prototype.remove = function(k) {
    k = this.roundKey(k);
    if (this.unique[k] && this.unique[k] != 'deleted')
        return this.extract(this.unique[k].index);
},
PriorityQueue.prototype.incPriority = function(iIndex) {
    while (iIndex > 0) {
        var iParent = Math.floor((iIndex - 1) / 2);
        if (this.queue[iIndex].compare(this.queue[iParent]) < 0) {
            this.swap(iIndex, iParent);
            iIndex = iParent;
        }
        else break;
    }
}
PriorityQueue.prototype.decPriority = function(iIndex) {
    while (1) {
        var iLeft = 2 * iIndex + 1;
        var iRight = iLeft + 1;
        if (iLeft < this.length) {
            var iChild = this.queue[iLeft].compare(this.queue[iRight]) < 0 ? iLeft : iRight;
            if (this.queue[iIndex].compare(this.queue[iChild]) > 0) {
                this.swap(iChild, iIndex);
                iIndex = iChild;
            }
            else break;
        }
        else break;
    }
}
PriorityQueue.prototype.swap = function(iA, iB) {
    var t = this.queue[iA];
    this.queue[iA] = this.queue[iB];
    this.queue[iB] = t;
    this.queue[iA].index = iA;
    this.queue[iB].index = iB;
}
PriorityQueue.prototype.roundKey = function(k) {
    // Round the key to 4 decimal place to identify duplicate key more reliably
    // It is a terrible idea to use float as key
    // but it is the only node value independent way to identify nodes for now
    var key = '';
    if (Array.isArray(k)) {
        var len = k.length;
        for (var i = 0; i < len; i++) {
            k[i] = Math.round(k[i] * 10000) / 10000;
        }
        key = k.join('_');
    }
    else {
        key = Math.round(k * 10000) / 10000;
    }
    return key;
}
PriorityQueue.prototype.clear = function() {
    this.queue = [];
    this.unique = {};
    this.length = 0;
    this.capacity = 0;
}