Forme qui englobe nuages de points 2D [Résolu]

[Geadupr]

bonjour à tous,

je viens vers vous car je sèche complet sur le problème suivant :


j'ai 4 nuages de points 2D dont le nombre de points est propre à chaque nuage. chaque nuage est localisé aléatoirement :



ce que je cherche à faire, c'est tracer la figure à quatre côtés qui englobe parfaitement tous les nuages de points (forme blanche sur l'image). les segments doivent être sur des points ! donc pas d'approximation possible.

pour chaque point, je dispose de ses coordonnées x et y, ainsi que l'index de son nuage de point.


si vous avez une idée... ?

merci

[FR119492]

Salut!
Voici une méthode simple, mais je ne sais pas ci c'est la plus efficace:

Tu commences par définir un quadrilatère dont les sommets sont les "premiers" points de chaque couleur.

Ensuite, tu parcours la liste des points rouges du deuxième au dernier. Si un point est à l'intérieur du quadrilatère, tu l'ignores. S'il est à l'extérieur, tu agrandis le quadrilatère en conséquence.

Pour finir, tu recommences avec les 3 autres couleurs.

Jean-Marc Blanc

[plegat]

Envoyé par FR119492

Salut!
Ensuite, tu parcours la liste des points rouges du deuxième au dernier. Si un point est à l'intérieur du quadrilatère, tu l'ignores. S'il est à l'extérieur, tu agrandis le quadrilatère en conséquence.

+1

En rajoutant que tu reparcours ta liste de points depuis le début si tu agrandis le quadrilatère, car rien ne dis que tu ne sortes pas un point précédent interne en bougeant un côté... et en faisant attention de ne pas bloquer sur une boucle infinie.

[Geadupr]

effectivement avec une boucle répétable ça devrait le faire, au bout d'un moment l'unique solution devrait être trouvée.

j'avais oublié de préciser que le sens des nuages (ou couleurs) est toujours le même, toujours rouge-jaune-vert-bleu dans le sens des aiguilles d'une montre.

je peux donc le séparer en deux triangles pour effectuer les calculs sans risquer de croisements.

merci pour vos réponses, je vais essayer et je vous tiens au courant

[math_lab]

Je pense que tu peux ignorer le fait que c'est un quadrilatère et simplement trouver des droites pour chaque couple de couleurs (et passant par un de leurs points) qui ont tous les points du même coté. Après, tu as juste a trouver les intersections de tes droites pour faire ton quad.

[Graffito]

Pour moi, le problème se décompose en 2 parties :

• trouver le polygone convexe qui englobe tous les points. C'est un sujet maintes fois abordé sur le forum et il existe une importante litterature à ce sujet sur le web (exemple : http://www-sop.inria.fr/geometrica/c...convexe-od.pdf)
• trouver le plus petit quadralitère englobant l'envellope, c'est-à-dire réduire le nombre de points de l'envellope.

Pour le deuxième algorithme, je ne connais pas de méthodologie particulière. Mais, il me semble qu'on peut pratiquer ainsi:

1. pour chaque coté Pn::n+1 du polygone, on peut calculer l'aire du petit triangle compris entre le coté et l'intersection In des droites passant par Pn-1::n+1 et Pn+1::n+2. Si le triangle est "du mauvais coté", l'aire est "infinie".
2. on supprime le coté générant la plus petite surface en remplaçant Pn et Pn+1 par In.
3. on itère 1) et 2) jusqu'à ce qu'il n'y ait plus que 4 points.

[Geadupr]

hé bien voila ça marche

la première méthode avec le quadrilatère qui s’agrandit au fur et à mesure fonctionne mais peut être lourde selon les cas car on peut réitérer plusieurs fois.

finalement c'est la méthode proposée par math_lab qui fonctionne très bien.

en fait les calculs sont les mêmes que la première méthode, sauf que l'approche est plus directe c'est une simplification de la première méthode en somme.

merci à tous pour votre aide

[Dut]

Pourquoi ne pas déterminer les équations des 4 droites qui forment le polygone ?

En prenant :

1. le point rouge qui a la plus petite abscisse et le point bleu qui a la plus petite abscisse
2. le point bleu qui a la plus petite ordonnée et le point vert qui a la plus petite ordonnée
3. le point vert qui a la plus grande abscisse et le point jaune qui a la plus grande abscisse
4. le point jaune qui a la plus grande ordonnée et le point rouge qui a la plus grande ordonnée

Les 4 sommets sont calculés par l'intersection des droites.

Ou alors j'ai raté quelque chose ?

[souviron34]

Il y a encore plus simple :

il n'y a pas besoin des équations des droites. Les 4 points suffisent...

[magelan]

Bonjour,

Envoyé par Dut

Pourquoi ne pas déterminer les équations des 4 droites qui forment le polygone ?

En prenant :

1. le point rouge qui a la plus petite abscisse et le point bleu qui a la plus petite abscisse
2. le point bleu qui a la plus petite ordonnée et le point vert qui a la plus petite ordonnée
3. le point vert qui a la plus grande abscisse et le point jaune qui a la plus grande abscisse
4. le point jaune qui a la plus grande ordonnée et le point rouge qui a la plus grande ordonnée

Les 4 sommets sont calculés par l'intersection des droites.

Ou alors j'ai raté quelque chose ?

Cette méthode en garantit pas que les points se trouvent tous à l'intérieur du quadrilatère. Un exemple pour la droite rouge/jaune (plus grande ordonnée):

Ici l'un des point sort du quadrilatère.

[Dut]

Envoyé par magelan

Cette méthode en garantit pas que les points se trouvent tous à l'intérieur du quadrilatère.

J'avais donc bien raté quelque chose


Sinon une autre idée (vu la configuration proposée dans le premier message) :

1. générer l'enveloppe convexe du domaine
2. ne conserver de cette enveloppe que les 4 segments de plus grande longueur
3. calculer les intersections

[Graffito]

ne conserver de cette enveloppe que les 4 segments de plus grande longueur

Excellente astuce dans le cas présent pour réduire le nombre de points de l'envellope convexe.

[Geadupr]

en effet c'est plus compliqué qu'il n'y parait, les deux premières méthodes ont l'avantage d'être sans surprises.

Graffito et Dut : l'enveloppe convexe pourrait peut-être fonctionner, à voir avec la suite du programme, car pour l'instant j'ai vraiment besoin que chaque segment soit sur deux couleurs, et comme un point jaune peut être plus près d'un point rouge que des autres points jaunes, le résultat pourrait ne pas convenir.

la méthode de math_lab reste rapide en calcul et convient à mon utilisation.