Discussion :

[Mucho]

Salut salut,

je vous explique le problème :
connaissant des segments reliés entre eux je me demandais comment trouver les polygones formés par ces segments.
Mais les polygones de taille minimum, exemple (mal dessiné, désolé ):



par exemple ici j'aimerais trouver les deux polygones presque rectangulaires en haut à gauche du dessin mais pas le polygone qui est l'union des deux.

et donc je me demandais quel algorithme utilisé de manière a ce que ce soit efficace.

(si je ne suis pas clair dites le moi, j'essaierai d'autres explications)

[LfS]

Ton image ne s'affiche pas chez moi, mais si j'ai bien compris ce que tu expliques, je crois que tu devrais chercher du côté de la triangulation de Delaunay...
Ca te donne le maillage le plus fin possible (en général unique je crois) qui relie tous les points d'un nuage (donc ici tes extrémités de segment).

[ToTo13]

Bonjour,

je vois deux solution à ton problème :

- La premère qui me semble la mieux (mais pas forcément la plus simple) est d'utiliser l'algorithme de HOUGH afin de trouver toutes tes droites. Tu obtient ainsi toutes les droites contenues dans ton image et donc tu peux alors retrouver toutes les formes polygonales qui s'y trouve et donc les comparer.

- Le deuxième, puisqu'il s'agit d'une image, est de compter le nombre de parties blanches, comme si c'était des objets. En résumé, tu comptes les objets blancs et non les lignes. Tu en obtient ainsi leur périmètre et l'aire et donc le nombre de cotés.

Bon courage...

[diogene]

Une suggestion, peut être :
Tu prends un point à l'intérieur de ta figure. Tu dois trouver le plus petit polygone dans lequel il se trouve. Pour trouver ce plus petit polygone, il faut peut être s'inspirer des algo de remplissage de zones.
Tu as alors trouvé l'un de tes polygones. Tu l'enlèves de la figure (ou tu le marques comme traité) et tu recommences jusqu'à ce que ta figure soit vide.

[Sivrît]

connaissant des segments reliés entre eux

Je me demande s'il ne faudrait pas préciser la nature du problème. Pour moi Mucho a déjà les segments, bref il travaille sur un graphe. Mais la discussion part sur le traitement d'une image. Ki k'a bon ?

[Mucho]

Désolé je me suis absenté un moment.

Et effectivement, comme dit M. Sivrît, je connais déjà les segments et chaque point est unique
(j'entend par la que pour une ligne brisée [AB] [BC], les points B du premier et deuxième segment est la même instance de donnée.

Tu obtient ainsi toutes les droites contenues dans ton image et donc tu peux alors retrouver toutes les formes polygonales qui s'y trouve et donc les comparer

Je me demandais juste si quelqu'un avait trouvé un algorithme super malin pour trouver les polygones le plus rapidement possible.

[Sivrît]

Bon, j'ai cogité dans le RER. Je ne sais pas si c'est super malin mais bon.

On peut déjà remarquer que chaque segment appartient à deux polygones, sauf ceux des bords extérieurs pour lesquels c'est un. De même, un noeud à la croisée de N segments est un sommet de N polygones sauf sur les bords où c'est N-1 (je suppose qu'aucun segment n'est une 'impasse', cad qu'un noeud a au moins deux segments).

On va constituer des listes de noeuds qui correspondent à des boucles. Le but est qu'à la fin chaque liste soit un polygone minimal. On va compter le nombre de listes auquelles les noeuds appartiennent ; Quand c'est égal au nombre de segments liés pour tous les noeuds on a fini.

En initialisation on crée une liste correspondant au pourtour du graphe (ce n'est pas trop difficile) et on compte 2 pour chacun de ses noeuds (donc si un noeud appartient à seulement deux segments on en a fini avec lui). On va ensuite subdiviser ce polygonus maximus encore et encore.

Tant que l'on a des noeuds à traiter:
-On prend un de ces noeuds appartenant déjà à l'une des boucles.
-A partir de lui on suit des segments encore non utilisés (il faudra donc marquer ceux étant déjà dans une boucle) et ne menant pas à un noeud déjà visité pour ce chemin pour ne pas tourner en rond
-Quand on trouve un autre noeud appartenant à une boucle, on coupe cette dernière en deux avec le chemin suivi. On obtient deux boucles. Les noeuds de début et de fin ont leur compteurs augmentés de 1, les noeuds intermédiaires sont mis à 2.


Par contre je m'apperçois qu'il faut identifier la boucle que l'on divise en deux car les noeuds de départ et d'arrivée peuvent avoir plus d'une boucle en commun. Il faut déterminer à l'intérieur de laquelle est situé notre chemin... et c'est pas trivial. Zut !

[Sivrît]

Autre idée, partir sur le principe l'algo de dijkstra puisque l'on a une distance de définie.

[Mucho]

Merci M. Sivrît !

C'est cool, j'avais eu une idée assez similaire à la tienne et elles ont l'air de bien se complétées.
Dès que j'ai le temps de faire progresser mon petit algorithme comment il marche au final.

Et encore merci !

[Mucho]

Finalement je parcours les segments que je connais en tournant a chaque fois a gauche.
A chaque boucle formée, qui est minimale je décompte leur compteur de 1 (celui ci est initialisé à 1 ou 2 suivant le nombre de polygones auxquels ils appartiennent potentiellement).

Lorsqu'un compteur d'un segment atteint 0, je le retire du problème.

Lorsqu'il n'y a plus de segment, il n'y a plus de problème