¿Cómo se divide un conjunto de rangos superpuestos en rangos no superpuestos?

Question

Digamos que usted tiene un conjunto de rangos:

• 0 - 100: 'a'
• 0 - 75: 'b'
• 95 - 150: 'c'
• 120-130 : 'd'

Obviamente, estos rangos se superponen en ciertos puntos. ¿Cómo analizaría estos rangos para producir una lista de rangos que no se superpongan, mientras retiene información asociada con su rango original (en este caso, la letra después del rango)?

Por ejemplo, los resultados de lo anterior después de ejecutar el algoritmo serían:

• 0 - 75: 'a', 'b'
• 76-94: 'a'
• 95 - 100: 'a', 'c'
• 101 - 119: 'c'
• 120 - 130: 'c', 'd'
• 131 - 150: 'c'

Answer 1

Tuve la misma pregunta cuando escribía un programa para mezclar muestras de audio (parcialmente superpuestas).

Lo que hice fue agregar un "evento de inicio" y "evento de detención" (para cada elemento) a una lista, ordenar la lista por punto de tiempo y luego procesarla en orden. Podrías hacer lo mismo, excepto usar un punto entero en lugar de un tiempo, y en lugar de mezclar sonidos estarías agregando símbolos al conjunto correspondiente a un rango. Si usted generaría rangos vacíos o simplemente los omitiría sería opcional.

Edit Tal vez algo de código ...

# input = list of (start, stop, symbol) tuples 
points = [] # list of (offset, plus/minus, symbol) tuples 
for start,stop,symbol in input: 
    points.append((start,'+',symbol)) 
    points.append((stop,'-',symbol)) 
points.sort() 

ranges = [] # output list of (start, stop, symbol_set) tuples 
current_set = set() 
last_start = None 
for offset,pm,symbol in points: 
    if pm == '+': 
     if last_start is not None: 
      #TODO avoid outputting empty or trivial ranges 
      ranges.append((last_start,offset-1,current_set)) 
     current_set.add(symbol) 
     last_start = offset 
    elif pm == '-': 
     # Getting a minus without a last_start is unpossible here, so not handled 
     ranges.append((last_start,offset-1,current_set)) 
     current_set.remove(symbol) 
     last_start = offset 

# Finish off 
if last_start is not None: 
    ranges.append((last_start,offset-1,current_set)) 

totalmente probado, obviamente.

Answer 2

Yo diría crear una lista de los puntos finales y ordenarlos, también indexar la lista de rangos por puntos de inicio y finalización. A continuación, repita la lista de puntos finales ordenados y, para cada uno, compruebe los intervalos para ver cuáles se están iniciando/deteniendo en ese punto.

Esta es, probablemente, mejor representada en el código ... si sus rangos son representados por tuplas:

ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')] 
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges]))) 
start = {} 
end = {} 
for e in endpoints: 
    start[e] = set() 
    end[e] = set() 
for r in ranges: 
    start[r[0]].add(r[2]) 
    end[r[1]].add(r[2]) 
current_ranges = set() 
for e1, e2 in zip(endpoints[:-1], endpoints[1:]): 
    current_ranges.difference_update(end[e1]) 
    current_ranges.update(start[e1]) 
    print '%d - %d: %s' % (e1, e2, ','.join(current_ranges)) 

Aunque mirando esto en retrospectiva, me sorprendería si no había una forma más eficiente (o al menos de aspecto más limpio) forma de hacerlo.

Answer 3

Pseudocódigo:

unusedRanges = [ (each of your ranges) ] 
rangesInUse = [] 
usedRanges = [] 
beginningBoundary = nil 

boundaries = [ list of all your ranges' start and end values, sorted ] 
resultRanges = [] 

for (boundary in boundaries) { 
    rangesStarting = [] 
    rangesEnding = [] 

    // determine which ranges begin at this boundary 
    for (range in unusedRanges) { 
     if (range.begin == boundary) { 
      rangesStarting.add(range) 
     } 
    } 

    // if there are any new ones, start a new range 
    if (rangesStarting isn't empty) { 
     if (beginningBoundary isn't nil) { 
      // add the range we just passed 
      resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse]) 
     } 

     // note that we are starting a new range 
     beginningBoundary = boundary 

     for (range in rangesStarting) { 
      rangesInUse.add(range) 
      unusedRanges.remove(range) 
     } 
    } 

    // determine which ranges end at this boundary 
    for (range in rangesInUse) { 
     if (range.end == boundary) { 
      rangesEnding.add(range) 
     } 
    } 

    // if any boundaries are ending, stop the range 
    if (rangesEnding isn't empty) { 
     // add the range up to this boundary 
     resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse] 

     for (range in rangesEnding) { 
      usedRanges.add(range) 
      rangesInUse.remove(range) 
     } 

     if (rangesInUse isn't empty) { 
      // some ranges didn't end; note that we are starting a new range 
      beginningBoundary = boundary + 1 
     } 
     else { 
      beginningBoundary = nil 
     } 
    } 
} 

Unidad de prueba:

Al final, resultRanges deben tener los resultados que está buscando, y unusedRanges rangesInUse deben estar vacíos, beginningBoundary debe ser nulo, y deberían hacerlo usedRanges contiene lo que los rangos no utilizados solían contener (pero ordenados por range.end).

Answer 4

Lo que describes es un ejemplo de la teoría de conjuntos.Para un algoritmo general para las cooperativas de computación, intersecciones y diferencias de conjuntos ver:

www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf

Si bien el documento está dirigido a los gráficos que se aplica a la teoría de conjuntos en general. No es exactamente material de lectura ligera.