Algoritma, bir dizi örtüşen bölümün kapsadığı toplam alanı hesaplamak için?

Question

Muhtemelen çakışan aralıkların bir uç noktalarının bir listesi var ve k=1,2,... (çift yönlü karşılaştırma yapmadan) için, k aralıklarıyla kaplanan toplam alanı hesaplamanın verimli bir yolunu kullanmak istiyorum. Yoksa bu mümkün değil mi?

Örneğin

, diyelim ki X başlangıç ​​noktalarının listesi ve y bitiş noktaları, ve x[i] < y[i] listesi ve

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

şekilde en az bir aralık ile kaplı toplam alan olduğundan 3.5 ve en az iki tarafından kapsanan toplam alan 1'dir.

teşekkürler, ph.

Answer 1

Bu hesaplama geometrilerinden klasik çizgi süpürme problemidir.

Her başlangıç ​​noktasına +1 ve her son noktaya bir -1 koyun. Ardından, negatif sonsuzdan pozitif sonsuzluğa kadar sayı çizgisinde yürümeyi hayal edin.

+1 ile her karşılaştığınızda, boyunu 1 artırın. -1'e her vurduğunuzda, boyunu azaltın. Sayı çizgisinde p1'den p2'ye geçerken, verilen yüksekliğin kapsadığı miktarda p2 - p1 (uzunluk taraması) ekleyin.

Ardından, her yükseklik tarafından tam olarak kapsanan uzunluk histogramınız olur. "En az iki aralık" durumunun üstesinden gelmek istiyorsanız toplamları biriktirebilirsiniz.

Answer 2

Ben de aynı şeyi yazarken @ rrenaud'un çözümünü yayınladığını bilmiyordum, bu yüzden açıklamayı çıkartacağım ve sadece kodu vereceğim.

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

Bu hat boyunca mesafelere k değerlerini eşleştiren bir nesne döndürür: Bu satır süpürme bir javascript versiyonudur.