Algorithmus um Formen durch Punkte darzustellen

[kuhlmaehn]

Hi! Ich bräuchte mal einen kleinen Anstoß, wie man am besten beliebige Formen - z.B. Schriften oder Bilder, also schwarz/weißes - durch Punkte darstellen kann.
Ich will also z.B. ein "B" durch 20 Punkte darstellen oder so. Diese sollen dann mit geraden Linien verbunden näherungsweise das "B" ergeben.
Das größte Problem was ich dabei sehe ist, dass in geraden Strecken nicht unnötige Punkte verschwendet werden und das Rundungen dafür mehr Punkte bekommen um am bestmöglichen rund zu wirken.
Außerdem ist ja danach auch nicht ganz klar, welche Punkte verbunden werden sollen und welche nicht.
Wie kann ich das am besten Lösen, bzw. wo/wie finde ich etwas zu diesem Thema?
Danke

 

[Matthias Reitinger]

Hallo,

meine spontane Idee wäre: über das Bild eine Kantendetektion (Sobel, Laplace, …) laufen lassen, in jedem Kantenpixel einen Punkt platzieren und mit allen Kantenpixeln in der Moore-Nachbarschaft verbinden. Anschließend verbundene Punkte, die grob auf einer Linie liegen, durch die zwei Endpunkte ersetzen. So lange wiederholen, bis die gewünschte Anzahl an Punkten erreicht ist.

Grüße, Matthias

 

[kuhlmaehn]

Danke, das erstellen der Punkte und Verbindungen müsste ich dann ja so hinkriegen. Ein Problem seh ich aber noch bei der Vereinfacherung der Formen bzw. beim reduzieren der Punkte. Das Zusammenlegen von Punkten "die grob auf einer Linie liegen" ist ja vielleicht etwas ungenau.
Ich hab mir gerade folgenden Algorithmus überlegt:

1. Entferne testweise jeden Punkt einmal und vergleiche das Polygon Vorher und Nachher.
2. Enfterne dann am Ende endgültig den Punkt, bei dem die kleinste Veränderung resultierte.
3. Mach das so lange, bis die gesuchte Punktzahl erreicht ist.

Da ja z.B. ein B aus drei Polygonen besteht (die "Haupthülle" und die beiden Ovale) würde ich dann denk ich ein Array von Punktlisten speichern oder so. Für das B dann ein Array mit drei Punktlisten.
Nur bin ich jetzt absolut Fraglos, wie man zwei Polygone vergleicht von denen man nur die Punkte hat!?

[Edit zum Algorithmus]
Dann könnte ich auch sagen, entferne Grundsätzlich alle Punkte bei den die Veränderung kleiner als x ist...

[Edit 2]
Ich hab mir gerade noch was überlegt, hoffentlich ist das nachvollziehbar...
Wenn ich einen Punkt entferne, mach ich ja, im kleinen Sinne betrachtet, immer ein Dreieck zu einer Linie. Daher muss ich doch nur den Flächeninhalt aller Dreiecke zwischen einem Punkt und seinem rechten und linken Nachbar vergleichen und dann den Punkt löschen, der das kleinste Dreieck aufspannt oder?
Ach und natürlich aufpassen, dass es durch ein Löschen nicht zu einer Linienüberschneidung kommt.
Hab ich hier was übersehen?

 

[kuhlmaehn]

Ich denk der Winkel macht dann doch mehr Sinn und daher würde ich jetzt einfach alle Winkel vergleichen. Im angehängten Beispiel würde dann warscheinlich der Punkt bei Winkel 3 entfernt werden.
Davor muss jedoch immer überprüft werden, ob es zu Überschneidungen kommt und ob sich die Orientierung geändert hat (Von im Uhrzeigersinn zu gegen den UZS z.B.).
Denkt ihr das funktioniert so?
Außerdem könnte ich einen Tipp gebrauchen, wie man die Überschneidungen erkennt.
(Ob sich die Orientierung geändert hat geht soweit ich mich erinnern kann mit der Punktdeterminante)
Danke