Des Rätsels Lösung

Hallo!

Also ich hab folgendes Problem: Ich möchte in einem Bild/Graphen/Matrix den höchsten, tiefsten, rechtesten und linkesten Punkt finden. Ich habs zuerst mit einem Floodfill-Algorithmus probiert, aber bei großen Bildern kommts schnell zu einem Stack-Overflow durch die vielen rekursiven Aufrufe. Noch dazu isses extrem langsam (funktioniert aber). Die Einschränkung ist, dass ich ganz links oben zum Suchen beginn (Im Bild im schwarzen Bereich) und mich dann nach rechts vorarbeite. Nachdem ich ganz rechts war, geh ich wieder nach links eine Zeile weiter unten. Das liegt daran, da meine Daten so im Speicher liegen und ich die Daten hintereinander und daher auch schneller abfragen/bearbeiten kann. Wenn ich aber einmal im grünen Bereich bin, dann kann ich mich dort beliebig fortbewegen. Jetzt ist die Frage, wie kann ich den höchsten, tiefsten, rechtesten und linkesten Pixel schnell finden? Die Betonung liegt auf schnell. Ich hab schon ein paar Ideen, die mir aber kompliziert scheinen, und daher frag ich mal nach, ob jemand eine bessere/einfachere Methode kennt. Es sollte Testweise auf unteren Graph funktionieren und im Notfall kann dieser ganz rechte Sonderfall übersehen werden, wenn man dadurch viel Zeit sparen kann. Solche Fälle kommen wahrscheinlich nicht so oft vor. Ich würd mich auf Vorschläge freuen.

[Blockierte Grafik: http://i17.photobucket.com/albums/b73/WuZweng/graph.gif]

Ja hab ich mir auch schon gedacht, jedoch ist es bei ca 10.000 - 50.000 Punkten in einem Graphen trotzdem sehr Zeitaufwändig. Ich hab schon eine Idee, wie ich das besser und schneller machen kann, trotzdem warte ich auf Vorschläge ab, falls es was besseres gibt. Danke trotzdem! =)

Hallo!

Danke für deine Anregungen! Folgendes:

Sagen wir es ist z.B.: eine 640*480 Matrix und es sind sehr viele solcher zusammenhängender Graphen in dieser Matrix. Ich brauch von allen die maxima. Somit kann ich nicht von links, recht, unten und oben kommen. Es liegt am Speicher, der Zeilenweiße linear im Speicher liegt. So wie ich nach dem ersten grünen Feld suche, ist sicher die schnellste.

Leider ist nicht bekannt, wie der Graph aussieht, sonst wär es leicht. Die einzige Möglichkeit das Problem zu lösen ist diese, sich IM Graph zu bewegen und so die Maxima finden. Die erste Idee war eben der Floodfill, aber wir kennen den Performanceverlust.. Das extreme ist, dass ein solcher Graph auch 20.000 Felder beinhalten kann, deswegen war die nächste Idee, dass ich mich nur am Rand bewege. Das war schon meine Idee, wie ich diesen Thread gestartet hab, aber ich wollte sehen welche Ideen da noch so kommen. Die Frage war nur, wie ich automatisch am Rand bleib. Meine Idee war folgende:

1.) Schau aufs Feld rechts neben dem aktuellen. Falls es im Graphen ist, dann schau wieviele Nachbarn dieses Feld hat. (Alle 8 Nachbarn). Falls dieses Feld weniger als 8 grüne Nachbarn hat, dann marschier dorthin. Das ganze solange ich nach rechts so gehen kann. Wenns nicht mehr geht, dann das gleiche mit nach unten gehen, nach links gehen und nach oben gehen.

2.) Das ganze funktioniert rekursiv ähnlich wie Floodfill, nur mit der Außnahme, dass ich Felder nicht betrete, die 8 grüne Nachbarn haben.


Somit bleib ich immer am Rand und spar mir die massigen Felder in der Mitte. Wenn ich durch die rekursiven Aufrufe wieder zum Anfang komme, ist es fertig. Jetzt hab ich mir gedacht, dass die 8 Nachbarn für jedes Feld eine große Anzahl von Vergleichen ist, deswegen wähl ich die 4er-Umgebung (oben, rechts, unten, links).

[Blockierte Grafik: http://i17.photobucket.com/albums/b73/WuZweng/Umgebung.gif]

Die Grafik zeigt die Nachbarn pro Feld für die verschiedenen Umgebungen. Das einzige was hier anders ist, ist dass es mehr 4er gibt als 8er in der 8er Umgebung (Im Graph, nicht in obiger Darstellung!). Es kommt aber aufs selbe, wenn ich trotzdem 4er betrete, aber keine 4er betrete, wenn ich schon auf einem 4er bin. Somit hab ich mir schon wieder einiges gesparrt. Die nächste Ersparniss ist, dass ich nicht alle Nachbarn anschauen muss.

1.) Von dem Feld wo ich komm, weiß ich dass es ein grüner Nachbar ist.
2.) Sobald ich einen Nachbar finde, der nicht grün ist, kann ich das Feld betreten.

Ja das waren meine Überlegungen. Vielleicht fällt jemandem noch was besseres ein. Ich würd mich freuen..

mfg

Wen es noch interessiert: Ich habs jetzt implementiert und es läuft im Schnitt auf große Flächen 10 mal so schnell wie der Floodfill-Algorithmus. Das interessante ist, dass der Algorithmus schneller ist, wenn ich alle 8 Umgebungspixel betrachte und abbreche, wenn eines davon nicht grün ist als wenn ich nur 4 Umgebungspixel betrachte.