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:listofpoint)
2
// array mit Zeigern oder mit den Indizes der Eingabeliste
3
grid:array[minX..maxX,minY..maxY]ofptrtopoint
4
res:listofpoint
5
6
// Punkte im Grid anordnen und
7
// T = n
8
foreachpinpoints
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
ifgrid[sx+1,sy)notempty
26
nextInGrid(sx+1,sy,grid,remaining)
27
elseifgrid[sx-1,sy]notempty
28
nextInGrid(sx-1,sy,grid,remaining)
29
elseifgrid[sx+1,sy+1]notempty
30
nextGrid(sx+1,sy+1,array,count);
31
else
32
// die restlichen Nachbarn
33
ifgrid[sx+1,sy-1]notempty
34
nextGrid(sx+1,sy-1,array,count)
35
elseif(array[sx-1,sy+1]notempty
36
nextGrid(sx-1,sy+1,array,count)
37
elseif(array[sx-1,sy-1]notempty
38
nextGrid(sx-1,sy-1,array,count)
39
40
41
"Speicheroptimierte"-VarianteO(n)=nlogn
42
enum2(points:listofpoint)
43
grid:listoflistofpoint
44
45
// Liste(n) aufbauen T ~ n log n
46
foreachpinpoints
47
// Suche ob schon eine Liste für die X-Koordinate vorhanden ist
48
pos=binarySearch(grid,p.x)
49
ifposingrid
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
>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?
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
