retirer les points internes d'un polygone

Version imprimable

Voir 40 message(s) de cette discussion en une page

11/01/2008, 18h33
souviron34

Citation:

Envoyé par edfed

un etre humain est apte a determiner l'enveloppe.

D'ou la maniere de faire de l'algo... Prend une feuille, un papier, dessine un nuage de points, et ensuite essaye a la main de trouver en dessinant seulement la meilleure enveloppe..... :P
11/01/2008, 18h48
edfed

Citation:

Prend une feuille, un papier, dessine un nuage de points

je vien d'assayer et bizarrement, j'arrive pas a ecrire. peut etre que la cartouche d'encre de ma feuille est vide.

et puis la foudre elle tombe bien où elle veut

pour ce qui est de dessiner un contour de nuage de points, je continue a dire qu'un etre humain est la meilleure solution.
car effectivement, nous sommes munis de DSP video instantanés, un par oeuil.
donc, trouver le contour d'une forme bizarre n'est pas un probleme.

essaye tu vas voir.
si tes points sont peu nombreux, l'enveloppe correspond aux points en peripherie, idem s'ils sont nombreux.

ensuite, vu que c'est pour une analyse visuelle, une sorte d'ovberview, on s'en fiche eperduement de la precision au dixieme de millimètre.

essaye avec mon avatar pour voir, c'est pas un beau nuage de points?
11/01/2008, 21h15
souviron34

:alerte: Troll detected :alerte:

Citation:

Envoyé par edfed

ensuite, vu que c'est pour une analyse visuelle, une sorte d'ovberview, on s'en fiche eperduement de la precision au dixieme de millimètre.

C'est bien connu, on peut directement greffer le cerveau sur une puce electronique, sans douleurs et sans operations, pour qu'un logiciel fasse avec zero ligne de programme le boulot du cerveau :aie:
11/01/2008, 21h29
Jean-Marc.Bourguet

Citation:

Envoyé par souviron34

mauvaise idee...

Peut-être, je n'ai jamais travaillé sur le problème. Mais il y a quelques affirmations que tu fais qui m'étonnent.

Citation:

D'une part le temps de calcul avec quelques dizaines de milliers de points est gigantesque.(meme en incremental).

N log N n'est pas gigantesque chez moi.

Citation:

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

Il faut faire attention comme dans toute implémentation de computational geometry où en effet les explications simplifiées ont tendance à ignorer les cas limites et donc les implémentations trop hatives à ne pas être robustes, mais je ne vois pas de problème de fond. Tu peux être plus explicite?

Citation:

