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 :

[edfed]

bein, apparement, c'est bien un truc comme je propose qu'il faudrai, mais cette fois si avec un indice de qualité, du genre gauss.

ça fait des années que j'essaye de comprendre le fonctionement de l'oeil humain, et de la vision en general.

l'indice de qualité serai utilisé pour determiner a partir de quelle distance on considere les points comme etant non adjacents, car meme dans un systeme de bitmap, ou ecran de pc, les pixels apparaissent comme collés les uns aux autres, mais pourraient tres bien etre espacés de plusieurs millimetres.

[ToTo13]

Bonjour,

essayons de nous mettre d'accord :
- tu veux l'enveloppe convexe de ton nuage de points ?
- tu connais déjà les points de contours et tu ne souhaites garder QUE les points qui sont à l'extérieur ?
- tu veux une enveloppe non convexe. Auquel cas elle n'est pas unique, voir même il y a un très grand nombre (pas une infinité, mais...) de solutions.

[Graffito]

determiner a partir de quelle distance les points sont adjacents

C'est bien un des aspect influera totalement sur la solution:
Doit-on considérer un point de l'ensemble comme parfaitement défini ou comme une probabilité de distribution autour de sa position?
Dans ce dernier cas, on pourra associer à tous point du plan une probabilité: ce n'est plus vraiment le même problème.

[pseudocode]

@souviron: ta technique de tracé ressemble enormément au snake. D'ailleurs je suppose que c'est ce que le PO cherche a faire. En fait, cette discussion a des similitudes avec celle concernant le calcul du contour de polygone à une distance fixe.

[souviron34]

ben ça ressemble , mais ça ne l'est pas pour des raisons de fond je pense...

Dans le cas a distance fixe, tu as déjà le polygone, et en fait tu le "zoomes" plus ou moins (avec le fait que les angles aigus peuvent se supprimer et les obtus nécessitent 3 points pour être vraiment à distance fixe).

Dans ce cas là, tu as juste le nuage de points.

Disons que ça a l'apparence de se comporter de manière ressemblante à un snake.. Sauf que le problème de fond est : trouver un algo qui élimine des points intérieurs ET garde une forme "réaliste". Et tu n'as AUCUNE quantité autre que la position, et elle est spatialement discrète (il y a eu éclair ou non). Donc pas de calculs de dérivée possible, pas "d'énergie" ou de quantité à mesurer ou évaluer,pas de possibilité de faire une matrice (voir explication plus bas). Visiblement avec l'exemple de gauche, l'enveloppe convexe ne convient pas. Il faut donc trouver la "vraie".

Comme je dis plus bas, c'est l'algo du GiftWrapping qui m'a donné la solution...

Tu fais l'enveloppe convexe, puis tu balances le rayon (la distance entre 2 sommets) vers l'intérieur. Le premier point que tu rencontres , tu regardes l'angle que ça donne à partir de ce point vers les 2 sommets. Si l'angle est OK, on garde le point. et on itère (mais en passant aux 2 sommets suivants, pour ne pas engendrer de "préférences"). On rajoutera donc éventuellement 1 point entre 2 sommets adjacents à chaque passe à travers l'ensemble..



@Graffito : sur ta remarque sur l'adjacence.

Dans le cas que je présente, il y a AU DEPART effectivement un paramètre de distance d'adjacence, mais ce n'est pas pour le calcul du polygone, mais pour la séparation en "taches" ou "cellules", donc rien à voir avec l'algo dont on parle.

Après, l'algo est intrinsèque. Une fois les points pris en compte déterminés avec la distance, on a un problème de géométrie pure...

Je me suis cassé les dents 2 ans sur ce truc, donc j'ai quand même réfléchi un peu.. En fait, c'est l'exemple du nuage de points de la méthode du GiftWrapping du bouquin de Sedgewick qui a fini par me donner la solution.

