Algoritmo per calcolare l'area totale coperta da un insieme di segmenti sovrapposti?

Question

Ho un elenco di endpoint di intervalli eventualmente sovrapposti e mi piacerebbe un modo efficiente per calcolare l'area totale coperta da intervalli k, per k=1,2,... (senza fare tutti i confronti a coppie). O questo non è possibile?

Ad esempio, supponiamo x è l'elenco dei punti di inizio e y è l'elenco dei punti finali, e che x[i] < y[i] e

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

modo che l'area totale coperta da almeno un intervallo è 3.5, e l'area totale coperta da almeno due è 1.

grazie, ph.

Answer 1

Questo è un classico problema di sweep della linea dalla geometria computazionale.

Metti un +1 in ciascun punto iniziale e un -1 in ogni punto finale. Quindi immagina di camminare sulla linea numerica dall'infinito negativo all'infinito positivo.

Ogni volta che si incontra un +1, aumentare l'altezza di 1. Ogni volta che si preme un -1, diminuire l'altezza. Mentre ci si sposta da p1 a p2 sulla linea numerica, aggiungere p2 - p1 (lunghezza spazzata) alla quantità coperta dall'altezza indicata.

Quindi avrai un istogramma delle lunghezze coperte esattamente da ogni altezza. È possibile accumulare i totali se si desidera gestire il caso "almeno due intervalli".

Answer 2

Non sapevo che @rrenaud avesse pubblicato la sua soluzione mentre stavo scrivendo la stessa cosa, quindi ometterò la spiegazione e ti darò il codice. Questa è una versione javascript della linea spazzata:

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

restituisce un oggetto che mappa i valori di k per distanze lungo la linea.