Wie teilt man einen Satz überlappender Bereiche in nicht überlappende Bereiche ein?

Question

Angenommen, Sie haben eine Reihe von Bereichen haben:

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

Offensichtlich überlappen diese Bereiche an bestimmten Punkten. Wie würden Sie diese Bereiche sezieren, um eine Liste von nicht überlappenden Bereichen zu erstellen, während Sie Informationen beibehalten, die mit ihrem ursprünglichen Bereich (in diesem Fall dem Buchstaben nach dem Bereich) verknüpft sind?

Zum Beispiel können die Ergebnisse der nach dem obigen Algorithmus ausgeführt wären:

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

Answer 1

Ich hatte die gleiche Frage beim Schreiben eines Programms zum Mischen (teilweise Überlappung) von Audio-Samples.

Was ich getan habe, war ein "Start-Ereignis" und "Stop-Ereignis" (für jedes Element) zu einer Liste hinzufügen, sortieren Sie die Liste nach Zeitpunkt, und dann in der Reihenfolge zu verarbeiten. Sie könnten dasselbe tun, außer dass Sie einen Integer-Punkt anstelle einer Zeit verwenden, und statt Sounds zu mischen, würden Sie dem Set, das einem Bereich entspricht, Symbole hinzufügen. Ob Sie leere Bereiche generieren oder einfach weglassen, wäre optional.

Edit Vielleicht haben einige Code ...

# 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)) 

Völlig ungetestet, offensichtlich.

Answer 2

Ich würde sagen, erstellen Sie eine Liste der Endpunkte und sortieren Sie sie, indexieren Sie auch die Liste der Bereiche nach Start- und Endpunkten. Durchlaufen Sie dann die Liste der sortierten Endpunkte, und überprüfen Sie für jeden Bereich die Bereiche, um zu sehen, welche an diesem Punkt starten/stoppen.

ist dies wahrscheinlich besser in Code dargestellt ..., wenn Ihre Bereiche von Tupeln dargestellt werden: in diesem

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)) 

Obwohl im Nachhinein suchen, ich wäre überrascht, wenn es nicht ein effizientes ist (oder zumindest sauberer aussehen).

Answer 3

Pseudocode:

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

Unit-Test:

Am Ende resultRanges sollten die Ergebnisse haben Sie, unusedRanges und rangesInUse gesuchte leer sein sollte, beginningBoundary Null sein sollte, und usedRanges sollte enthalten, was unusedRanges enthielt (aber sortiert nach range.end).

Answer 4

Was Sie beschreiben, ist ein Beispiel für Mengenlehre.Für einen allgemeinen Algorithmus zur Berechnung Gewerkschaften, Kreuzungen und Unterschiede von Sätzen sehen:

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

Während das Papier bei Grafiken gezielt wird, ist es auch auf allgemeine Mengenlehre anwendbar. Nicht gerade leichtes Lesematerial.