algorithme pour obtenir toutes les différentes zones d'une figure

Question

Comme entrée nous n'avons un ensemble de segments, voici un exemple:

[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)] 

(désolé je fait de mon mieux, mais mes images sont un peu floue)

J'ai besoin de trouver toutes les zones individuelles. De la figure ci-dessus j'aurais 3 zones différentes, JKL, CEFG et {ABCD, JKL}:

Notez que les segments qui ne font pas de zone sont ignorés (tels que [HI]), et une zone ne peut pas être divisé par un segment, par exemple:

je pouvais le faire facilement avec un code spaghetti qui serait tout à fait unefficient, mais avant de le faire, avez-vous une idée de un algorithme sur lequel je peux commencer à travailler? Je cherche quelque chose d'aussi efficace que possible ...

Answer 1

Idée: Essayer de créer les anneaux les plus petits à partir des nœuds les moins connectés. Réduire la taille du problème au fur et à mesure.

1. Supprimer tous les nœuds avec un seul segment car ils ne peuvent faire partie d'aucune zone.
2. Trier les noeuds dans l'ordre croissant après nombre de segments (vous voulez un O (n log log n) ou moins algorithme)
3. Sélectionnez le nœud avec le plus petit nombre de segments
4. flood fill le long des segments jusqu'à ce qu'une cible potentielle est déjà rempli (ne vont pas en arrière)
5. ... (il pourrait y avoir 2 anneaux en plus complétés ici)
6. de profit en supprimant 2 nœuds de segments qui sont connectés au noeud sélectionné
7. mise à jour les segments de nœuds restants.

ToDo: si le moins noeud connecté est 3 ou plus ...