Polygon aus Kantenbild extrahieren

[Medium]

Mhh, generell ist da eine 4er Nachbarschaft deutlich besser geeignet, wenn nicht sogar nötig (ich erinner mich grad nicht). Man konnte auch irgendwie 8er in 4er überführen und umgekehrt, aber auch da hab ich gerade eine Sperre in den Synapsen :?. Es war zumindest nicht schwer!

Das Problem bei 8er ist ja:

Code:

Starte bei X, suche links herum, beginnend mit dem oberen möglichen Nachbarn:

0    | 1    | 2    | 3    | 4 
-----+------+------+------+------
   X |    - |    - |    - |    -
   O |    X |    - |    - |    -
OOOO | OOOO | OOXO | OO-X | OO--

-> Tracing Ende, Kontur unvollständig, da "falsch abgebogen"

Sowas kann dir bei 4er NBs nicht passieren.


Kreuzungen kannst du übrigens nicht überwinden, ohne wirklich aufwendig zu werden. Eine Kreuzung wird immer als Ecke erkannt werden, es sei denn, du prüfst zusätzlich die 2px Nachbarschaft mit ab, und schaffst Kriterien für Kreuzungen. Dabei musst du noch drauf achten, dass Pixel in denen sich was kreuzt mehr als nur ein Mal zugeordnet werden müssen, wenn die "andere" kreuzende Kontur nicht unterbrochen werden soll. Das stell ich mir arg fummelig vor!

[Nikolas]

Ich habe jetzt eine recht elegante Möglichkeit gefunden:

Man nehme einen Stack!
Auf den legt man ein Pixel aus dem Polygon und

-> nimm das oberste Objekt vom Stack und schaue ob du nahe am Ziel bist. (und dein Polygon schon mehr als 10 Punkte beinhaltet. )
Wenn ja, bist du fertig
ansonsten lege alle (8er) Nachbarn drauf, die auch zur Kontur gehören und noch nicht gesehen wurden.
goto (->)

Mein Problem bestand aus kleinen Anhängseln, die nur ein paar Pixel lang waren. Komme ich jetzt an eine Kreuzung, gehe ich einen Weg. Ist es die kurze Sackgasse, finde ich bald keine Nachbarn mehr und gehe zurück zum richtigen Weg. Damit habe ich dann einen kleinen Schlenker im Polygon, aber da nachher alles durch Fourier geglättet wird, kann mir das egal sein.
Gehe ich den richtigen Weg, wird mich der irgenwann ans Ziel führen, an dem ich dann meinen Stack verwerfe und so den falschen Weg nicht in meinem Polygon habe.

lineare Laufzeit, recht stabil und ziemlich einfach :)

Damit ist ein Problem gelöst, das nächste kommt sofort
Durchlaufrichtung eines Polygons bestimmen

[bernhard_LA]

ps : hier gib es einen algo zu diesem problem
http://cardhouse.com/computer/vector.htm