Contrairement à une image, il n'y a pas de "résolution", on ne peut pas (dans l'absolu on pourrait, mais dans mon cas je ne pouvais certainement pas) faire une matrice (carte = amérique du nord, distance mini entre les points = 1m, d'où une matrice 6 Millions * 6 Millions )

Ce ne sont pas des probas. Tu sais PARFAITEMENT que les points sont là (d'où d'ailleurs les angles dans l'enveloppe complexe, car il FAUT passer par les points extrêmes..) : il y a eu un éclair ou pas.... proba 100% là ou il y un point, 0% ailleurs.. Ce n'est pas une modélisation, mais une observation. Et d'ailleurs c'est le BUT de cet algo : déterminer l'enveloppe, PUIS modéliser pour obtenir des probas... pour prévoir..

NOTE : et si tu compares l'image originale et les résultats, tu vois quand même que la dernière ou avant-dernière image du bas correspond pas mal à ce que tu "découpes" ou identifies à l'oeil sur la première....

[edfed]

dans le cas de points eloignés, et nombreux, la recherche de points "adjacents" d'apres un facteur de qualité, permettrai de connaitre l'enveloppe de l'image.

car c'est bien une image. meme si elle fait 6G*6G pixels.

donc, il ne s'agit pas de mathematiques pures a base de formules, mais d'algorythmes de recherche, scrutation.

prenons un point.

un facteur de qualité de 100 pixels, ça voudrait dire que si un point est present dans cet intervale, alors il est considéré comme adjacent.
les points deviennent alors des cercles de rayon Q ( qualité)
si les cercles secoupent, ils ont adjacents.

la creation d'une ligne rejoingnant deux points permetrait alors d'obenir l'enveloppe.
a savoir que si deux points sont considéré adjacents et en bordure, ils seront connectés par une ligne.

je me penche sur ce probleme pour creer une fonte bitmap zoomable, un algo qui relie automatiquement les points avec des lignes quand on zoome

le probleme n'a pas l'air si compliqué.

si c'est bien payé, je veu bien me pencher sur l'algorythme en ASM

[souviron34]

d'autant plus que comme visiblement tu ne vois pas les implications de ce que tu dis, ça va être super utile comme prog....

et pour ta gouverne :

a) si c'est un problème de géométrie pure. UNE MANIERE de le présenter serait de le mettre en image, MAIS ce n'est pas le problème.

b) algorithme s'ecrit avec un I .. c'est pas de la musique...

c) Si le problème est pas si compliqué, comment se fait-il qu'il n'existe aucun algo connu ?? Ah c'est vrai j'oubliais.. On t'attendait ....

d) tu n'es pas le PO... Que d'ailleurs on n'entend plus

e) et de plus ta conclusion est fausse (suffit de regarder les images données plus haut)

la recherche de points "adjacents" d'apres un facteur de qualité, permettrai de connaitre l'enveloppe de l'image.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
*
 *******
 
  *** ******
 
  **     * * * * **
***             ****************
*    * *** *** **     *****
 
***             ********
  *******  ****
    *****************
   ****
            *****

les points **** sont adjacents et NE SONT PAS DANS l'ENVELOPPE (et pourtant "qualité" max : distance minimale)

[edfed]

desfois, la solution est simple, il suffit d'y penser

par exemple, pour trouver un mot dans un texte, certains disent qu'il faut se casser la tete pendant des heures, puis, hop, je lui ai pondu un code simple en moins de 10 minutes sans le tester. et s'etait fonctionnel, car je l'ai testé un peu plus tard, et ça fonctionnait.

donc, au risque de vous froisser, je peu vous affirmer que la solution est plus simple qu'il n'y parait.

[Jean-Marc.Bourguet]

Une possibilite -- qu'il me semble avoir deja suggeree dans ce forum -- est de calculer la triangulation de Delaunay sur l'ensemble de points, ensuite remplacer les segments externes par les deux autres cotes du triangle correspondant suivant un critere ou l'autre (angle interne du triangle superieur a 90 degres me semble un bon critere sur les quelques dessins que j'ai fait) et iterer jusqu'a convergence en faisant attention a ne pas avoir des points relies simplement par un segment. Pour tenir compte de cette possibilite et avoir ce qui me semble etre intuitivement le meilleur choix, plutot que de remplacer n'importe quel segment admissible, choisir celui qui a l'angle interne le plus grand.

[pseudocode]

