Discussion :

[SandyF]

Salut à tous je suis à la recherche d'un algorithme permettant de déterminer les polygones contenus dans un plan, connaissant toutes les lignes qu'il contient.
Je m'explique: Sur un plan comme test2 ou test3 ci-dessous représentant des bâtiments, je voudrais faire ressortir la liste de toutes les pièces qui s'y trouvent sachant que j'ai à ma disposition la liste de tous les murs (droites) et qu'une pièce pourrait comporter plus de 4 murs(pentagone, hexagone).

Merci de votre aide

[Graffito]

Peut-être une solution ainsi:

1. si les extrémités des segments sont approximatives, il faut effectuer une correction pour que les points soient biens confondus,
2. pour chaque segment , tester si il a des intersections communes avec d'autres segments (en dehors des ectrémités) : si c'est le cas, scinder le segment en 2 parties,
3. supprimer les segments de longueur nullle et les doublons,
4. supprimer les murs dont une (ou les 2) extémités n'appartiennent à aucun autre segment,
5. chercher l'extrémité A du segment la plus au nord (si il y en a plusieurs sur la même horizontale prendre le point le plus à l'ouest sur cette horizontale),
6. Mettons une origine fictive O, un peu à l'est de A
7. chercher parmi l'ensemble des vecteurs AX, le vecteur AB qui maximise l'angle OAX,
8. ajouter AB au contour et l'éliminer de la liste des segments,
9. idem avec les vecteurs BX en testant le max de l'angle ABX pour trouver C (ajouter BC au contour et l'éliminer de la liste des segments),
10. itérer l'opération 9) jusqu'à retomber sur A
11. supprimer tous les segments dont les 2 extrémités se trouvent dans le contour [ABC...A] précédement trouvé
12. si il reste des segments non traités, alors on a alors un batiment isolé et on recommence l'ensemble du traitement à partir de l'étape 5)

Kolossale erreur! tu ne recherches pas le contour! mais les pièces
à priori, on peut utiliser un algo semblable :

1. en prenant O à l'ouest de A et le min de l'angle au lieu du Max et en n'éliminant pas les segments dans le calcul d'une pièce,
2. une fois trouvée la piéce, il va falloir supprimer les segments de la pièce qui appartiennent au contour (hé!hé! il faut quand même le calculer au traitement de chaque pièce)

[pseudocode]

Salut à tous je suis à la recherche d'un algorithme permettant de déterminer les polygones contenus dans un plan, connaissant toutes les lignes qu'il contient.

Tes données d'entrée sont des images (bitmap) ou alors des listes de segments (géométrie) ?

Dans le premier cas on peut utiliser les techniques de segmentation. Dans le deuxième on peut faire de l'exploration de graphe.

[SandyF]

Tes données d'entrée sont des images (bitmap) ou alors des listes de segments (géométrie) ?

Dans le premier cas on peut utiliser les techniques de segmentation. Dans le deuxième on peut faire de l'exploration de graphe.

Mes données d'entrée sont des listes de segments donc je pencherais plutot pour l'exploration de graphes.
N'ayant pas vraiment travaillé sur les graphes, pourrais-je avoir d'amples précisions sur l'algo d'exploration de graphes à utiliser?

[pseudocode]

Mes données d'entrée sont des listes de segments donc je pencherais plutot pour l'exploration de graphes.
N'ayant pas vraiment travaillé sur les graphes, pourrais-je avoir d'amples précisions sur l'algo d'exploration de graphes à utiliser?

L'exploration en elle même n'est pas le plus dur. C'est plutôt la construction du graphe qui est compliquée. L'utilisation des "quadedge" devrait résoudre ton problème.

[SandyF]

ça fait dejà beaucoup de questions, mais au fait ça représente quoi les "quadedge" en question? Je trouve rien de consistant dessus

[pseudocode]

ça fait dejà beaucoup de questions, mais au fait ça représente quoi les "quadedge" en question? Je trouve rien de consistant dessus

hum... c'est facile a comprendre mais dur à expliquer . Cherche des papiers sur la triangulation de Delaunay, on y parle des quadedges.

En gros on pourrait dire que c'est une structure qui modélise à la fois un segment [A,B] et les deux demi-plan (Gauche/Droite) qu'il sépare.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
      (G)
       |
 A ----+---> B
       |
      (D)

En assemblant plusieurs quadedges bout à bout, on peut former des polygones. Les règles d'assemblage impliquent de "fusionner" (ou "séparer") les demi-plans.

Par exemple dans un triangle (3 quadeges), les 3 demi-plans intérieurs sont fusionnés, et les 3 demi-plans exterieurs aussi => l'assemblage final modélise deux surfaces distinctes : 1 intérieur et 1 exterieur.