Aire de polygones

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+m² (n sommets, m arrêtes). Par contre, j'ai pas trouvé ni son nom, ni de réf.

EDIT: Trouvé.

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).

À 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.

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.

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.

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.