Algoritmo para achatar intervalos sobrepostos

15

Estou procurando uma maneira agradável de nivelar (dividir) uma lista de intervalos numéricos potencialmente sobrepostos. O problema é muito semelhante ao da pergunta: A forma mais rápida de dividir intervalos de datas sobrepostos e muitos outros.

No entanto, os intervalos não são apenas inteiros, e eu estou procurando um algoritmo decente que possa ser facilmente implementado em Javascript ou Python, etc.

Exemplo de dados:

Exemplodesolução:

Desculpas se esta for uma duplicata, mas ainda estou para encontrar uma solução.

    
por Jollywatt 29.05.2014 / 04:25
fonte

5 respostas

9

Ande da esquerda para a direita, usando uma pilha para acompanhar de que cor você está. Em vez de um mapa discreto, use os 10 números do seu conjunto de dados como pontos de quebra.

Começando com uma pilha vazia e definindo start para 0, faça um loop até chegar ao fim:

  • Se a pilha estiver vazia:
    • Procure a primeira cor que começa em ou antes de start e empurre-a e todas as cores com classificação mais baixa para a pilha. Na sua lista nivelada, marque o início dessa cor.
  • else (se não estiver vazio):
    • Encontre o próximo ponto inicial para qualquer cor com classificação mais alta em ou após start e encontre o fim da cor atual
      • Se a próxima cor começar primeiro, empurre-a e qualquer outra coisa no caminho para ela na pilha. Atualize o final da cor atual como o início desta e adicione o início dessa cor à lista simplificada.
      • Se não houver nenhuma e a cor atual terminar primeiro, defina start para o final dessa cor, retire-a da pilha e verifique a próxima cor mais alta classificada
        • Se start estiver no intervalo da próxima cor, adicione essa cor à lista nivelada, começando em start .
        • Se a pilha esvaziar, apenas continue o loop (volte para o primeiro ponto de marcador).

Esta é uma análise mental dos dados do seu exemplo:

# 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.
    
por 29.05.2014 / 06:34
fonte
3

Esta solução parece a mais simples. (Ou pelo menos, o mais fácil de entender)

Tudo o que é necessário é uma função para subtrair dois intervalos. Em outras palavras, algo que vai dar isso:

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

O que é simples o suficiente. Então você pode simplesmente iterar através de cada um dos intervalos, começando pelo mais baixo, e para cada um, subtrair de todos os intervalos acima, por sua vez. E aí está.

Aqui está uma implementação do subtrator range em 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

Usando esta função, o resto pode ser feito assim: (Um 'span' significa um intervalo, já que 'range' é uma palavra-chave do 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

Isso dá [['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]]] , o que é correto.

    
por 29.05.2014 / 07:41
fonte
2

Se os dados realmente tiverem um escopo semelhante aos dados de amostra, você poderá criar um mapa como este:

map = [0 .. 150]

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

Depois, percorra este mapa para gerar os intervalos

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

Para trabalhar, os valores precisam estar em um intervalo relativamente pequeno, como em seus dados de amostra.

Editar: para trabalhar com true floats, use o mapa para gerar um mapeamento de alto nível e, em seguida, consulte os dados originais para criar os 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
    
por 29.05.2014 / 04:39
fonte
2

Aqui está uma solução relativamente simples no Scala. Não deve ser muito difícil portar para outro idioma.

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

apply recebe em Set de todos os intervalos que já foram aplicados, localiza as sobreposições e retorna um novo conjunto menos as sobreposições e mais o novo intervalo e os novos intervalos de divisão. foldLeft repetidamente chama apply com cada intervalo de entrada.

    
por 29.05.2014 / 19:52
fonte
0

Mantenha apenas um conjunto de intervalos ordenados por início. Adicione um intervalo que cubra tudo (-oo .. + oo). Para adicionar um intervalo 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
    
por 29.05.2014 / 06:59
fonte