Discussion :

[giloutho]

Bonjour à tous,

J'ai réalisé un petit soft de visualisation de trace gps enregistrées lors de vols en parapente. Ils existe divers challenge où pour apprécier la valeur d'un vol on note le nombre de kms parcourus, 1 km = 1 point. Pour une distance dite "libre" c'est facile on mesure la distance entre les deux points les plus éloignés.

Donc voici ma première question : dans un nuage de points dont les coordonnées sont latitude et longitude, comment déterminer les deux points les plus éloignés.

J'avoue ne pas avoir beaucoup d'idées. J'imagine de calculer la distance du point 1 à tous les autres points. Je garde la plus grande, et je recommence avec le point 2 par rapport à à tous les autres points et ainsi de suite...Et ensuite je compare les valeurs obtenues ?

Je parle de première question, car cela peut devenir nettement plus compliqué, un parcours en triangle par exemple compte beaucoup plus qu'un parcours simple. Le nombre de points est majoré de 20%.

Là je vois pas trop comment procéder ... Pourtant cela se fait, il existe quelques logiciels qui font le calcul des diverses combinaisons possibles, pour permettre au pilote de déclarer son vol avec le maximum de points. Sans rentrer dans les détails, pour qu'un vol puisse être considéré comme autre chose qu'une simple distance, il faut qu'il y ait moins de 3 km entre le point de départ et le point d'arrivée. Calculer cela, au moins c'est à ma portée

Merci d'avance

[souviron34]

il y a plusieurs solutions...

A priori ton GPS envoie des infos tous les x (secondes etc..).

Tu peux donc sommer toutes les distances 2 a 2 durant la duree du vol. Cela donnera (a peu pres) la distance totale parcourue.

Tu peux aussi calculer le min/max des latitudes/longitudes.

Ca te donne une boite dans laquelle le vol est compris(une premiere approxcimation du probleme no 1)

[giloutho]

Merci Souviron34... je me suis mal exprimé, le calcul se fait à posteriori et non pas en analysant des trames en temps réel. Il s'agit d'une analyse de la trace qui se fait sur un PC après récupération de la trace.

Je travaille sur une liste de points. Je suis en C# donc c'est une liste mais dans d' autres langages ce serait un array.

La distance totale parcourue je la calcule déjà.

Je vais explorer la piste de la boite... donc d'un polygone...

Cze qui me chagrine vraiment c'est l'histoire des angles pour le triangle.

[Tommy31]

Et en déterminant une courbe approximante sur le nuage ?

[giloutho]

Merci Tommy... Pourrais tu m'expliquer ce que tu entends par courbe approximante ?

[mr_samurai]

Tu peux simplement sommer sur le contour convexe de ton nuage ... par contre si fai des zig-zags l'approximation est moins bonne ...

Si tu ne disposes pas d'une information sur l'ordre d'acquisition des tes points, je ne vois pas comment procéder autrement .


++

[souviron34]

Tu peux simplement sommer sur le contour convexe de ton nuage ...

+1

[giloutho]

Merci de vous intéresser à mon problème... Par contre pourrais tu m'expliquer la manip pour :

Tu peux simplement sommer sur le contour convexe de ton nuage ...

Je suis le boulet de la semaine !!!

Par contre en ce qui concerne :

Si tu ne disposes pas d'une information sur l'ordre d'acquisition des tes points

Je l'ai complètement puisque ma liste est ordonnée par ordre chronologique. Chaque point comporte latitude, longitude, altitude et heure (hh:mm:ss).

[mr_samurai]

Tu peux donc sommer toutes les distances 2 a 2 durant la duree du vol. Cela donnera (a peu pres) la distance totale parcourue.

si on prend (Pi)i=1..N l'ensemble de tes point alors :

D = SOMMEi=1..N-1[d(Pi,Pi+1)]
avec, d(X,Y) la distance entre X , Y.
Bien sur une opération de conversion est nécessaire pour passer à des mètres.

[Zavonen]

