Discussion :

[pseudocode]

Mes coordonnees sont des coordonnes latitude, longitude avec 2 decimales de precision apres la virgule. Pourquoi ?

Pour savoir si on pouvait précalculer la distance entre les points de l'image et le polygone. Visiblement non, a moins de discrétiser tes données et donc de tolérer une certaine erreur sur le calcul de distance.

[souviron34]

je pense vraiment que la solution la plus simple, complète, et efficace est celle-ci :

Tu calcules un "faux" polygone dézoomé (avec la distance en moins).
Et là, tout ce que tu as à faire, c'est vérifier si ton point est dans le premier et pas dans le deuxième..

Avec les algos cités (pt-in-polygon) ça se fera vite...

Ou alors de calculer comme on l'avait dit les distances avec chaque segment suivant les formules données au début du thread..


Mais pt_in-polygon est juste basé sur N fois :

5 tests + 4 additions + 1 multiplication + 1 division

(j'avais récupéré la méthode de Segdewick, mais elle semble ne pas marcher à tous coups. Celle du forum Dr Maths marche parfaitement :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
  int     i, j ;
  int Inside = 0 ;
 
 
   if ( N_Pts <= 2 )
      return False ;
 
   for (i = 0, j = N_Pts-1; i < N_Pts; j = i++) 
    {
       if ((((Pts[i].Y <= Pt.Y) && (Pt.Y < Pts[j].Y)) ||
            ((Pts[j].Y <= Pt.Y) && (Pt.Y < Pts[i].Y))) &&
           (Pt.X < ((Pts[j].X - Pts[i].X) * (Pt.Y - Pts[i].Y) / 
                       (Pts[j].Y - Pts[i].Y) + Pts[i].X)) )
 
          Inside = !Inside;
      }

[Saita]

J'ai deja implementer un algorithme (qui est presque similaire) pour savoir si un point est dans un polygone.
Mais je n'ai pas compris l'histoire du faux polygone dezoomer.. Tu calcules ses sommets comment ?

[souviron34]

puisque tu as des lat-lon, il faut commencer par aller à la rectangularisation (les équations de projection), qui représentent les coordonnées dans un système rectangulaire (en mètres).

De là, il faut que tu "rétrécisses" ton polygone par la distance limite. Ce qui veut dire que tu projettes vers l'intérieur chaque sommet sur la médiatrice de l'angle. Par contre, il faut ensuite repasser un coup, puisque des côtés peuvent du coup se croiser. Il faudra donc remplacer le(s) sommet(s) éventuellement par l'intersection des côtés.

Là tu as le "même" polygone que précédemment, sauf qu'il est plus petit d'une certaine distance (c'est le même algo que dans un autre post pour "ajouter" une distance (ou une enveloppe) : problème de trigonométrie).

[Saita]

Interessant !
Ca pourrait etre une bonne idee...
Mais que faire dans ce cas : (10eme post de Brutus)

(je laisse volontairement le fait que la ligne brisée bleu résultante s'auto-intersecte. Ceci ne perturbera pas l'algorithme, par contre, il sera utile de signaler l'incohérence géométrique)

[souviron34]

ton lien ne marche pas..


PS : c'est un projet à toi, ou dans une entreprise ?

[Saita]

Oui c'est un projet d'entreprise..Mais que j'adore soit dit en passant
J'ai change mon precedent post

[souviron34]

Interessant !
Ca pourrait etre une bonne idee...
Mais que faire dans ce cas : (10eme post de Brutus)

la logique mathématique impose d'enlever le sommet et d'avoir 2 intersections. Les distances seront toutes correctes..

C'est en ça que l'algo est un peu plus complexe que la stricte application du principe

De la même manière, comme j'avais cité à la fin de l'autre post, dans le cas d'un angle aigu, l'angle peut totalement disparaître..



PS: j'ai regardé hier ma routine d'ajout de distance.. Effectivement, elle est un peu longue (2000 lignes de C ), et ajoute soit à un polygone (cas plus simple, puisqu'on n'a qu'à prendre l'extérieur), soit à une ligne brisée (cas plus complexe car on a besoin des 2 côtés de la ligne).

Je vais voir si je pourrais la simplifier, et l'étendre à la soustraction d'une distance pour un polygone (ce qui revient à prendre la ligne intérieure, que j'avais laissé tomber dans mon cas).

PPS : si le besoin est urgent, contacte-moi par MP..


PPPS : d'alleurs, la figure est fausse, puisque la distance entre le sommet et sa projection est plus grande que la distance entre le côté et sa projection.. En fait, cette figure repésente le zoom du polygone, pas l'ajout d'une distance...

[Saita]

Non ca va se n'est pas urgent pour l'instant...En fait j'ai anticipe un peu sur la demande, je devrais avoir une reunion a ce propos avec mon boss...vendredi dernier ! lol et hier aussi ! Mais je ne l'ai toujours pas eu cette discussion ! Donc ca ne presse pas Et puis c'est pas comme si je n'avais aucune autre solution, l'autre (de tester pour chaque segment) marche bien a mon avis meme si elle n'est peut etre pas optimale.

Pour ton pps...Tu as raison ! mais alors du coup, impossible de m'imaginer la vraie figure..j'ai un bug au niveau de l'angle..
Je peux avoir un dessin

[souviron34]

Pour ton pps...Tu as raison ! mais alors du coup, impossible de m'imaginer la vraie figure..j'ai un bug au niveau de l'angle..
Je peux avoir un dessin

Voici un exemple d'une ligne brisée, puis de l'ajout d'une distance à 20, 50, 100, 150, 200, 250, 300, 350, 400, 500, 800 et 1200 kms.

(je ne sais pas si je laisserais la figure longtemps, à cause de la taille de l'attachement (169k) ).

[Saita]

Merci je l'ai vu (et enregistre)

[Saita]

Bonjour, je devrais peut être ouvrir un autre sujet mais j'espere que quelqu'un me répondra quand même si je reste sur celui-ci..
Je bute sur une conversion.
Comme je l'ai dis au début, le but est d'émettre une alarme quand la distance point segment du polygone est en dessous d'une distance lambda.
Le plus simple est convivial est que ma distance lambda soit en km.
Mais je travaille est des coordonnées latitude/longitude...
Je n'arrive pas a trouver comment faire la correspondance entre les deux.
A un moment dans mon programme je fais des comparaisons :

Code :

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

1
2
3
#Then the minmum distance is PA, we check if this distance is under our constant
          if ( $xAP**2+$yAP**2 < $Const**2 ) {
#Alarrrrrrrrrrme ! et la distance est racine de

ou $xAP et $yAP sont les coordonnes de mon vecteur AP (P le point et AB le segment que l'on teste)
Mais le problème est donc que ma constante est en kilomètre..Donc mon résultat ne sera pas celui attendu.
J'espère que vous comprenez ce que je veux faire, sinon dites le moi, j'essaierai d'être plus claire.
Merci

[souviron34]

lol...

Problème usuel et déjà (largement) commenté ici...

La transformation de latitude-longitude en mètres (km) dépend du datum (coordonnées du centre de la Terre et ellipticité) et de la projection utilisée...


Il faut donc :

• a) connaître ta projection
• b) transformer en coordonnées rectangulaires suivant les équations ad'hoc
• c) calculer les distances

Une distance entre 2 couples (lat-lon) ne donne pas de distance en km.. Tout au plus une approximation (1 degré n'a pas la même longueur au pôle ou à l'équateur)..

[Saita]

Oui j'avais trouve des methodes pour ca..mais je veux transformer des metres (ou kilometres) en une autre unite..celle que j'obtiens quand je fais une distance entre deux points ayant des coordonnees latitude longitude...
Je ne sais pas si je suis tres clair.. En gros, je ne veux pas passer de ma distance aux kilometres mais l'inverse... Et ca coince.
Je retourne chez moi et je detaille ca si c'est pas clair ce soir.
++

[Saita]

Ok. Mon chéri m'a expliqué où je faisais erreur... Calculer

Code :

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

sqrt($xAP**2+$yAP**2)

ne sert à rien, ça ne donne pas du tout une distance si mes points xA yA xP yP sont en longitude latitude...
Je n'avais pas compris.
Donc ce que j'ai voulu faire tombe à l'eau. Et je pense qu'on peut en dire autant de l'histoire du Polygone dézoomer..

[souviron34]

ben non, ça dépend ce que tu cherches à faire....

Si c'est avoir une alarme à l'intérieur d'un certain polygone, je t'ai exliqué la marche à suivre :

1. transformer les coordonnées lat/lon des sommets de ton polygone en coordonnées X,Y, données par les transformations d'après ta projection de base (Lambert, stéréographique, UTM, vraie à 60 degrés latitude nord, ou autre).
   
   
2. ajouter (ou plutôt retrancher) la distance à ce polygone en X,Y
   
   
3. à chaque point en mvt, vérifier si il est dans le polygon 1 et pas dans le 2
   
   
   si la réponse au test ci-dessus est oui :
   
   • si le point était déjà en alarme, rien
   • si le point n'était pas en alarme, déclencher alarme
   
   
   
   si la réponse au test ci-dessus est non :
   
   • si le point était en alarme, arrêter l'alarme
   
   
   
4. afficher position (en lat,lon)

[souviron34]

ça ne donne pas du tout une distance si mes points xA yA xP yP sont en longitude latitude...
Je n'avais pas compris.

c'est ce que j'avais écrit ici :

Une distance entre 2 couples (lat-lon) ne donne pas de distance en km.. Tout au plus une approximation (1 degré n'a pas la même longueur au pôle ou à l'équateur)..

[Saita]

Dslee. Je n'avais pas compris..
Pour moi lat,long=coordonnees x,y ce qui est completement faux !
Va falloir que je me plonge dans la theorie un peu plus...J'ai jamais fait ce genre de truc (enfin si une ou deux fois mais j'en ai garde un mauvais souvenir..)
Bref, merci pour l'aide et les infos..
Je reviendrai poser des questions quand je verrai mieux de quoi je parle.
++

[Saita]

http://www.developpez.net/forums/d64...nees-polygone/
Magnifique lien qui correspond a mes attentes (vive la fonction recherche...Quand on sait ce qu'on cherche ! lol)
Donc, je reprend espoir, tous mes calculs et idees peuvent etre reprises (si j'ai bien compris) en appliquant simplement la jolie formule indiquee dans wiki (car mes lat/long viennent de google maps qui utilise la projection de Mercator) http://fr.wikipedia.org/wiki/Projection_de_Mercator qui me permet de retomber sur mon plan d'ou je peux effectuer tous mes calculs niveau lycee
Mais je sais que l'on t'a deja pose cette question mais je prend quand meme le risque : Quel centre λ0 prendre ?
Je veux une carte du monde donc...Puis-je prendre quasiment n'importe quel centre ?
Deuxieme question, il est marque que cette projection ne marche plus aux poles... Bon, j'imagine que le cas ne se produira pas pour moi, mais si on se rapproche des poles, quel danger ?
Merci encore

[souviron34]

Mais je sais que l'on t'a deja pose cette question mais je prend quand meme le risque : Quel centre λ0 prendre ?
Je veux une carte du monde donc...Puis-je prendre quasiment n'importe quel centre ?

La longitude centrale de ta carte.

Si tu as vraiment une carte du monde (360 degrés), tu te centres là où tu veux, sachant que ce qui sera là sera au milieu de la carte..

Sinon il faut calculer l'étendue en longitude, et en prendre le milieu.

Deuxieme question, il est marque que cette projection ne marche plus aux poles... Bon, j'imagine que le cas ne se produira pas pour moi, mais si on se rapproche des poles, quel danger ?
Merci encore

Voir l'exemple donné sur Wiki :

La calotte arctique et le continent antarctique prennent toute la largeur de la carte..

Le pôle est à l'infini mathématique (tan (PI/2) (tan(1/4 PI + 1/2 phi), or phi est égal à PI/2, puisque la latitude démarre à l'équateur)).