計算一組重疊片段覆蓋的總面積的算法？

我有一個可能重疊區間的端點列表，我想要一個有效的方法來計算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

計算一組重疊片段覆蓋的總面積的算法？

回答

相關問題