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

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。

- petrelharp

---

至少有一个区间覆盖的总面积为3.5。我似乎漏掉了什么 - 你是如何计算出这个结果的？ - davmac

区间覆盖的面积 - 维度不匹配？ - n. m.

我在通用意义上使用“区域”（这里指“长度”）。@davmac 画个图？ - petrelharp

Answer 1

这是一道典型的计算几何问题，需要进行线性扫描。

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

每次遇到+1时，将高度增加1。每次遇到-1时，将高度减小。当你从p1移动到p2时，在给定高度下添加p2-p1（覆盖的长度）。

然后你会得到每个高度覆盖的长度直方图。如果要处理“至少两个区间”的情况，可以累加总数。

- Rob Neuhaus

---

很棒，就是我想要的！ - petrelharp

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值映射到沿着线的距离的对象。

- sethobrien