Algorithme d'aplatissement des plages de chevauchement

Je recherche une belle façon d'aplatir (fractionner) une liste de plages numériques potentiellement chevauchantes. Le problème est très similaire à celui de cette question: moyen le plus rapide de fractionner les plages de dates qui se chevauchent , et bien d'autres.

Cependant, les plages ne sont pas uniquement des entiers, et je recherche un algorithme décent qui peut être facilement implémenté en Javascript ou Python, etc.

Exemples de données:

Exemple de solution:

Toutes mes excuses s'il s'agit d'un doublon, mais je n'ai pas encore trouvé de solution.

Marchez de gauche à droite en utilisant une pile pour garder une trace de la couleur sur laquelle vous vous trouvez. Au lieu d'une carte discrète, utilisez les 10 nombres de votre jeu de données comme points d'arrêt.

En commençant avec une pile vide et en mettant startà 0, bouclez jusqu'à ce que nous atteignions la fin:

• Si la pile est vide:
  • Recherchez la première couleur à partir de ou après start, et poussez-la et toutes les couleurs de rang inférieur sur la pile. Dans votre liste aplatie, marquez le début de cette couleur.
• sinon (si non vide):
  • Trouvez le point de début suivant pour toute couleur de rang supérieur à ou après start, et trouvez la fin de la couleur actuelle
    • Si la couleur suivante commence en premier, poussez-la et toute autre chose sur le chemin vers la pile. Mettez à jour la fin de la couleur actuelle comme début de celle-ci et ajoutez le début de cette couleur à la liste aplatie.
    • S'il n'y en a pas et que la couleur actuelle se termine en premier, définissez-la startà la fin de cette couleur, retirez-la de la pile et vérifiez la couleur classée la plus élevée suivante.
      • Si se starttrouve dans la plage de couleurs suivante, ajoutez cette couleur à la liste aplatie, en commençant par start.
      • Si la pile se vide, continuez simplement la boucle (revenez au premier point).

Ceci est un passage mental étant donné vos données d'exemple:

# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty.  Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color.  Next off stack, "y", has already ended.  Next off stack, "g", has not ended.  Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color.  Next off stack, "b", is out of range (already ended).  Next off stack, "r", is out of range (not started).  Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty.  Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color.  Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.

Cette solution semble la plus simple. (Ou du moins, le plus facile à saisir)

Il suffit d'une fonction pour soustraire deux plages. En d'autres termes, quelque chose qui donnera ceci:

A ------               A     ------           A    ----
B    -------    and    B ------        and    B ---------
=       ----           = ----                 = ---    --

Ce qui est assez simple. Ensuite, vous pouvez simplement parcourir chacune des plages, en commençant par la plus basse, et pour chacune, en soustraire à tour de rôle toutes les plages au-dessus. Et voila.

Voici une implémentation du soustracteur de plage en Python:

def subtractRanges((As, Ae), (Bs, Be)):
    '''SUBTRACTS A FROM B'''
    # e.g, A =    ------
    #      B =  -----------
    # result =  --      ---
    # Returns list of new range(s)

    if As > Be or Bs > Ae: # All of B visible
        return [[Bs, Be]]
    result = []
    if As > Bs: # Beginning of B visible
        result.append([Bs, As])
    if Ae < Be: # End of B visible
        result.append([Ae, Be])
    return result

En utilisant cette fonction, le reste peut être fait comme ceci: (Un 'span' signifie une plage, car 'range' est un mot-clé Python)

spans = [["red", [12.5, 13.8]],
["blue", [0.0, 5.4]],
["green", [2.0, 12.0]],
["yellow", [3.5, 6.7]],
["orange", [6.7, 10.0]]]

