Another

by Bartosz Zieliński

HTML

<canvas id="dupa"></canvas>

JavaScript

class BoundingBox {
    constructor(segment, index) {
        const [x1, y1, x2, y2] = segment;
        this.minX = Math.min(x1, x2);
        this.maxX = Math.max(x1, x2);
        this.minY = Math.min(y1, y2);
        this.maxY = Math.max(y1, y2);
        this.segment = segment;
        this.index = index;
    }

    overlaps(other) {
        return !(this.maxX < other.minX || 
                this.minX > other.maxX ||
                this.maxY < other.minY || 
                this.minY > other.maxY);
    }
}

function findIntersectionPoint(seg1, seg2) {
    const [x1, y1, x2, y2] = seg1;
    const [sx1, sy1, sx2, sy2] = seg2;
    
    const dx = x2 - x1;
    const dy = y2 - y1;
    const dsx = sx2 - sx1;
    const dsy = sy2 - sy1;

    const denominator = (dx * dsy) - (dy * dsx);
    if (denominator === 0) return null;
    
    const ua = ((dsx * (y1 - sy1)) - (dsy * (x1 - sx1))) / denominator;
    const ub = ((dx  * (y1 - sy1)) - (dy *  (x1 - sx1))) / denominator;
    
    if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
        return [
            x1 + (ua * dx),
            y1 + (ua * dy)
        ];
    }
    return null;
}

function findOverlappingBoxes(mainBox, sortedBoxes, start, end) {
		if (start === undefined) start = 0;
    if (end   === undefined) end = sortedBoxes.length - 1;
    // Base case: single box
    if (start === end) {
        if (sortedBoxes[start].overlaps(mainBox)) {
            return [sortedBoxes[start]];
        }
        return [];
    }
    
    // Base case: empty range
    if (start > end) return [];
    
    const mid = Math.floor((start + end) / 2);
    const midBox = sortedBoxes[mid];
    
    // If main box is completely to the left of mid box, only search left half
    if (mainBox.maxX < midBox.minX) {
        return findOverlappingBoxes(mainBox, sortedBoxes, start, mid - 1);
    }
    
    // If main box is completely to the right of mid box, only search right half
    if (mainBox.minX > midBox.maxX) {
        return...