La terre n'est pas plate ...
Mais quand on se restreint à un petit parcours on peut supposer qu'elle l'est.
Supposons qu'on se déplace sur le même méridien d'un angle de d1 degré de latitude.
L'angle en radians est donc alpha=(d1/180)*pi.
La distance parcourue est donc R*alpha
Supposons maintenant qu'on se déplace sur un même parallèle d'un angle de d2 degré de longitude.
Pour les mêmes raisons la distance parcourue est R*beta où beta =(d2/180)*pi
Confondons localement la sphère terrestre avec son plan tangent la distance parcourue pour une variation de d1 degré de latitude et d2 degré de longitude est donc par Pythagore:
R*pi/180*sqrt(d1*d1+d2*d2).
Si tu disposes de n points P1, P2, ...,Pn
Tu peux remplir une matrice carrée n*n où le coefficient de la ligne i et de la colonne j correspond à la distance de Pi à Pj.
En fait le triangle supérieur suffit puisque la matrice est symétrique.
Ensuite, tu cherche le maximum des coefficients par un balayage du triangle supérieur et tu as la valeur cherchée.

[souviron34]

je ne crois pas que c'est ce dont parlait mr_samurai mais plutot de la transformation latitude->m ou longitude->m
(1 degre a peu pres egal a 100 kms (lat) et 110 kms (lon))

[giloutho]

Je crois qu'il faut que j'explore la piste donnée par Zavonen... Grand merci Zavonen d'avoir pris le temps de faire une réponse didactique. J'ai un bout de C qui, me semble t il, va exactement dans ce sens. Je dis me semble t il car cela a été fait et commenté par un allemand !!! Comme en plus je capte pas tout en C. Mais j' ai bien vu qu'il construisait une matrice.

En ce qui concerne les distances et les angles... cela ne me pose aucun problème, j'ai les formules qui me permettent de faire directement :

Code :

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

