Algorytm spłaszczania nakładających się zakresów

16

Szukam dobrego sposobu spłaszczenia (podzielenia) listy potencjalnie nakładających się zakresów liczbowych. Problem jest bardzo podobny do pytania: Najszybszy sposób podziału nakładających się zakresów dat i wielu innych.

Jednak zakresy to nie tylko liczby całkowite i szukam porządnego algorytmu, który można łatwo zaimplementować w Javascript lub Python itp.

Przykładowe dane: Przykładowe dane

Przykładowe rozwiązanie: wprowadź opis zdjęcia tutaj

Przepraszam, jeśli to duplikat, ale jeszcze nie znalazłem rozwiązania.

Jollywatt
źródło
Jak ustalić, że zielony jest na górze niebieskiego, ale pod żółtym i pomarańczowym? Czy zakresy kolorów są stosowane w kolejności? W takim przypadku algorytm wydaje się oczywisty; po prostu ... erm, zastosuj zakresy kolorów w kolejności.
Robert Harvey
1
Tak, są one stosowane w kolejności. Ale to jest problem - jak „zastosować” zakresy?
Jollywatt
1
Czy często dodajesz / usuwasz kolory, czy też musisz zoptymalizować szybkość zapytań? Ile „zakresów” zwykle będziesz miał? 3? 3000?
Telastyn
Nie będzie zbyt często dodawać / usuwać kolorów, i będzie między 10-20 zakresami, z dokładnością ponad 4 cyfr. Dlatego metoda zestawu nie jest całkiem odpowiednia, ponieważ zestawy będą musiały mieć ponad 1000 elementów. Metoda, którą zastosowałem, jest tą, którą opublikowałem w Pythonie.
Jollywatt

Odpowiedzi:

10

Chodź od lewej do prawej, używając stosu, aby śledzić, w jakim kolorze jesteś. Zamiast dyskretnej mapy użyj punktów 10 w zbiorze danych jako punktów przerwania.

Zaczynając od pustego stosu i ustawiając startna 0, zapętlaj aż do końca:

  • Jeśli stos jest pusty:
    • Poszukaj pierwszego koloru, zaczynając od lub po start, i wepchnij go i wszystkie kolory z niższej rangi na stos. Na spłaszczonej liście zaznacz początek tego koloru.
  • else (jeśli nie pusty):
    • Znajdź następny punkt początkowy dla dowolnego wyższego koloru w lub później starti znajdź koniec bieżącego koloru
      • Jeśli następny kolor zaczyna się jako pierwszy, wepchnij go i cokolwiek innego w drodze do niego na stos. Zaktualizuj koniec bieżącego koloru jako początek tego i dodaj początek tego koloru do spłaszczonej listy.
      • Jeśli nie ma, a bieżący kolor kończy się jako pierwszy, ustaw startkoniec tego koloru, zdejmij go ze stosu i sprawdź kolor o najwyższej pozycji w rankingu
        • Jeśli startjest w zakresie następnego koloru, dodaj ten kolor do spłaszczonej listy, zaczynając od start.
        • Jeśli stos się opróżni, po prostu kontynuuj pętlę (wróć do pierwszego punktu wypunktowania).

Oto mentalny przegląd danych przykładowych:

# 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.
Izkata
źródło
co rozumiesz przez „cokolwiek innego w drodze do stosu”?
Guillaume07
1
@ Guillaume07 Dowolna ranga między bieżącym a wybranym następnym startem. Przykładowe dane tego nie pokazują, ale wyobraź sobie, że żółty został przesunięty, aby zaczął się przed zielonym - musisz wepchnąć zarówno zielony, jak i żółty na stos, aby kiedy żółty koniec się skończył, koniec zieleni wciąż znajdował się we właściwym miejscu na stosie więc nadal pojawia się w wyniku końcowym
Izkata
Kolejna myśl, której nie rozumiem, to powód, dla którego najpierw mówisz „Jeśli stos jest pusty: poszukaj pierwszego koloru rozpoczynającego się na początku lub przed nim”, a następnie w przykładzie kodu komentujesz „# Stos jest pusty. Poszukaj następnego punkt początkowy od 0 lub później ”. Tak więc, gdy będzie wcześniej, a później
Guillaume07
1
@ Guillaume07 Tak, literówka, poprawna wersja jest dwa razy w bloku kodu (drugi to komentarz w dolnej części, który zaczyna się od „Stos jest pusty”). Zredagowałem ten punktor.
Izkata
3

To rozwiązanie wydaje się najprostsze. (Lub przynajmniej najłatwiejszy do uchwycenia)

Potrzebna jest tylko funkcja odejmowania dwóch zakresów. Innymi słowy, coś, co da to:

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

Co jest dość proste. Następnie możesz po prostu iterować przez każdy z zakresów, zaczynając od najniższego, i dla każdego z nich odejmować po kolei wszystkie zakresy nad nim. I masz to.


Oto implementacja odejmera zakresu w Pythonie:

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

Korzystając z tej funkcji, resztę można wykonać w następujący sposób: („zakres” oznacza zakres, ponieważ „zakres” jest słowem kluczowym 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

To daje [['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]]], co jest poprawne.

Jollywatt
źródło
Twoje wyniki na końcu nie odpowiadają oczekiwanym
wynikom
@Izkata Gosh, byłem nieostrożny. To musiało być wyjście z innego testu. Naprawiono teraz, dzięki
Jollywatt,
2

Jeśli dane są naprawdę podobne do danych przykładowych, możesz utworzyć mapę w następujący sposób:

map = [0 .. 150]

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

Następnie wystarczy przejść przez tę mapę, aby wygenerować zakresy

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

Aby działać, wartości muszą znajdować się w stosunkowo małym zakresie, tak jak w przykładowych danych.

Edycja: aby pracować z prawdziwymi liczbami zmiennoprzecinkowymi, użyj mapy do wygenerowania mapowania wysokiego poziomu, a następnie odwołaj się do oryginalnych danych, aby utworzyć granice.

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
Gort the Robot
źródło
To bardzo miłe rozwiązanie, już się z nim spotkałem. Jednak szukam bardziej ogólnego rozwiązania, które może zarządzać dowolnymi dowolnymi zakresami zmiennoprzecinkowymi ... (nie byłoby to najlepsze w przypadku czegoś takiego jak 563.807 - 770.100)
Jollywatt
1
Myślę, że można to uogólnić, zaokrąglając wartości i generując mapę, ale zaznaczając lokalizację na krawędziach jako mającą dwa kolory. Następnie, gdy zobaczysz lokalizację z dwoma kolorami, wróć do oryginalnych danych, aby określić granicę.
Gort the Robot
2

Oto stosunkowo proste rozwiązanie w Scali. Przeniesienie do innego języka nie powinno być trudne.

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

applypobiera Setwszystkie zakresy, które zostały już zastosowane, odnajduje nakładki, a następnie zwraca nowy zestaw minus nakładki oraz nowy zakres i nowo podzielone zakresy. foldLeftwielokrotnie wywołuje applyprzy każdym zakresie wejściowym.

Karl Bielefeldt
źródło
0

Po prostu zachowaj zestaw zakresów posortowany według początku. Dodaj zakres obejmujący wszystko (-oo .. + oo). Aby dodać zakres 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
Kevin Cline
źródło