+1 avec Jean-Marc.Bourguet.

Je vous conseille d'ailleurs la lecture de ce papier:

http://www.greyc.ensicaen.fr/~jfadil...PRL2004.pdf.gz

[khayyam90]

Ce problème est très intéressant mais son caractère permissif sur "l'acceptabilité des solutions" le rend très piégeant.

J'avais travaillé sur un problème proche, il s'agissait de déterminer un tissu urbain aussi précis que possible à partir d'images satellites. Cependant la limite de ce tissu devait se conformer à la taille des objets observés (routes principalement). Nous avions à extraire une enveloppe à partir d'un nuage de points. Les réflexions ont été menées principalement sur une étude statistique des densités de points avec des fenêtres de différentes tailles, de manière à extraire tout d'abord les grandes formes du tissu puis en itérant d'affiner le tout. Le nombre d'itérations était fonction des objets que nous observions et de la finesse du résultat attendu.
Cette méthode avait l'énorme avantage de passer outre les problèmes de concavité.
Elle nécessitait cependant une densité à peu près constante des points sur les zones à extraire, ce qui était un critère très contraignant notamment la portabilité de la méthode à d'autres problèmes.

J'approuve l'idée de Jean-Marc (en fait dès qu'on parle de triangulation de Delaunay j'approuve) ). Une suppression de triangles ayant un côté plus grand qu'une limite fixée (ou un raisonnement sur les angles cf post précédent) permettent de progresser dans les concavités ou de créer des trous dans les maillages. Et l'approche est esthétique

[souviron34]

beeeppppp !!!!

mauvaise idee...

D'une part le temps de calcul avec quelques dizaines de milliers de points est gigantesque.(meme en incremental). D'autre part, et c'est le plus important, la triangulation ne marche bien que si des coordonnees ne sont pas alignees, et si il y a quand meme un minimum de semblant de "vide" autour de chaque point. Mais quand on a des agglomerats de points TRES proches , eventuellement superposes, eventuellement alignes, ca se passe plutot mal.. (divisions par zero, cercles circonscrits abherrants...)... J'ai essaye avec les exemples donnes ci-dessus (plus quelques autres, appli operationnelle oblige...)..

Mais c'est aussi TRES lourd en calcul, pour du temps reel avec 150 000 points, pas terrible..

La mienne est pas terrible non plus (iterative), mais environ 10 a 50 fois plus rapide (classement des points, et exploration "ordonnee", et boucle sur les indices et non sur les points eux-meme...)

@Jean-Marc : en fait, dans mon algo, la limite "humainement" acceptable est 60 degres je crois (j'ai plus l'algo sous les yeux). Mais quelque chose comme ca. donc 90 degres correspond a 25% de convexite avec mes criteres (entre 60 et 180).

En fait, ca marche vraiment bien : moins de 5% d'erreur sur la localisation EXACTE de la cellule orageuse grace a ce contour , projete ensuite 25 minutes plus tard.... Fonctionne en temps reel operationnellement depuis maintenant 8 ans...

Mais fondamentalement le principe est bien celui que vous decrivez, comme je l'ai ecrit plus haut (et esthetique ) :

On part du convexe, et on descend avec des angles (et nous arrivons tous a la meme conclusion : il y a une limite angulaire).

@kayyam90 : oui, mais dans ton cas d'une part tu avais une image (donc en fait des points regulierement repartis et adjacents), et d'une taille "raisonnable"...

Le probleme est : si l'on n'a PAS de resolution (pas de notion d'adjacence), on est dans le probleme geometrique pur. Donc effectivement on pourrait avoir Delaunay (avec les limitations imposees ci-dessus), mais on ne peut pas se baser sur des criteres de distance, ni de densite... En fait, nous avions commence a reflechir avec cette methode (celle qui est utilisee par les radars.. ) Mais les radars ont une matrice d'environ 200*200.... Quand on a voulu appliquer, et comme la resolution des equations de transformation geographique sont le metre, ont se rend compte d el'impossibilite d eproceder de cette facon... D'ou la reflexion....

[edfed]

un etre humain est apte a determiner l'enveloppe.