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

我有一个可能重叠区间的端点列表，我想要一个有效的方法来计算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。

来源

2011-09-08 petrelharp

”至少有一个区间覆盖的总面积是3.5“我错过了一些东西 - 你怎么看待这个问题？ – davmac

“间隔覆盖的区域” - 尺寸不匹配？ –

我的意思是一般意义上的“区域”（这里是“长度”）。 @davmac画一张照片？ – petrelharp

这是一个来自计算几何的经典线扫描问题。

在每个起点放一个+1，在每个终点放一个-1。然后想象一下从负无穷到正无穷的数字线上行走。

每次遇到+1时，将身高增加1.每次击中-1时，降低身高。当您从数字线上的p1移动到p2时，将p2 - p1（长度扫描）添加到给定高度覆盖的数量。

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

来源

2011-09-08 04:43:00

拉德，这将做到这一点。正是我在找的！ – petrelharp

我不知道@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值映射到沿线的距离。 “

来源

2011-09-08 05:25:20 sethobrien

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

回答

相关问题