计算一组重叠线段覆盖的总面积的算法？

Question

我有一个可能重叠间隔的端点列表，并且我想要一种有效的方法来计算 k 间隔覆盖的总面积，对于 k=1,2,... （无需执行所有操作）两两比较）。或者说，这不可能吗？

例如，假设 x 是起点列表，y 是终点列表， 并且 x[i] y[i]，这样

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

至少一个区间覆盖的总面积为 3.5，至少两个区间覆盖的总面积为 1。

谢谢，ph。

Answer 1

这是计算几何中的经典线扫描问题。

在每个起点处放置 +1，在每个终点处放置 -1。然后想象一下沿着数轴从负无穷到正无穷行走。

每次遇到+1时，你的身高就增加1。每次遇到-1时，你的身高就会减少。当您在数轴上从 p1 移动到 p2 时，将 p2 - p1（扫描长度）添加到给定高度所覆盖的量。

然后您将得到每个高度精确覆盖的长度直方图。如果您想处理“至少两个间隔”的情况，您可以累积总数。

Answer 2

我不知道 @rrenaud 在我写同样的东西时发布了他的解决方案，所以我将省略解释，只给你代码。这是线扫描的 javascript 版本：

// 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;
}

它返回一个将 k 值映射到沿线距离的对象。