Aire de polygones

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Je viens aujourd'hui avec un problème qui parait trivial, mais qui me bloque depuis une grosse heure.

J'ai un ensemble de points, et pour chaque point, j'ai trois autres points auquels il est relié. Le résultat est un ensemble de polygones concaves. Le résultat me donne quelque chose similaire à ça.

Maintenant, j'aimerais pouvoir calculer l'air de chacun de ces polygones. Mon problème vient du fait que je ne sais pas quels points vont en former un ensemble.

Une suggestion d'algorithme ?

Merci

Auteur du sujet

Oui, bien sûr, mais pour ça il faut que je connaisse mon polygone. Le problème, c'est que je ne le connais pas ici. J'avais pensé à essayer de les créer en regardant les angles, en prenant toujours le plus petit angle par exemple, pour toujours "tourner à droite" jusqu'à atteindre mon point d'origine, mais je ne suis pas sûr de tous les trouver comme ça.

Staff

Cette réponse a aidé l'auteur du sujet

Mon problème vient du fait que je ne sais pas quels points vont en former un ensemble.

J'espère ne pas être à côté de la plaque, mais j'ai une idée. Tu considères ton ensemble de point comme un graphe (non orienté) et tu cherches les induced cycles (ou holes). Ce sont en gros des cycles qui vont paver ton graphe, sans contenir de cycles plus petits. Ça manque un peu d'info sur Wikipédia, mais apparemment tu peux les trouver avec un algo en n+m2 (n sommets, m arrêtes). Par contre, j'ai pas trouvé ni son nom, ni de réf.

EDIT: Trouvé.

Édité par Aabu

+3 -0
Auteur du sujet

Merci pour la réponse, du coup j'ai lu un peu sur le sujet. Ce que je cherche, c'est en effet des "induced cycles", mais tous ces "induced cycles" ne sont pas ce que je cherche.

Sur la figure 2 de cet article, qui en représente 3, seul l'un d'entre-eux est ce que je veux. Les autres on un sommet ou plusieurs à l'intérieur (bien qu'ils soient "induced").

Cette réponse a aidé l'auteur du sujet

Oui, il faut forcément utiliser les positions des sommets.

