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
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?
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...
1 | enumerate(points: list of point) |
2 | // array mit Zeigern oder mit den Indizes der Eingabeliste
|
3 | grid: array[minX..maxX, minY..maxY] of ptr to point |
4 | res: list of point |
5 | |
6 | // Punkte im Grid anordnen und
|
7 | // T = n
|
8 | foreach p in points |
9 | grid[p.x, p.y] = addr(p) |
10 | |
11 | // Startposition in der Liste mit Punkten suchen
|
12 | // kleinstes x und kleinstes y
|
13 | // T = n
|
14 | sx, sy = findStartPos(...) |
15 | |
16 | // eigentlicher Durchlauf
|
17 | nextInGrid(sx, sy, grid, |points|) |
18 | |
19 | nextInGrid(sx, sy, grid, remaining) |
20 | // "gefundenen" Punkt speichern
|
21 | results.add(grid[sx, sy]) |
22 | remaining--; |
23 | |
24 | // rechter oder linker Nachbar
|
25 | if grid[sx + 1, sy) not empty |
26 | nextInGrid(sx + 1, sy, grid, remaining) |
27 | else if grid[sx - 1, sy] not empty |
28 | nextInGrid(sx - 1, sy, grid, remaining) |
29 | else if grid[sx + 1, sy + 1] not empty |
30 | nextGrid(sx + 1, sy + 1, array, count); |
31 | else
|
32 | // die restlichen Nachbarn
|
33 | if grid[sx + 1, sy - 1] not empty |
34 | nextGrid(sx + 1, sy - 1, array, count) |
35 | else if (array[sx - 1, sy + 1] not empty |
36 | nextGrid(sx - 1, sy + 1, array, count) |
37 | else if (array[sx - 1, sy - 1] not empty |
38 | nextGrid(sx - 1, sy - 1, array, count) |
39 | |
40 | |
41 | "Speicheroptimierte"-Variante O(n) = n log n |
42 | enum2(points: list of point) |
43 | grid: list of list of point |
44 | |
45 | // Liste(n) aufbauen T ~ n log n
|
46 | foreach p in points |
47 | // Suche ob schon eine Liste für die X-Koordinate vorhanden ist
|
48 | pos = binarySearch(grid, p.x) |
49 | if pos in grid |
50 | // Punkt in die Teilliste einfügen
|
51 | grid[p.x].add(p) |
52 | else
|
53 | // neue Teilliste erzeugen
|
54 | grid.insert(p, pos) |
55 | |
56 | // Startposition T ~ n
|
57 | sx, sy = findStartPos(...) |
58 | // Durchlauf
|
59 | nextInGrid2(...) |
60 | |
61 | nextInGrid2(sx, sy, grid, remaining) |
62 | results.add(grid[sx][sy]) |
63 | // Punkt aus der Liste bzw. Teilliste entfernen
|
64 | grid.remove(sx, sy) |
65 | remaining--; |
66 | |
67 | // die einfache Überprüfung wird hier durch eine Binärsuche ersetzt
|
68 | // linker Nachbar
|
69 | // X-Position
|
70 | posX = binarySearch(grid, p.x - 1) |
71 | // Y in der passenden Teilliste suchen, falls diese existiert
|
72 | if posX != -1 |
73 | posY = binarySearch(grid[p.x], p.y) |
74 | if posY != -1 |
75 | nextInGrid2(posX, posY, grid, remaining) |
76 | end
|
77 | // und die restlichen Nachbarn überprüfen
|
>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?
Dann entweder die zweite Lösung oder man implementiert eine etwas aufwendigere Planesweep/Scanline-Lösung
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.
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.