spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wenn mehrere Mengen den gleichen Knoten haben, der genau zwei Kanten aufweist, nimmst du die Menge mit der kleinsten Mächtigkeit und verwirfst alle anderen. Sollten sie weitere, derartige Knoten einschließen, musst du die natürlich für zukünftige, ähnliche Überprüfungen ignorieren.
Damit allein kannst du Bild B schon wieder lösen. Allgemein lösen wirst du damit aber nicht können, wenn eine Fläche etwa nur von Vertices eingeschlossen wird, die alle mehr als zwei Kanten haben. Um das zu machen, könntest du die Vertices und deren Kanten, von denen du schon weißt, dass die zu einem Knoten gehören, komplett ignorieren und die Anzahl der Kanten der Vertices, mit denen jene verbunden waren, entsprechend reduzieren.
Doch auch damit wirst du nicht jede Fläche jedes Graphen finden können. Der folgende würde zum Beispiel Probleme machen:

Um diesen Fall aufzubröseln, muss man eigentlich gar nicht so viel verändern. Die oben skizzierte Vorgehensweise lässt sich super durchführen, bis nur noch Vertices "interessant/bekannt" sind, die mehr als zwei Kanten haben. Haben wir einen solchen Fall wie in dieser Skizze hier, könntest du das Ergebnis protokollieren, wenn du je einen Vertex einfach mal ignorierst. Aus diesen ganzen Protokollen prüfst du dann wieder auf die minimalen Ergebnisse.
Vielleicht nochmal am Beispiel aus dem Bild:

Und damit sollte sich das eigentlich ganz gut erledigt haben, wenn ich mich jetzt nicht total vertan habe.
Das alles setzt natürlich deine Grundlage voraus und ist nur eine Lösung von potentiell sehr vielen. Persönlich würde ich das Problem ganz anders rangehen.

MfG
Check

Okay, da habe ich mich vertan. Nach so einer Prüfung ist man doch ziemlich unkonzentriert.
Vergiss das einfach, ist Nonsens. An sich suchst du nach den Connected Components eines Graphen, was sich mit einer einfachen Tiefensuche auch recht simpel lösen lassen sollte. Da mit Zyklen zu arbeiten fügt unnötige Komplexität hinzu.

MfG
Check

1) Du gehst alle Knoten (A) durch und für jeden Knoten:
1.0) Erstelle eine leere Liste (Z)
1.1) Suche den jeweils im Uhrzeigersinn nächstgelegenen erreichbaren Knoten (B) (bei welchem Winkel du für diese Suche beginnst ist hierbei total egal), der nicht schon in Liste (Z) ist:
1.2) Packe (B) in (Z)
1.3) Suche den nächsten Knoten Bz derart, dass der Winkel (im Uhrzeigersinn) zwischen der nächsten Kante und der vorherigen Kante minimal ist.
1.4) Packe (Bz) in (Z)
1.5) Gehe zu (Bz) und mache bei 1.3 weiter, bis du wieder beim Knoten (A) ankommst (B==A)
1.6) Packe alle so abgelaufenen Knoten (in Z) als Polygon (P) in eine Ergebnisliste (E)
1.7) Gehe zu 1.1 und mache beim nächsten Knoten in Uhrzeigersinn weiter
2) Sortiere alle Knoten (Z) aller Polygone (P) der Ergebnisliste (E) nach ihrer Nummer aufsteigend (1->4->2 = 1->2->4; 4->2->1 = 1->2->4), bzw. implementier eine equals/hash-Methode in dieser Art
3) Entferne alle dabei entstehenden Duplikate (also fliegt 4->2->1 weg) (mit einem Ergebnis-Set für Polygone und der richtigen equals/hash-Methode passiert das von allein)
Übrig bleiben alle kleinsten Zyklen, bzw. eben alle Polygon-Flächen.

tl;dr: Du gehst jeden Knoten durch und durchläufst ganz stupide *alle* an ihn angrenzenden Polygone durch Durchlaufen der Knoten im Uhrzeigersinn und entfernst hinterher Duplikate.

Statt zu 1.1 geht zu 1.0, ja Das hatte ich nachträglich eingefügt und dann wohl vergessen.
Der grüne Weg ist in der Tat interessant und ist nach dem Algo wirklich ein Ergebnis. Allerdings kannst du das rauswerfen, wenn du die Summe der tatsächlichen Innenwinkel (das, was als innen angenommen wurde) mit aufsummierst und mit dem vergleichst, was hätte als Innenwinkel rauskommen müssen (bei 3 Knoten 1*180, bei 4 Knoten 2*180, bei 5 Knoten 3*180 und so weiter). Ist das tatsächliche Ergebnis größer, ist es kein valides Polygon, sondern nimmt "die Welt außen rundrum" als Polygoninhalt an, was aber offensichtlich verkehrt ist.

Ich denke man könnte das auch mit einer Art veränderten A-Stern lösen ( passt nicht so ganz aber wird hoffentlich klar wie ich darauf komme):

Nodes sind deine Punkte, die eine Liste ihrer Nachbarn haben und eine weitere leere Liste, die Parent-Nodes speichern soll.



expandNode() fügt die nicht besuchten Nachbarn zu der OpenList hinzu, wenn dieser noch nicht Besucht ist( wie A-Stern, ohne Heuristik), und fügt den aktuellen Knoten als Parent hinzu.

und die Funktion PolygonFound liefert im Endeffekt eine Liste der Nodes zurück die ein Polygon bilden.
Hierzu wird geprüft, ob ein Node mehrere Parent-Nodes hat und wenn ja, befindet sich dort ein Polygon.

polygonFound() geht einfach die Parents durch bis es keine mehr gibt, "fügt" diese in das Polygon ein (hab es als Liste modelliert) und löscht auf dem weg dahin alle besuchten Parent-Nodes.

Allerdings ist das nur eine Idee, habe es kurz getestet, müsste aber größere Probleme modellieren um sicher zu gehen.

Das findet aber vermutlich entweder nicht alle Polygone oder aber es findet nicht nur die kleinesten Zyklen, sondern alle Zyklen.