Algoritmo para calcular el área total cubierta por un conjunto de segmentos superpuestos?

Question

Tengo una lista de puntos finales de intervalos posiblemente superpuestos, y me gustaría una forma eficiente de calcular el área total cubierta por k intervalos, para k=1,2,... (sin hacer todas las comparaciones por pares). ¿O esto no es posible?

Por ejemplo, x supongamos que es la lista de los puntos de inicio, e y es la lista de puntos finales, y que x[i] < y[i], y

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

de modo que el área total cubierta por al menos un intervalo es 3.5, y el área total cubierta por al menos dos es 1.

gracias, ph.

Answer 1

Este es un problema clásico de barrido de línea de la geometría computacional.

Ponga un +1 en cada punto de inicio y un -1 en cada punto final. Luego imagine caminar en la recta numérica desde el infinito negativo al infinito positivo.

Cada vez que encuentre un +1, incremente su altura en 1. Cada vez que golpee un -1, disminuya su altura. A medida que pasa de p1 a p2 en la recta numérica, agregue p2 - p1 (barrido de longitud) a la cantidad cubierta por la altura determinada.

A continuación, obtendrá un histograma de las longitudes cubiertas exactamente por cada altura. Puede acumular los totales si desea manejar el caso de "al menos dos intervalos".

Answer 2

No sabía @rrenaud había publicado su solución mientras escribía lo mismo, por lo que omitiré la explicación y solo le daré el código. Esta es una versión de JavaScript del barrido de línea:

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

Devuelve un objeto que asigna k valores a distancias a lo largo de la línea.