La mienne est pas terrible non plus (iterative), mais environ 10 a 50 fois plus rapide (classement des points,...

Donc on est a nouveau dans du N log N, non? (A moins que tu utilises du clustering pour éviter des comparaisons?) Note que je n'ai pas une idée des facteurs, mais j'ai l'impression que tu considères qu'il y a une différence plus forte que cela.

Citation:

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

Si je ne me trompe pas, 90 degré pour l'angle interne, ça peut se formuler aussi en disant que le point intérieur est dans le demi cercle ayant pour diamètre les deux points sur l'enveloppe. Et si on met le diagramme de Voronoi, ça veut dire que la cellule du sommet interne sort de l'autre côté du triangle. Plus aigu ça me semble vraiment dedans.

(Note que je ne tiens absolument pas compte que tu avais aussi un problème de clustering... une idée à explorer -- j'y ai encore moins réfléchi qu'au reste -- pour le clustering en se basant uniquement sur Delaunay serait de ne pas faire attention justement au cas où on dégénère en un segment et de couper les cluster à ces endroits).

voici juste l'entête d ela fonction, avec les explications... Je mettrais peut-être le code à un moment donné....

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
/*
 *  C o m p u t e C o m p l e x E n v e l o p e
 *
 * The basic algorithm has been complexified in order to speed up the computation
 * and to address the problem of few points in an elongated part, to split them
 * fairly amongst the sides. 
 * 
 *  The amount of time is :
 *        proportionnal to the number of points
 *        anti-proportional to the convexity from 100% to 50% and 
 *        and 2.25*anti-proportional to the convexity from 50% to 0%
 *        (0% convexity runs 4.5 times slower than 50%, which run 2 times slower than 100%)
 *
 *                                  *
 *
 *
 *
 *                             *
 *                        *
 *
 *                      100%  50%   0%
 *
 *
 *   The basic algorithm is :
 *
 *        * Computes the convex enveloppe (gift-wrapping algorithm)
 *        * Then explores in between each of the convex summits to find
 *          the farthest "inside" point with maximum view angle to the 
 *          2 adjacents summits. A threshold is set so that the contour
 *          will not go through all points, but only through points giving
 *          a certain "smoothness" in the contour.
 *        * Then explores between new formed summits the same way until no
 *          new summits can ne found. 
 *
 *   The main inconvenient of that algorithm is that, as points were ranked
 *   relative to their angle form the lower-right point in order to perform
 *   the gift-wrapping convex algorithm, we have to explore all the remaining
 *   points each time we want to find if a point lies in between 2 summits, as
 *   this ranking does not provide a clue as to whether a point lies within the
 *   geometrical limits of the segment. Furthermore, because of the concavity
 *   in some parts the angles of close points could be outside the range. 
 *
 *   Thus, in order to speed up the process, we derived a more complex algorithm
 *   which, despite being more complex, provides a sort of ranking improving a lot
 *   the exploration of remaining points. It uses the basic algorithm, but as the
 *   final stage of the computation. The basic algorithm is an addition-algorithm,
 *   the complexified is a deletion-algorithm.
 *
 *   Here is the process of this complexified but faster algorithm :
 *
 *        * First sort the points by their angle to the closest-to-center point
 *          (this should ensure that we have an enveloppe of the set of point,
 *           although going through all points)
 *        * Then place the lower-right point at the first rank of the array,
 *          keeping the same order. We thus have a contour going through all
 *          points but starting from the lower-right point.
 *        * Then finds the convex contour of points by storing the indexes of
 *          the convex summits, without re-arranging the points.
 *        * Then finds points whose viewpoint of the 2 adjacent summits is within
 *          the limits (this step is much faster than the one of the basic algorithm
 *          as we have to explore only the array of points between the indexes of the
 *          convex summits. Thus we store only the indexes of points in order not to
 *          re-arrange the points). At that stage we have a sensible complex contour, 
 *          but not completely satisfactory, as the shape of the whole polygon could 
 *          be elongated, and thus taking the angle from the center of mass could be 
 *          a bit wrong (it's the true contour at an almost 90% confidence level, but
 *          for very concave parts).
 *        * Then we re-arrange the points, storing all already found summits at the
 *          beginning of the array, and moving unkept points at the end.
 *        * Then we sort the remaining points by their distance to the lower-right
 *          point.
 *        * And now we can apply the central computation of the basic algorithm. 
 *          With the previous sorting we have a way of skipping and stopping the 
 *          exploration of the remaining points, thus speeding up a lot this phase.
 *          Another factor of speed up is also the fact that the previous stage was
 *          already almost complete, leaving anly a few iterations at that stage.
 *        * Finally we have to check for extremely thin strips, as the alogithm
 *          above tries to be fair between each summit, thus it can produce a point
 *          which belongs less to a (i,i+1) than to (i+1, i+2).
 *  
 *
 */
int MCore_ComputeComplexEnvelope ( MCore_GeoPt *Pts, int N_Pts, int EnvelopeType, MCore_GeoPt **NewPts )

Enveloppe_Type est le pourcentage codé de convexité (de 0 à 100).

12/01/2008, 17h24
souviron34

Citation:

Envoyé par Jean-Marc.Bourguet

Si je ne me trompe pas, 90 degré pour l'angle interne, ça peut se formuler aussi en disant que le point intérieur est dans le demi cercle ayant pour diamètre les deux points sur l'enveloppe. Et si on met le diagramme de Voronoi, ça veut dire que la cellule du sommet interne sort de l'autre côté du triangle. Plus aigu ça me semble vraiment dedans.

(Note que je ne tiens absolument pas compte que tu avais aussi un problème de clustering... une idée à explorer -- j'y ai encore moins réfléchi qu'au reste -- pour le clustering en se basant uniquement sur Delaunay serait de ne pas faire attention justement au cas où on dégénère en un segment et de couper les cluster à ces endroits).

le clustering était déjà fait à cette étape là..

Là on a juste les points d'UNE CELLLULE.

Et en fait en ce qui concerne Delaunay, c'est que comme il n'y a pas de manière "propre" pour arranger les points au départ, quand tu a splusieurs milliers ou dizaines de milliers de points à classer, d'abord tu as le temps passé et la mémoire utilisée pour créer les triangles, et d'autre part l'élimination et la sélection par les cercles ne se passent pas souvent très bien quand, comme je le disais, tu as des points alignés ou superposés.
Car de principe, une fois l'enveloppe convexe calculée, tu cherches quand même les points dans les cercles. Donc là, si d'un seul coup ton cercle est défini par 3 point alignés, :aie: .. Ou 2 points superposés :aie: . ou contient 200 points presque superposés :aie: Et du coup, il faut en plus rajouter le temps de vérification des conditions aux limites, qui au nombre s'avère, tout cumulé, beaucoup plus pénalisant... Et même en ayant enlevé ça, des points très très proches mais non superposés, et surtout en grande quantité, perturbent complètement le calcul (comment trouver le triangle le plus "équilatéral" quand tu en as 1000 ?)

En fait, Delaunay marche parfaitement pour une distribution de points irrégulièrement répartis, mais avec une "semi-répartition de densité quasi-constante" quand même (c'est d'ailleurs ce que j'avais pris pour les stations météo au sol). Mais pour un nuage du genre de ceux montrés en exemple, ça ne marche pas du tout...
13/01/2008, 12h27
Graffito

Citation:

Souviron34: 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..

Argument simpliste et fallacieux:aie::
- Les impacts des éclairs doivent être considérés dans l'espace temps (ils ne se produisent pas tous au même instant), or apparament tu as du faire un découpage du temps qui fait que dans l'espace à 3 dimension sol/temps, tu ne considères en fait pas des points.
- Si seuls les points "comptent" sans introduction de condition additionnelle, l'envellope non convexe n'a aucun sens dans l'absolu.
13/01/2008, 18h01
souviron34

Citation:

Envoyé par Graffito

Argument simpliste et fallacieux:aie::
- Les impacts des éclairs doivent être considérés dans l'espace temps (ils ne se produisent pas tous au même instant), or apparament tu as du faire un découpage du temps qui fait que dans l'espace à 3 dimension sol/temps, tu ne considères en fait pas des points.
- Si seuls les points "comptent" sans introduction de condition additionnelle, l'envellope non convexe n'a aucun sens dans l'absolu.

Le pas de temps dans lequel on considère les éclairs comme cohérents est défini par l'utilisateur :aie: (en général 10 minutes).

Je crois que tu ne comprends pas le fond du problème : considérons que 10 minutes = 1 seul instant t.

Tous les éclairs arrivés dans ces 10 minutes sont considérés de manière identique. On ne prend en compte (à ce stade-là) QUE leur position. Cette position est ponctuelle dans l'espace 3D (une latitude une longitude). L'hypothèse de base de l'algo est de NE PAS PRESUPPOSER une resolution sous-jacente (donc PAS de "pixellisation" possible).
Enfin, la NATURE etant ce qu'elle est, il suffit de regarder en l'air un jour de nuage pour s'apercevoir que les nuages ne sont pas convexes... :aie:

Ces points sont donc REPRESENTATIFS de la cellule.. le BUT est justement de modèliser la cellule afin de pouvoir effectuer une prévision. Mais pour pouvoir prédire, il faut avoir analyser. Et vu que nous ne disposons QUE des points, il faut donc en DEDUIRE la cellule, au plus proche de la REALITE (c'est la différence entre les maths et la physique... : on SAIT que cela représente une cellule, mais les MESURES sont discrètes. Il faut donc FAIRE AVEC , SANS hypothèse sous-jacente (donc pas de résolution de "découpage")). Ce n'est qu'une fois l'enveloppe trouvée que là on peut se donner une résolution et modéliser la cellule en la "pixellisant" et en donnant des valeurs de probas à chaque pixel).

Et par conséquent l'enveloppe NON convexe a un sens DANS l'ABSOLU car elle représente au plus près la REALITE PHYSIQUE. C'est l'enveloppe convexe qui n'a aucun sens physique, et donc aucun sens dans l'absolu.
13/01/2008, 20h45
Graffito

Citation:

Je crois que tu ne comprends pas le fond du problème : considérons que 10 minutes = 1 seul instant t.

et considérons que le point d'impact d'un éclair est un cercle de rayon 100 mètres ...

Citation:

et en donnant des valeurs de probas à chaque pixel

Serions nous d'accord sur ce point ?
Dans un message précédent, en réponse à la probabilité de distribution que j'évoquais, tu écrivais :

Citation:

proba 100% là ou il y un point, 0% ailleurs

PS : je ne remets pas en cause ta proposition d'algorithme, mais juste la formulation de la justification.
13/01/2008, 21h27
edfed

boh, la foudre elle tombe bien là ou elle veu...

une representation pixelisée ne serait pas si conne, car, de toute façon, c'est pixelisé.
il suffit de regarder les images jointes pour voir que ça l'est.

pour ne pas pixeliser, il faudrait faire un tramage d'unité 0.3mm , le pixel d'un moniteur normal.
je n'ose pas imaginer le nombre de disques durs necessaires au stockage de ces infos.

en plus, le but de cette manoeuvre est de determiner les zones de preference de la foudre, non?
ces zones couvrent des dixaines de Km.
la foudre tombe souvent au memes endroits d'une année sur l'autre (je ne l'ai pas lu dans un bouquin rebarbatif de mr tartanpion, docteur en sciences appliquées a la foudre, je le constate).

je pense que l'algoryhtme permettant de determiner ces zones existe depuis bien longtemps, mais il n'est pas fait que pour ça...

ça s'appelle flou gaussien + netteté + baguette magique.
14/01/2008, 04h18
souviron34

Citation:

Envoyé par Graffito

et considérons que le point d'impact d'un éclair est un cercle de rayon 100 mètres ...

:aie:

5 cms si tu veux...

Citation:

Envoyé par Graffito

Serions nous d'accord sur ce point ?

Dans un message précédent, en réponse à la probabilité de distribution que j'évoquais, tu écrivais :

Non nous ne sommes pas d'accord. Cette pixellisation s'effectue APRES la reconnaissance de l'enveloppe....

Etape 1 : identifier (clusteriser) les points par "cellule"
Etape 2 : trouver l'enveloppe de la cellule
[Etape 3 : la remplir de "pixels"
Etape 4 : affecter à chaque "pixel" ainsi défini une proba basée sur la densité réelle d'impacts/m2.
]
Etape 5 : prévoir une expansion/diminutuon de la cellule au cours du temps
[Etape 6 : prévoir la densité au cours du temps à l'intérieur de la cellule]

Les étapes 3, 4, et 6 sont liées. Les étapes 3 et 4 ne servent QUE pour l'étape 6.

Donc en ce qui concerne la MODELISATION de l'enveloppe ainsi que sa PREDICTION, PAS DE PIXELISATION....

Citation:

Envoyé par edfed

en plus, le but de cette manoeuvre est de determiner les zones de preference de la foudre, non?
ces zones couvrent des dixaines de Km.
la foudre tombe souvent au memes endroits d'une année sur l'autre (je ne l'ai pas lu dans un bouquin rebarbatif de mr tartanpion, docteur en sciences appliquées a la foudre, je le constate).

Allez, va jouer....

Non, le but de cette manoeuvre est d'évacuer des usines (explosifs, produits chimiques), de fermer des aéroports, d'avertir des sociétés de travaux publics de s'éloigner de la dynamite, de couper des lignes de courant THT avec assez d'avance pour que les usines puissent être évacuées, et pour éviter les dégats (arrêter à temps le remplissage des réservoirs d'un 747 par exemple), détourner le trafic aérien vers un autre aéroport, déclencher un vol de surveillance des pompiers aériens, etc etc... C'est du temps réel critique, c'est pas pour jouer à des statistiques...

Non seulement chaque seconde compte, mais en plus la fermeture "fausse" d'une usine ou d'un aéroport a des conséquences qui font que l'approximation convexe dont parle Graffito est TOTALEMENT non envisageable. Il faut être au plus près de la réalité pour ne faire évacuer et envoyer les alertes QUE quand c'est vraiment nécessaire...
14/01/2008, 11h00
pseudocode

Désolé d'intervenir dans votre rixe, mais je voudrais revenir sur l'algo de Souviron:

Citation:

Then finds points whose viewpoint of the 2 adjacent summits is within the limits.

At that stage we have a sensible complex contour, but not completely satisfactory, as the shape of the whole polygon could be elongated, and thus taking the angle from the center of mass could be a bit wrong (it's the true contour at an almost 90% confidence level, but for very concave parts).

Si j'ai bien compris (c'est pas gagné), tu construis d'abord l'enveloppe convexe puis tu "déformes" cette enveloppe en "enfonçant" les bords.

Tu ajoutes donc des nouveaux sommets à l'enveloppe entre les sommets d'origine. Le "entre" utilise une mesure d'angle depuis le centre de masse.

J'ai bon ?

absolument :D

Comme je l'ai expliqué plus haut..

En fait je pars du convexe et je rentre petit à petit..

Utiliser le centre de masse comme point de départ et non pas le point le plus en bas à droite par exemple (ce qui est pris pour le Gift Wrapping) permet d'avoir quelque chose de nettement plus convenable dans le cas présenté à gauche (une "banane").

Mais une fois une première étape passée, il faur revenir à quelque chose de plus "standard", pour avoir par exemple le plus correctement possible la partie la plus concave de la "banane". (les angles pris par rapport au centre de masse donnent ici (au plus creux, si ce creux est vers le centre) un classement ne correspondant pas à l'enveloppe...).

En fait les 2 manières ont leurs forces et faiblesses. Mais partir du GiftWrapping pour quelque chose comme la "banane" montrée ne donne pas de bons résultats pour détecter la courbure générale (les angles ne sont pas dans le bon ordre), et partir du centre de masse ne donne pas de bons résultats pour le centre pour la même raison. Il faut donc mixer les 2 méthodes : le centre pour commencer à avoir grossièrement la figure, un point extrême pour affiner le centre....

Et une fois tout terminé, il y a 2 possibilités de s'être fourvoyé dans le classement des points, pour les parties très fines et allongées :

comme on prend les sommets 2 à 2 classés suivant les angles, et qu'on explore ensuite entre ces sommets, on peut prendre un point comme "intérieur" au segment "i i+1" alors qu'il serait plus proche du segment "i+1 i+2" , et il peut du coup y avoir croisement.

Donc la terminaison de l'algo se fait en 2 passes :
Vérifier qu'il n'y a pas de croisements. Si il y en a, les corriger.
Code:

1 2 3 4 5 6 7 *6 *5 *3 *4 *2 *1
Avec l'algo normal, on rattachera 5 à 1-2, 3 à 2-4, et 4-6 croisera 1-5 (le dessin ici n'est pas exact, mais c'est l'idee).
Vérifier qu'un point dans une partie allongée est effectivement rattaché au segment le plus proche.
Code:

1 2 3 4 5 *5 *4 *3 *2 *1
si on suit l'algo normal, on explore d'abord entre les 2 points du bas (1 et 2).
On va trouver 3. Mais on voit bien que 3 est plus proche de 4-5 que de 1-2.
(avec en plus un angle plus large)
PS: je sais que j'aurais dû publier cet algo quelque part, mais comme je ne suis pas dans le monde universitaire, je n'ai trouvé aucun contact en maths pour me diriger vers une bonne publi (et pour IEEE il faut être membre pour soumettre). Si vous en avez, contactez-moi par MP ;)

14/01/2008, 14h50
edfed

j'ai lu quelque part que la methode des graphes pouvait etre utilisée pour des choses dans se genre.

le poid de chaque liaison est inversement proportionel à la distance avec l'autre point de la liaison.

par un traitement des liaisons du graphe, on peu donc obtenir le nombre minimal de liaisons necessaires à faire le contour.

pour la figure n°2, le resultat serait une etoile dont le centre est le segemnt 3-2
14/01/2008, 14h53
pseudocode

@souviron: Je crois que j'ai compris le principe général. Je nage encore un peu sur la 2eme partie de l'algo (un sorte de gift-wrapping localisé ?)

L'approche est quand meme un peu analogue au snake. On part d'une approximation (un cercle centré sur le centre de masse) et on deforme le contour en suivant des contraintes. Le probleme c'est que le snake ne donnera qu'une approximation du contour (en particulier le nombre et la positions des sommets).

Ton approche semble beaucoup plus efficace... si j'arrive a tout comprendre j'essaierai de l'implementer, a titre d'exercice. (geek un jour, geek toujours)

Citation:

Envoyé par edfed

par un traitement des liaisons du graphe, on peu donc obtenir le nombre minimal de liaisons necessaires à faire le contour.

Tu peux expliquer comment tu differencies un noeud de contour et un noeud interne ?
14/01/2008, 15h13
souviron34

Citation:

Envoyé par pseudocode

si j'arrive a tout comprendre j'essaierai de l'implementer, a titre d'exercice. (geek un jour, geek toujours)

si tu veux , si tu es intéressé, je peux t'envoyer le code par MP ou mail...

pour la 2ième partie, ce n'est pas le Gift Wrapping. C'est juste utiliser le même principe pour CLASSER les points entre 2 sommets...
14/01/2008, 15h30
edfed
je ne vois pas pourquoi on devrai differencier un noeud interne d'un noeud externe. mais pour ça, il existe des methodes.

je ne me suis pas encore penché sur la question des graphes en profondeur.
un noeud de contour est sur les bords
un noeud interne est cerné de points dans les 4 directions principales, N, O, E, S
par exemple,
Code:

1 2 3 4 5 6 *1 *2 *3 *4 *5 *6 *7 *8 *9 *10 *11
*7 est relié à *3,*4,*10 et *9
*8 est relié à *4,*2,*5,*11 et *10

chacun de ces noeuds fait partie du contour.

en parralelle au graphe, il faut faire un traitement spacial, tester les coordonées des points.
un point qui est à l'exterieur du contour à une direction au moins sans laison.
un noeud du contour, mais interne cette fois ci, à plusieurs points liées a lui dans une dirction données.

par exemple, *7 est un noeud interne car *9 et *10 sont tout les deux en dessous de lui, et que quelle que soit la direction, il y a un point relié a lui.

le point *2 est un noeud externe car il n'a rien au dessus de lui.

apres c'est une histoire de tests et de combinaisons possibles.

il y à 8 directions, possibles
nord, NO, ouest, SO, sud, SE, est, NE,... nord.

pour parler angles, 0, 45,90,135,180,225,270,315, et retour à 0
14/01/2008, 15h43
pseudocode

Citation:

Envoyé par souviron34

si tu veux , si tu es intéressé, je peux t'envoyer le code par MP ou mail...

Bah tu sais, moi le Fortran... :roll:

Je vais essayer de voir si on peut raffiner le snake final pour le "coller" au plus proche du nuage de points... c'est pas gagné. :aie:

Citation:

pour la 2ième partie, ce n'est pas le Gift Wrapping. C'est juste utiliser le même principe pour CLASSER les points entre 2 sommets...

Ah... je me disais bien que c'etait curieux aussi: aucune raison que la courbure soit toujours concave/convexe entre 2 sommets.

NB: au fait, l'algo d'enveloppe convexe qui trie les points suivant l'angle avec un point extreme c'est pas le gift-wrapping (aka Jarvis march) : c'est le Graham scan.
14/01/2008, 17h47
souviron34

l'algo est en C ;)

Pour le nom, il y a les 2, je crois : le principe est Graham Scan mais la methode s'appelle Gift Wrapping, non ??
14/01/2008, 17h48
souviron34

Citation:

Envoyé par edfed

.....
il y à 8 directions, possibles
nord, NO, ouest, SO, sud, SE, est, NE,... nord.

pour parler angles, 0, 45,90,135,180,225,270,315, et retour à 0

mdr :mouarf:

Voir 40 message(s) de cette discussion en une page