d = Distance(Lat1,long1,Lat2,Long2

et de la même manière :

Code :

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

c = Cap(Lat1,long1,Lat2,Long2)

Donc pour explorer la distance libre, cela devrait gazer.

Mais pour le triangle, j'ai l'impression que cela va être une autre histoire, il va falloir que je m'occupe des angles... Pi en plus, je ne vous ai pas tout dit il existe encore d'autres possibilités dont une est assez utilisée c'est le quadrilatère :

La règle est simple il faut qu'il y ait moins de trois kilomètres entre BD et BA et que l'on arrive à caser un polygone convexe à l'intérieur...

[mr_samurai]

Tu m'as perdu en route .

Que cherches tu à calculer exactement ?

[Zavonen]

Voici pour les trajets 'quasi-linéaires'
Il n'y a qu'à remplacer N par le nombre de points
et remplir les tableaux des longitudes et des latitudes

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
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// le nombre de points
#define N 100
// la table des latitudes
double Latitudes[N];
// la table des longitudes
double Longitudes[N];
// le rayon de la terre en mètres
const double R=6378000.00;
// le nombre pi
const double pi=3.14159265;
// La matrice des distances
double Distances[N][N];
 
// La distance de Pi à Pj
double dist(int i, int j)
{
    return R*pi/180*sqrt((Latitudes[i]-Latitudes[j])*(Latitudes[i]-Latitudes[j])+
                         (Longitudes[i]-Longitudes[j])*(Longitudes[i]-Longitudes[j]));
}
 
// fonction qui remplit le riangle supérieur de la matrice des distances
void Remplir()
{
    int i,j;
    for ( i=0;i<N;i++)
        for ( j=i+1;j<N;j++)
            Distances[i][j]=dist(i,j);
}
// Détermine la distance maximum de deux points
double MaxDist()
{
    double M=Distances[0][0];
    int i,j;
    for (i=0;i<N;i++)
        for (j=i+1;j<N;j++)
            if (Distances[i][j]>M) M=Distances[i][j];
    return M;
}
 
int main()
{
    Remplir();
    printf("%lf\n",MaxDist());
    return 0;
}

[Zavonen]

Pour les trajets 'polygonaux' la condition entre le départ à l'arrivée est facile à transcrire dans le pgm ci-dessus:
Distances[0][N-1]<3000
Par contre ce qui est difficile c'est de déterminer s'il s'agit 'plutôt d'un triangle' ou 'plutôt d'un quadrilatère'.
Et ce qui est encore plus difficile c'est de déterminer, si on cherche un triangle quel est celui qui représente le mieux le trajet, à moins qu'on recherche tout bêtement le
Sup de d(Mi,Mj)+d(Mj,Mk)+d(Mk,Mi)
Ce qui est un jeu d'enfant à écrire.
Il doit y avoir des contraintes que tu n'a pas communiquées.

[giloutho]

Pour Mr_Samourai et ceux qui ont la gentillesse de me lire je reprends depuis le début en réexpliquant ce que je cherche à calculer.

Bq de parapentistes emmenent en vol en GPS. Il existe ds chaque pays un challenge de distance géré grâce au web. On télécharge sa trace GPS et elle est évaluée en terme de distance. 1km = 1 point. La distance n'est pas simplement évaluée depuis le point de départ jusqu'à l'aterrissage. Si vous regardez le schéma No1 donné au début du post vous constaterez qu'il y a ce que l'on appelle deux points de contournement. La distance entre DA et DB est plus grande que la distance séparant le déco de l'atterro. En anlysant sa trace, on a donc intérêt à rechercher les deux points les plus éloignés. Pour compter les kms qui vont etre retenus pour le scoring, il faut finalement faire tenir le plus grand segment possible à l'intérieur du nuage de point. La longeur du segment donne le nombre de km retenus pour le calcul de points.

Dans les règles de Féderation Aeronautique Internationale ( qui régissent les records de planeurs, sur des bases très proches) il y a une prime pour les parcours en boucle. Le pilote qui boucle un parcours en triangle réalise une performance bq plus importante qu'une distance libre. Il y a forcément une branche face au vent, etc..., etc...En triangle 1km = 1,2 points. Mais pour qu'il y ait ce bonus, il faut respecter quelques règles, la distance entre le décollage et l'atterrissage doit être inférieure à 3km, etc... je passe les détails. Si c'est un quadrilatère, on peut encore comptabiliser qq kms supplémentaires. Mais la plus petite branche du parcours doit faire au moins 15% de la distance totale.Donc là encore dans le nuage de points, on cherche à faire rentrer un polygone ( triangle ou quadrilatère), et c'est le périmètre de ce polygone qui donnera la distance prise en compte.

A quoi sert le bout de code que je désire réaliser ? d'une part savoir ce que vaut le vol réalisé en regard des règles FAI, est ce que ça peut passer en quadrilatère ou est ce que ce sera juste un triangle ? D' autre part les pilotes adorent discuter le soir au coin des cartes en préparant le vol du lendemain. Il s'agit donc aussi d'évaluer en terme de points ce que peut rapporter le cheminement envisagé.

Voili, voilou... merci Zavonen pour le bout de code, je vais travailler dessus...

[Alikendarfen]

Bonjour,

Le problème de la reconnaissance des triangles ou des quadrilatères me fait penser au calcul d'une courbe de Bezier mais à l'envers.

Je ne suis pas spécialiste (et une recherche sur internet sera utile) mais j'imagine un algo où il faudrait chercher à réduire progressivement le nombre de points des points de parcours. Par exemple, si trois points sont quasi alignés, à une tolérance près, ne garder que les extrémités.

Par passes de réductions successives, cela donne peut être le résultat recherché... (pas sur d'avoir le temps, mais j'essaye de m'y mettre pour voir).

[Alikendarfen]

PS : t'est il possible de nous communiquer quelques fichiers exemples, dans un format simple ?

Merci

[pseudocode]

Je ne suis pas spécialiste (et une recherche sur internet sera utile) mais j'imagine un algo où il faudrait chercher à réduire progressivement le nombre de points des points de parcours. Par exemple, si trois points sont quasi alignés, à une tolérance près, ne garder que les extrémités.

Par passes de réductions successives, cela donne peut être le résultat recherché... (pas sur d'avoir le temps, mais j'essaye de m'y mettre pour voir).

Ca me semble une bonne idée.

On peut utiliser l'espace de Hough pour trouver les droites.

On construit la fonction F(t)=(rho,theta)
- avec "t" est le n° de la mesure
- avec (rho,theta) les caracteristiques de la droite portant le segment [P(t),P(t+1)]

+ Un petit lissage pour supprimer les outliers
+ un petit algo de réduction multi-linéaire (Douglas-Peucker)

[Tommy31]

Il déchire ce topic