Algorithmus alle einzelnen Bereiche von einer Figur zu bekommen

Question

Als Eingangs wir hier nur eine Reihe von Segmenten haben, ist ein Beispiel:

[AB] = [(0, 0), (0, 4)] ; [BC] = [(0, 4), (2, 6)] 

[CD] = [(2, 6), (4, 0)] ; [DA] = [(4, 0), (0, 0)] 

[CE] = [(2, 6), (5, 6)] ; [EF] = [(5, 6), (5, 3)] 

[FG] = [(5, 3), (3, 3)] ; [HI] = [(2, 1), (4, 5)] 

[JK] = [(1, 3), (2, 3)] ; [KL] = [(2, 3), (1, 1)] 

[LJ] = [(1, 1), (1, 3)] 

(sorry ich mein Bestes versucht, aber meine Bilder sind ein bisschen unscharf)

ich brauche alle einzelnen Bereiche zu finden. Bei der obigen Abbildung i 3 verschiedenen Bereichen haben würde, JKL, CEFG und {ABCD, JKL}:

Beachten Sie, dass Segmente, die keinen Bereich machen, werden ignoriert (wie [HALLO]), und ein Bereich, kann nicht von einem Segment aufgeteilt werden, zum Beispiel:

ich es leicht mit einigem Spaghetti-Code tun könnte, die völlig uneffizient sein würden, aber bevor es zu tun, haben Sie eine Vorstellung davon, ein Algorithmus, mit dem ich anfangen kann? Ich suche nach etwas so effizient wie möglich ...

Answer 1

Idee: Versuchen, die kleinsten Ringe von den am wenigsten verbundenen Knoten zu erstellen. Verringern Sie die Problemgröße, wie wir gehen.

1. Entfernen Sie alle Knoten mit nur einem Segment, da sie nicht Teil eines Bereichs sein können.
2. sortieren die Knoten in aufsteigender Reihenfolge nach der Anzahl der Segmente (Sie ein O wollen (n n) oder weniger Algorithmus log log) mit den wenigsten Segmente
3. flood fill entlang Segmente
4. Wählen Sie den Knoten, bis ein potenzielles Ziel ist bereits gefüllt (gehe nicht rückwärts)
5. ... (es 2 plus Ringe hier abgeschlossen sein könnte)
6. Gewinn von 2 Segmentknoten zu entfernen, die
7. Update die verbleibenden Knoten Segmente an den ausgewählten Knoten verbunden sind.

ToDo: was ist, wenn die am wenigsten verbunden Knoten 3 oder höher ist ...