How to divide a set of overlapping ranges into non-overlapping ranges?

Question

Let's say you have a set of ranges:

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

Obviously, these ranges overlap at certain points. How would you dissect these ranges to produce a list of non-overlapping ranges, while retaining information associated with their original range (in this case, the letter after the range)?

For example, the results of the above after running the algorithm would be:

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

Answer 1

I'd say create a list of the endpoints and sort it, also index the list of ranges by starting and ending points. Then iterate through the list of sorted endpoints, and for each one, check the ranges to see which ones are starting/stopping at that point.

This is probably better represented in code... if your ranges are represented by tuples:

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

Although looking at this in retrospect, I'd be surprised if there wasn't a more efficient (or at least cleaner-looking) way to do it.

Answer 2

I had the same question when writing a program to mix (partly overlapping) audio samples.

What I did was add an "start event" and "stop event" (for each item) to a list, sort the list by time point, and then process it in order. You could do the same, except using an integer point instead of a time, and instead of mixing sounds you'd be adding symbols to the set corresponding to a range. Whether you'd generate empty ranges or just omit them would be optional.

Edit Perhaps some 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))

Totally untested, obviously.

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:

At the end, resultRanges should have the results you're looking for, unusedRanges and rangesInUse should be empty, beginningBoundary should be nil, and usedRanges should contain what unusedRanges used to contain (but sorted by range.end).

Answer 4

What you describe is an example of set theory. For a general algorithm for computing unions, intersections, and differences of sets see:

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

While the paper is targeted at graphics it is applicable to general set theory as well. Not exactly light reading material.