Discussion :

[Zavonen]

A mon avis c'est assez simple, voici encore qqs bouts de code C:

Code :

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#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;
}
 
// décide si un vol est fermé
double VolFerme()
{
    return Distances[0][N-1]<3000;
}
 
// mesure le vol triangulaire
double VolTriangle()
{
    int i,j,k;
    double M=0.0;
    double T;
    for (i=0;i<N;i++)
        for (j=i+1;j<N-1;j++)
            for (k=j+1;k<N;k++)
            {
                T=Distances[i][j]+Distances[j][k]+Distances[i][k];
                if (T>M) M=T;
            }
    return M*1.2;
}
 
// Condition pour la reconnaissance d'un vol quadrilatère
double Condition (double x, double y, double z, double t)
{
    double S=x+y+z+t;
    if (x/S<0.15) return 0; //raté
    if (y/S<0.15) return 0; //raté
    if (z/S<0.15) return 0; //raté
    if (t/S<0.15) return 0; //raté
    return 1; // gagné
}
// mesure le vol quadrilatère
double VolQuadri()
{
    int i,j,k,h;
    double M=0.0;
    double Q;
    for (i=0;i<N;i++)
        for (j=i+1;j<N-2;j++)
            for (k=j+1;k<N-1;k++)
                for (h=k+1;h<N;h++)
                {
                    Q=Distances[i][j]+Distances[j][k]+Distances[k][h]+Distances[i][h];
                    if (Condition(Distances[i][j],Distances[j][k],Distances[k][h],Distances[i][h])&&(Q>M)) M=Q;
                }
    return M*1.2;
}
// maximum de 2 nombres
double Max2(double u, double v)
{
    return (u>v)?u:v;
}
// maximum de 3 nombres
double Max3(double u, double v, double w)
{
    return Max2(u,Max2(v,w));
}
// Distance finalement prise en compte
double VolValide()
{
    double L=MaxDist(); // distance linéaire
    double T=0,Q=0;
    if (VolFerme()) // si vol fermé
    {
        T=VolTriangle(); // évaluer vol triangulaire
        Q=VolQuadri(); // évaluer vol quadrilatère
    }
    return Max3(L,T,Q); // retourner le max
}
 
 
int main()
{
    Remplir();
    printf("%lf\n",VolValide());
    return 0;
}

[Graffito]

Sup de d(Mi,Mj)+d(Mj,Mk)+d(Mk,Mi)

et pour optimiser, pré-calculer la matrice D[Mi,Mj] pour tous les couples.

Comme l'imagine alikendarfen :
On peut aussi réduire considérablement le nombres de points significatifs en traitant les suites "glissantes" de 5 points consécutifs An-2,An-1,An,An+1,An+2.
Dans ces suites on pourra éliminer An, si :
- An est proche du segment An-1_An+1,
- la projection de An sur ce segment est situé entre An et An+1,
- les angles An-2/An-1\An et An-2/An-1\An+1 ne font pas apparaitre une brusque vartiation de direction
- idem pour les angles An/An+1\An+2 et An-1/A+1\An+2.

Petite question sur les quantités d'info à traiter:
Quel est le nombre max de positions et l'ordre de grandeur de la distance entre 2 positions consécutives?

[giloutho]

Super les réponses, me reste plus qu'à éplucher tout cela...

Pour la réponse de pseudocode, ch'suis pas sûr d'être tout à fait au niveau

Mais là j'ai des pistes sérieuses pour me mettre au boulot. Pour Graffito, le nombre de points est variable et dépendant de deux facteurs : la durée du vol évidemment et l'intervalle de trace choisi par le pilote sur son GPS. En général 1 point toutes les 10 s suffit, mais certains te balancent des traces avec 1 point toutes les secondes. S'il a fait 150 bornes en 4 heures La distance entre deux points va varier aussi en fonction de cet intervalle et de la vitesse. Grossièrement, je dirais entre 50m et 200 m ( entre 20km/h et 60 km/h avec un point toutes les 10s). Ce qui brouille aussi pas mal, c'est que sur la trace il y a plein de spirales. En gros pour assurer le cheminement il faut grimper en altitude donc spiraler dans le thermique, aller vers le point suivant, donc perte d'altitude, remonter en spiralant, transiter, etc... Mais de toute façon j'ai plus ou moins prévu, de prendre un point toutes les dix secondes. C'est à dire que si le gus fournit une trace avec un point toutes les secondes, je construirai ma matrice en prenant un point sur 10...

J'ai deux programmes qui font cette évaluation, je suis stupefait par la différence de performances. Quand je fais mouliner une grosse trace, il donnent tous les deux des résultats assez proches, mais par contre il y en a un qui met trois fois moins de temps !!!

[pseudocode]

Pour la réponse de pseudocode, ch'suis pas sûr d'être tout à fait au niveau

Mais heu.... c'était clair pourtant.

cherche "Douglas-Peucker" sur images.google.fr

[giloutho]

Trop fort Zavonen J'ai pris ton code et ça marche nickel... pour la meilleure distance et le triangle. Je vais aller faire dodo avant d'attaquer le quadrilatère.

Sur une trace test je trouve exactement les mêmes valeurs que les programmes de réference...

Merci à tous