Discussion :

[Rastacouéne]

bonjour!

voila mon problème:
je dispose d'un tableau de Point de taille nbPts.
Ce tableau stock les points d'un polygone 2D sur un plan XZ
je cherche a pouvoir gardé que les points extérieurs au polygone, ceux qui vont former son enveloppe ( pour une représentation graphique apres mais la n'est pas le probleme)

je rajoute aussi que mes points ne sont pas triés^^

auriez vous des idées pour tester si un point se trouve dans l'eveloppe non convexe d'un polygone ou au contraire qu'il la compose?

merci,thanks,danke...

[Graffito]

tester si un point se trouve dans l'enveloppe non convexe d'un polygone ou au contraire qu'il la compose?

Impossible pour les points situés dans l'envellope convexe : le choix de l'enveloppe non convexe est forcément arbitraire.

Plus de détails ici:http://www.iag.asso.fr/articles/nuage.htm

[souviron34]

Graffito je ne serais pas aussi categorique.

Je l'ai fait..

En fait, pour le PO, explique de maniere la plus precise possible ton probleme.

Je t'expose en gros ce que j'avais fait :

Soit un nuage de points.

• Determiner l'enveloppe convexe.
• Entre 2 sommets de l'enveloppe convexe, faire tourner un rayon jusqu'a ce qu'il touche un point interne. Si angle trouve > a une certaine limite, prendre ce point, et iterer.

Evidemment, le point sensible est la limite

J'ai determine, avec des exemples physiques sur lesquels je travaillais, une limite "humaine", c'est a dire a peu pres ce que ferait l'oeil humain. Si on ne met pas de limite, on finira par obtenir l'algo du voyageur de commerce degrade : on passera par tous les points avec des angles horribles, ce qui n'est pas ce que fait notre oeil.

Ayant determine cette limite, je peux donc avoir un algo Calcule_Enveloppe avec un parametre (pourcentage) que j'ai appelle "Realite" ou "Humanite". 0% et l'enveloppe est convexe. 100% et l'enveloppe contient les points ou chaque angle est superieur ou egal a cette limite.

Si vous etes interesse, je peux detailler plus...

[edfed]

une bonne astuce consisterai a afficher les points du polygone en monochrome sur fond noir
ensuite, tester pour chaque points s'il est dans ou au au bord
au bord, il y aurai au moins un point noir a ses cotés, et un bitmap sera créé dans une autre partie de la memoire. ce bitmap ne montrera que les points de la peripherie.

bon, ça bouffe pas mal de temps de calcul, mais c'est simple et ça fonctionne

[Graffito]

Graffito je ne serais pas aussi categorique.

Sur le plan théorique, on malheuresement obligé de l'être.

Soit les 5 points:

Code :

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

1
2
3
4
5
A          B
 
      O
 
D         C

Il y a le choix entre de multiples enveloppes non convexes, comme par exemple AOBCD, ABCD,...
Et il est impossible de dire si O appartient à l'envellope.

J'ai même le sentiment qu'il existe toujours une envelloppe non convexe passant par un des points du nuage.

[edfed]

ha, c'est pour calculer l'envellope d'un polygone vide
bein, dans ce cas, il n'y a rien a faire, vu que les points decrivent l'enveloppe

[souviron34]

Sur le plan théorique, on malheuresement obligé de l'être.

Sans doute.. Cependant nous sommes ici sur un site informatique, et, à moins que je me trompe lourdement, notre ami PO n'est pas un chercheur en mathématiques.

Son problème est donc concret. C'est la raison pour laquelle je lui demande des prrécisions.

Et j'en profite pour expliquer mon point de vue sur le "concret". Dans mon cas (enfin celui que je devais traiter ), les points sont les impacts de la foudre. Bien qu'irrégulièrement répartis dans l'espace et le temps, ils sont limités à la cellule orageuse concernée.

A l'observation, ils forment bien un ensemble cohérent, se déplaçant à la vitesse de l'orage. De même que le radar détermine une enveloppe en faisant des contours (la représentation des points du radar est une image, ce qui, de manière absolue, est faux, puisque les "pixels" ne sont pas totalement adjacents) , on peut de même déterminer l'enveloppe de l'orage par la position des éclairs..

Et la vision par l'oeil des impacts provoque une détermination par notre cerveau d'une "enveloppe". Donc, même si théoriquement il n'y a pas de solutions (je le sais, j'ai passé 2 années à essayer de chercher partout... ^^)
il peut y avoir une solution informatique "utilisable"..

Comme vous pouvez le voir ci-dessous, ça a quand même un intérêt non négligeable, en particulier quand on se retrouve dans le cas à gauche.. Mais aussi car ce qui est intéressant ce n'est pas les impacts, mais la zone...

Et on voit bien (de 100 % de convexité à 0% (qui correspond à ma limite "d'humanité")) que la dernière ou avant-dernière étape (25% ou 0%) est beaucoup plus "réelle" et "réaliste" et "ce que l'on ferait à l'oeil" que les convexes....

Voici ce que ça donne :