Je pense que l'on peut faire avec un balayage des points de gauche vers la droite pour récupérer tous les polygones. L'idée est de maintenir une « frontière » (d'arêtes) derrière laquelle les polygones sont complétés, plus des arêtes de polygones en cours de construction. En fait pour simplifier on peut unifier les deux et dire que les arêtes des polygones en cours de construction sont en double dans la frontière.

Voici un dessin. Cela ne correspond pas à un balayage de gauche à droite, les nœuds n'étant pas traités dans le bon ordre, mais c'est juste pour illustrer (d'ailleurs je vois que je devrais avoir refermé un polygone en bas, tant pis, je pense qu'on comprend).

Frontière

À chaque fois que l'on ajoute un nœud, on balaye ses arêtes dans le sens trigonométrique. On ignore les arêtes liant à un nœud qui n'est pas dans la frontière (i.e. on ignore les arêtes pointant vers l'avant). Les nœuds entre deux arêtes dans l'ordre du balayage constituent un polygone avec le nœud en cours de traitement.

+2 -0
Auteur du sujet

Merci,

Donc, en faisant comme ça, on considère un sous-graphe, et à chaque fois qu'on ajoute un noeud, on lance l'algo pour vérifier si il y a un cycle induit ?

Mais ensuite, pour que ça continue à marcher, il va falloir enlever des points du sous-graphe. Par exemple, sur l'image, en ajoutant le noeud qui est presque au milieu, on va fermer deux cycles induits. On les prend en compte, on les enregiste, mais ensuite, il faut enlever 4 noeuds, pour maintenir une "frontière". Comment est-ce qu'on peut faire ça ?

Cette réponse a aidé l'auteur du sujet

On peut faire avec une liste chaînée contenant les nœuds dans la frontière. Il faut aussi associer à chaque nœud une éventuelle position (élément) dans la liste chaînée, ainsi on ne devra pas la reparcourir entièrement à chaque fois que l'on traite un nœud (il suffira de récupérer directement la position du nœud dans la liste chaînée pour savoir à partir d'où commence le polygone et d'où on doit enlever les nœuds).

Quand on doit enlever des nœuds de la frontière, on « coupe » et « recolle » la liste chaînée.

Édité par blo yhg

+1 -0

Cette réponse a aidé l'auteur du sujet

Tu peux tenter une segmentation et un monte-carlo dessus. L'avantage c'est que c'est facile à mettre en place, pas de formule explicite et donc ça s'adapte à toute autre configuration. Le désavantage c'est que ça converge en racine du nombre de points tirés.

EDIT: Un joli graphique en premiere page google pour 'segmentation image':

Avec cette image, il ne reste qu'a determiner la bounding box d'un ensemble de meme couleur, puis d'approximer son aire par une methode de rejet (le test d'appartenance portant sur la couleur du point tire).

L'avantage c'est que cela permet de traiter des choses qui ne sont pas des polygones mais des patatoides.

Édité par KFC

+2 -0

Cette réponse a aidé l'auteur du sujet

Au pire, on peut carrément compter les pixels de chaque région, non ?

Et puis finalement il y a beaucoup plus simple que ce que je disais si on veut faire sur le graphe.

Il suffit de trier les arêtes de chaque nœud dans l'ordre trigonométrique (ça nous fait une liste circulaire pour chaque nœud). Chaque polygone est obtenu en partant d'un nœud et d'une arête qui lui est liée. À chaque itération, on suit l'arête pour obtenir le prochain nœud. Pour obtenir la prochaine arête, on prend l'arête qui suit l'arête courante dans l'ordre trigonométrique, parmi les arêtes du nouveau nœud. On répète jusqu'à retomber sur le nœud de départ.

Pour obtenir chaque polygone une et une seule fois, on peut stocker pour chaque couple (nœud, arête) si on a déjà traité le polygone correspondant.

edit : en plus dans l'autre algo, il ne faut pas maintenir une frontière mais plutôt une liste de frontières qui feraient tout le tour des polygones déjà complétés (avec des arêtes en double éventuellement si l'intérieur est vide). Et on n'aurait même pas besoin de balayer de gauche à droite.

Édité par blo yhg

+1 -0
Auteur du sujet

J'avais pensé à le faire, mais le problème n'était pas tant l'unicité, qui peut être vérifiée, que l'exhaustivité.

Si on parcourt tous les noeud, et que pour chaque noeud, on considère les trois arrêtes, avant de ne considérer que la première dans le sens trigonomètrique, est-ce suffisant ? Sur un petit cas que j'ai regardé, ça a l'air de marcher, mais il y a peut-être des cas particuliers problèmatiques.

KFC, j'aime bien ta méthode aussi, vu que ça pourrait nous permettre de traiter nos images expérimentales pour lesquelles on n'a pas d'infos sur les noeuds et arrêtes (on était en train de considérer acheter un logiciel àplus de 3000€ pour le faire…). J'ai téléchargé ImageJ, qui semble pouvoir le faire. Je vais essayer un peu.

Merci à vous trois !

Si on parcourt tous les noeud, et que pour chaque noeud, on considère les trois arrêtes, avant de ne considérer que la première dans le sens trigonomètrique, est-ce suffisant ?

Je ne comprends pas ce que tu dis (« avant de ne considérer que la première » ?). Chaque polygone va être parcouru, puisqu'il contient une arête. On se place à l'intérieur du polygone, face à l'arête, et on prend le nœud de gauche. Avec ce couple (nœud, arête), le polygone est parcouru dans l'ordre anti-trigonométrique.

Édité par blo yhg

+0 -0
Auteur du sujet

Mais chaque arête appartient à deux polygones, du coup je voulais être sûr que la méthode permettait de voir les deux.

Mais le problème a été résolu en utilisant ImageJ, en suivant cet exemple. Pas aussi pratique qu'un petit algo, pas aussi élegant que n'aurait pu l'être la méthode de KFC, mais ça me donne des résultats satisfaisants, et surtout, ça ne va pas me prendre trop de temps.

Merci !

Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte