Pixel sortieren

[Pixel sortieren (Gast)]

Hallo,
ich habe eine Kette von ca. 1000 Pixeln (1000 x/y-Paare), von denen je 
zwei entweder seitlich oder diagonal miteinander verbunden sind, wie 
hier:

........
.1..45..
..23..6.
.....7..
........

Gibts da einen einfachen Algorithmus, die Pixel von einem zum anderen 
Ende durchzunummerieren, möglichst fertig in Matlab (zum Testen, wird 
später im Video-DSP implementiert)?

Mein Ansatz wäre, mit einem beliebigen Pixel anzufangen und sich in 
beiden Richtungen die Kette entlanghangeln, Aufwand O(N^2). Wäre 
zeitlich noch akzeptabel - gibts dafür eine Matlab-Funktion?

Evtl. gehts schneller als O(N^2), wenn z.B. abwechselnd nach x und y 
sortiert wird und dann jeweils Segmente gebildet werden, in denen 
entweder x oder y monoton steigt, aber ich sehe noch nicht, wie das im 
Detail implementiert werden könnte.

Seb

[Christoph Kessler (db1uq) (Gast)]

Also die Kurve bewegt sich wie der König im Schach, es gibt 8 erlaubte 
Züge, aber das Pixel von dem man kommt und seine beiden 
Nachbarpositionen sind tabu. Bleiben also 5 mögliche Nachbarpunkte, auf 
denen es weitergehen kann.

Um den richtigen zu ermitteln soll jetzt eine - möglicherweise 
vorsortierte - Tabelle nach diesen 5 x/y-Paaren durchsucht werden.

Habe ich die Aufgabe so richtig verstanden?

[arc (Gast)]

Wenn genügend Speicher zur Verfügung steht, könnte man das
in O(n) lösen:
Idee: Man erstellt ein Array mit der Größe des umschließenden Rechtecks
und kennzeichnet darin jeden Punkt aus der Eingangsliste (z.B. ptr/null 
oder als Index in die/das Eingangsliste/array).
Dann die Startposition suchen: Einfacher Durchlauf durch die 
Eingangsliste und den Punkt merken, für den gilt p.x = min({p.x}) und 
p.y = min({p.y}). Hat man den Startpunkt, kann man dann die jeweiligen 
Nachbarn überprüfen und den letzten Startpunkt löschen. Mit dem nächsten 
Punkt geht's dann weiter (nextInGrid)

Hat man weniger Speicher, erstellt man statt des Arrays eine Liste mit 
Listen (C++ z.B. mit STL: list<list<Point>>).

Pseudocode...

enumerate(points: list of point)
  // array mit Zeigern oder mit den Indizes der Eingabeliste
  grid: array[minX..maxX, minY..maxY] of ptr to point
  res: list of point

  // Punkte im Grid anordnen und 
  // T = n
  foreach p in points
    grid[p.x, p.y] = addr(p)
  
  // Startposition in der Liste mit Punkten suchen
  // kleinstes x und kleinstes y
  // T = n
  sx, sy = findStartPos(...)

  // eigentlicher Durchlauf 
  nextInGrid(sx, sy, grid, |points|)

nextInGrid(sx, sy, grid, remaining)
  // "gefundenen" Punkt speichern
  results.add(grid[sx, sy])
  remaining--;

  // rechter oder linker Nachbar 
  if grid[sx + 1, sy) not empty 
     nextInGrid(sx + 1, sy, grid, remaining)
  else if grid[sx - 1, sy] not empty
     nextInGrid(sx - 1, sy, grid, remaining)
  else if grid[sx + 1, sy + 1] not empty 
     nextGrid(sx + 1, sy + 1, array, count);
  else 
     // die restlichen Nachbarn 
     if grid[sx + 1, sy - 1] not empty
        nextGrid(sx + 1, sy - 1, array, count)
     else if (array[sx - 1, sy + 1] not empty
        nextGrid(sx - 1, sy + 1, array, count)
     else if (array[sx - 1, sy - 1] not empty
        nextGrid(sx - 1, sy - 1, array, count)
   

"Speicheroptimierte"-Variante O(n) = n log n
enum2(points: list of point) 
  grid: list of list of point

  // Liste(n) aufbauen T ~ n log n 
  foreach p in points
    // Suche ob schon eine Liste für die X-Koordinate vorhanden ist
    pos = binarySearch(grid, p.x) 
    if pos in grid
       // Punkt in die Teilliste einfügen
       grid[p.x].add(p)
    else 
       // neue Teilliste erzeugen
       grid.insert(p, pos) 
      
   // Startposition T ~ n
   sx, sy = findStartPos(...)
   // Durchlauf
   nextInGrid2(...)

nextInGrid2(sx, sy, grid, remaining)
  results.add(grid[sx][sy])
  // Punkt aus der Liste bzw. Teilliste entfernen
  grid.remove(sx, sy)
  remaining--;

  // die einfache Überprüfung wird hier durch eine Binärsuche ersetzt
  // linker Nachbar 
  // X-Position 
  posX = binarySearch(grid, p.x - 1)
  // Y in der passenden Teilliste suchen, falls diese existiert
  if posX != -1
     posY = binarySearch(grid[p.x], p.y)
     if posY != -1 
        nextInGrid2(posX, posY, grid, remaining) 
  end
  // und die restlichen Nachbarn überprüfen

[Sebastian (Gast)]

>in O(n) lösen:
>Idee: Man erstellt ein Array mit der Größe des umschließenden Rechtecks

Jaja. Rechteck hat O(N^2) Pixel. Guter Vorschlag.
Nächster Vorschlag?

[arc (Gast)]

Dann entweder die zweite Lösung oder man implementiert eine etwas 
aufwendigere Planesweep/Scanline-Lösung

[Christoph Kessler (db1uq) (Gast)]

x und y-Koordinaten in einer Zahl zusammenfassen, z.B. y höherwertiger 
Teil.
Diese 1000 Zahlen aufsteigend sortieren. Mit sukzessiver Approximation 
mit je 10 Vergleichen können die 5 Nachbarpixel in der Tabelle gesucht 
werden, einer der 5 muß enthalten sein, der Rest nicht. Also ist im 
Schnitt nach 25 Vergleichen der Nachbarpunkt gefunden.

[Detlef _. (detlef_a)]

Ja, Punkte sortieren geht mit O(n*log(n)) und in der Tabelle suchen mit 
O(log(n)), müßte doch eigentlich insgesamt mit O(n*log(n)) gehen, oder 
nich?

Cheers
Detlef