オーバーラッピングセグメントのセットによってカバーされる総面積を計算するアルゴリズムはありますか？

Question

私はおそらく重複する区間の終点のリストを持っています。そして、私はk=1,2,...（すべてのペアワイズ比較を行うことなく）でk区間でカバーされる総面積を効率的に計算したいと思います。あるいは、これは不可能なのでしょうか？

少なくとも一つの区間によって覆われた総面積となるように、例えば、と仮定するxは開始点のリストであり、yは、エンドポイントのリストであり、 とx[i] < y[i]、及び

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

その3.5であり、少なくとも2つでカバーされる総面積は1である。

ありがとう、ph。

Answer 1

これは、計算幾何学から古典的な線掃引問題です。

各開始点に+1を付け、すべての終了点に-1を付けます。次に、負の無限大から正の無限大までの数値ラインを歩くことを想像してください。

あなたが+1に出くわすたびに、あなたの身長を1ずつ増やします。あなたが-1になるたびに身長を減らしてください。番号行のp1からp2に移動すると、指定された高さでカバーされる量にp2-p1（長さがスイープ）を追加します。

次に、縦のヒストグラムが各高さで正確にカバーされます。 「少なくとも2つの間隔」のケースを処理する場合は、合計を累積することができます。

Answer 2

私は同じことを書いている間に@rrenaudが自分の解決策を投稿したことを知らなかったので、説明を省略してコードを伝えます。

// 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値を線に沿った距離にマップするオブジェクトを返します。