SW-Bild in Wege umrechnen.

[Yooda]

Servus,

ich sitze diesmal an einer für mich aktuell recht kniffligen Herausforderung.
Folgendes:

Ich möchte gerne ein Bild einlesen und dann die jeweils zusammenhängenden Pixel in Teilstrecken umwandeln. Dabei gilt, dass die Teilstrecken lediglich eine Richtung haben dürfen und Abzweigungen verboten sind.
Zusätzlich gilt, dass das Bild nicht Zeilenweise bearbeitet werden darf, da diese ermittelten Wege im späteren Verlauf die Befehle für eine x-y-z Fräse verwendet werden müssen.
Als Beispiel habe ich mal Paint angeschmissen, um es zu verdeutlichen:

Ich hoffe, dass die Grafik selbsterklärend ist

Wie kann ich am besten Vorgehen, damit ich am Ende quasi nur noch die Einzelstrecken habe? (Es geht mir dabei nicht um die Koordinaten).


Viele Grüße

David

 

[theHacker]

Klingt schwer nach NP-vollständig

Ich würde mich quasi immer "an der Mauer" entlang tasten. Guck, ob die Felder rechts/links (da nur eine Richtung erlaubt is, entscheidest du dich einfach für eine) noch belegt sind, also quasi die Grenze zwischen grün und weiß suchen. In dieser Richtung vortasten.
Natürlich musst du dir immer merken, was du schon im Pfad hast und diese grünen Felder als weiß markieren, sodass du sie nicht wieder anfässt.

Interessant wären dann noch die Fragen:

• Wie finde ich den Anfang? - beliebig? oder vielleicht von den Ecken des Koordinatensystems nach innen tasten?
• Was tu ich, wenn ich in einer Sackgasse stecke? Geht quasi Richtung Pathfinding, um noch möglichst viel vom Weg zu holen, ohne was auszulassen.
• Heuristik? Ist etwas über die Figur bekannt, die abgesucht werden muss?

 

[Yooda]

• Wie finde ich den Anfang? - beliebig? oder vielleicht von den Ecken des Koordinatensystems nach innen tasten?
• Was tu ich, wenn ich in einer Sackgasse stecke? Geht quasi Richtung Pathfinding, um noch möglichst viel vom Weg zu holen, ohne was auszulassen.
• Heuristik? Ist etwas über die Figur bekannt, die abgesucht werden muss?

Ich habe mir folgendes überlegt:

Den Anfangspunkt definiert das erste gefundene schwarze Pixel

Wenn ich in einer Sackgasse stecke, drücke ich die Paniktaste
Ne, Scherz beiseite

Um Pathfinding werde ich wohl kaum herum kommen, da diese Situationen i.d.R. immer vorkommen werden.

Die Figuren werden eben ja durch diese Bilder definiert. Da ich nicht weiß, was eingespeist wird, muss ich eben solch einen allgemeingültigen Algorythmus dazu entwickeln. Vermutlich auch mit vielen "Ausnameregeln".