Implementation of Sweepline

sweepline.js

function intersects(line_one, line_two) {
    if(line_one.first.x == line_one.second.x) {
        // line_one is vertical.
        if(line_two.first.x == line_two.second.x) {
            // line_two is also vertical? This isn't looking that good...
            return line_two.first.x == line_one.first.x && line_one.first.y <= line_two.second.y && line_one.second.y >= line_two.first.y;
        } else {
            // line_two is horizontal.
            return line_two.first.x <= line_one.first.x && line_two.second.x >= line_one.first.x && line_one.first.y <= line_two.first.y && line_one.second.y >= line_two.first.y;
        }
    } else {
        // line_one is horizontal.
        if(line_two.first.x == line_two.second.x) {
            // line_two is vertical.
            return line_two.first.y <= line_one.first.y && line_two.second.y >= line_one.first.y && line_one.first.x <= line_two.first.x && line_one.second.x >= line_two.first.x;
        } else {
            if(line_one.first.y == line_two.first.y) {
                // line_two is horizontal as well... treat as normal range overlap
                return line_one.first.x <= line_two.second.x && line_one.second.x >= line_two.first.x;
            }
        }
    }
    return false;
}
function make_line(a, b, c, d) {
    if(a > c) {
        [a, c] = [c, a];
        [b, d] = [d, b];
    }
    let result = { first: { x: a, y : b}, second: { x : c, y: d } };
    // console.log("Made line: ", result);
    return result
}
function naive(lines) {
    let comparisons = 0;
    for(let i = 0; i < lines.length - 1; i++) {
        let line_one = lines[i];
        for(let j = i + 1; j < lines.length; j++) {
            let line_two = lines[j];
            comparisons++;
            if(intersects(make_line(...line_one), make_line(...line_two))) {
                console.log("OVERLAPS: ", i, j)
            }
        }
    }
    console.log(comparisons)
}
let MARKER = {
    BEGIN: 0,
    END: 1
}
function smart(lines) {
    let comparisons = 0
    let points = []
    for(let i = 0; i < lines.length; i++) {
        let { first, second } = make_line(...lines[i]);
        points.push({ point: first, line: i, MARKER: MARKER.BEGIN })
        points.push({ point: second, line: i, MARKER: MARKER.END })
    }
    points.sort((point1, point2) => {
        let { x: x1, y: y1 } = point1.point;
        let { x: x2, y: y2 } = point2.point;
        comparisons++;
        if( x2 < x1 ) {
            return 1
        } else if( x2 > x1 ) {
            return -1
        } else if( x2 == x1) {
            if( y2 < y1 ) {
                return 1
            } else if( y2 > y1 ) {
                return -1
            } else {
                if(point1.MARKER < point2.MARKER) {
                    return -1;
                } else if(point2.MARKER > point1.MARKER) {
                    return 1;
                }
                return 0
            }
        }
    })
    let beginnings = new Map()
    for(let i = 0; i < points.length; i++) {
        let { line, point } = points[i];
        if(beginnings.has(line)) {
            let start = beginnings.get(line)
            beginnings.delete(line)
            for(let other_line of beginnings.keys()) {
                let other_point = beginnings.get(other_line)        
                comparisons++;
                if(other_point.y <= point.y && other_point.y >= start.y) {                
                    console.log("OVERLAPS: ", line, other_line)
                }
            }
        } else {
            beginnings.set(line, point)
        }
    }
    console.log(comparisons)
}