i = 0 # Start at lowest span
while i < len(spans):
    for superior in spans[i+1:]: # Iterate through all spans above
        result = subtractRanges(superior[1], spans[i][1])
        if not result:      # If span is completely covered
            del spans[i]    # Remove it from list
            i -= 1          # Compensate for list shifting
            break           # Skip to next span
        else:   # If there is at least one resulting span
            spans[i][1] = result[0]
            if len(result) > 1: # If there are two resulting spans
                # Insert another span with the same name
                spans.insert(i+1, [spans[i][0], result[1]])
    i += 1

print spans

Cela donne [['red', [12.5, 13.8]], ['blue', [0.0, 2.0]], ['green', [2.0, 3.5]], ['green', [10.0, 12.0]], ['yellow', [3.5, 6.7]], ['orange', [6.7, 10.0]]], ce qui est correct.

Si la portée des données est similaire à celle de vos exemples de données, vous pouvez créer une carte comme celle-ci:

map = [0 .. 150]

for each color:
    for loc range start * 10 to range finish * 10:
        map[loc] = color

Parcourez ensuite cette carte pour générer les plages

curcolor = none
for loc in map:
    if map[loc] != curcolor:
        if curcolor:
            rangeend = loc / 10
        make new range
        rangecolor = map[loc]
        rangestart = loc / 10

Pour fonctionner, les valeurs doivent être dans une plage relativement petite, comme dans vos exemples de données.

Modifier: pour travailler avec de vrais flottants, utilisez la carte pour générer une cartographie de haut niveau, puis référez-vous aux données d'origine pour créer les limites.

map = [0 .. 15]

for each color:
   for loc round(range start) to round(range finish):
        map[loc] = color

curcolor = none
for loc in map
    if map[loc] != curcolor:

        make new range
        if loc = round(range[map[loc]].start)  
             rangestart = range[map[loc]].start
        else
             rangestart = previous rangeend
        rangecolor = map[loc]
        if curcolor:
             if map[loc] == none:
                 last rangeend = range[map[loc]].end
             else
                 last rangeend = rangestart
        curcolor = rangecolor

Voici une solution relativement simple dans Scala. Il ne devrait pas être trop difficile de porter dans une autre langue.

case class Range(name: String, left: Double, right: Double) {
  def overlapsLeft(other: Range) =
    other.left < left && left < other.right

  def overlapsRight(other: Range) =
    other.left < right && right < other.right

  def overlapsCompletely(other: Range) =
    left <= other.left && right >= other.right

  def splitLeft(other: Range) = 
    Range(other.name, other.left, left)

  def splitRight(other: Range) = 
    Range(other.name, right, other.right)
}

def apply(ranges: Set[Range], newRange: Range) = {
  val left     = ranges.filter(newRange.overlapsLeft)
  val right    = ranges.filter(newRange.overlapsRight)
  val overlaps = ranges.filter(newRange.overlapsCompletely)

  val leftSplit  =  left.map(newRange.splitLeft)
  val rightSplit = right.map(newRange.splitRight)

  ranges -- left -- right -- overlaps ++ leftSplit ++ rightSplit + newRange
}

val ranges = Vector(
  Range("red",   12.5, 13.8),
  Range("blue",   0.0,  5.4),
  Range("green",  2.0, 12.0),
  Range("yellow", 3.5,  6.7),
  Range("orange", 6.7, 10.0))

val flattened = ranges.foldLeft(Set.empty[Range])(apply)
val sorted = flattened.toSeq.sortBy(_.left)
sorted foreach println

applyprend dans une Setde toutes les plages qui ont déjà été appliquées, trouve les chevauchements, puis retourne un nouvel ensemble moins les chevauchements et plus la nouvelle plage et les plages nouvellement divisées. foldLeftappels répétés applyavec chaque plage d'entrée.

Gardez simplement un ensemble de plages triées par début. Ajoutez une gamme qui couvre tout (-oo .. + oo). Pour ajouter une plage r:

let pre = last range that starts before r starts

let post = earliest range that starts before r ends

now iterate from pre to post: split ranges that overlap, remove ranges that are covered, then add r