Algorithm to compute total area covered by a set of overlapping segments?

Question

I have a list of endpoints of possibly overlapping intervals, and I'd like an efficient way to compute the total area covered by k intervals, for k=1,2,... (without doing all pairwise comparisons). Or, is this not possible?

For example, suppose x is the list of start points, and y is the list of end points, and that x[i] < y[i], and

x = (1.5, 2, 3, 5)
y = (3, 4, 4, 6)

so that the total area covered by at least one interval is 3.5, and the total area covered by at least two is 1.

thanks, ph.

Answer 1

This is a classic line sweep problem from computational geometry.

Put a +1 at each start point, and a -1 at every end point. Then imagine walking on the number line from negative infinity to positive infinity.

Every time you encounter a +1, increment your height by 1. Everytime you hit a -1, decrease your height. As you move from p1 to p2 on the number line, add p2 - p1 (length swept) to the amount covered by the given height.

Then you'll have a histogram of lengths covered by exactly by each height. You can accumulate the totals if you want to handle the "at least two intervals" case.

Answer 2

I didn't know @rrenaud had posted his solution while I was writing the same thing, so I'll omit the explanation and just give you the code. This is a javascript version of line sweep:

// x and y inputs are your start and end points for ranges,
// as in the example data
function countOverlapRanges(x, y) {
    var ranges = [];
    var n = x.length;
    if (n !== y.length) {
        throw "Input arrays must be the same length!";
    }
    var i;

    // iterate over all inputs, pushing them into the array
    for (i = 0; i < n; ++i) {
        ranges.push({
            value: x[i],
            change: 1
        });
        ranges.push({
            value: y[i],
            change: -1
        });
    }

    // sort the array into number-line order
    ranges.sort(function (a, b) {
        return a.value - b.value;
    });

    var result = {};
    var k = 1;
    var maxK = 1;
    n = ranges.length;

    // iterate over the sorted data, counting the size of ranges
    var cur, value, lastValue = ranges[0].value;
    for (i = 1; i < n; ++i) {
        cur = ranges[i];
        value = cur.value;
        if (k) {
            var difference = value - lastValue;
            result[k] = (result[k] || 0) + difference;
        }
        k += cur.change;
        maxK = Math.max(maxK, k);
        lastValue = value;
    }

    // so far we've counted the ranges covered by exactly k intervals.
    // adjust the results to get the size of ranges covered by
    // at least k intervals.
    var sum = 0;
    for (i = maxK; i > 0; --i) {
        sum = result[i] = sum + result[i];
    }

    return result;
}

It returns an object that maps k values to distances along the line.