Discussion :

[totolito]

Bonjour à vous,

J'ai à disposition un appareil qui me fournis la position 2D d'un outil de fouille (genre petite pelle hydraulique).

J'essaye d'afficher une courbe avec en abscisses l'éloignement de l'outil par rapport à une référence (x) et en ordonnées la profondeur atteinte de l'outils (y).
Pour m'aider à développer, j'affiche sur le même graphe un nuage de points qui correspond à tous les points renvoyés par l'outils, et ma courbe après traitement.

J'ai quelques difficultés pour gérer ma courbe lorsque l'outil repasse aux mêmes endroits avec des profondeurs différentes. Comme vous pouvez le voir sur la courbe en pièce jointe, j'ai quelques pics indésirables. J'ai dans un premier temps cherche différents algo pour identifier l'enveloppe inférieur du nuage de point, mais comme je fais ce traitement en temps réel sur un petit micro, je m'oriente actuellement vers un algo un peu plus "bête".

Le traitement pour chaque nouveau point est le suivant:


SI un point aillant le même x existe déjà dans mon graphe ET que le nouveau point a un y plus petit ALORS remplacer l'ancien avec le nouveau
SINON SI le nouveau point.x est plus petit ou plus grand que tous ceux déjà ajoutés, ALORS ajouter le nouveau point
SINON
{
Prendre les deux points existant adjacents à mon point.x, faire une extrapolation linéaire pour calculer la droite passant par ces deux points
SI y extrapolé en point.x est plus grand que point.y ALORS ajouter mon nouveau point
}

Tout ceci me donne un résultat assez proche de ce que je souhaite, mais j'ai encore quelques pics indésirables. Je pense qu'il faudrait encore quelques ajustements.


Ci-dessous le "vrai code". La partie en commentaire améliore un peu le filtrage mais ne suffit pas.

Merci à ceux qui s'y intéresseront...

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
 
void DialogPlots::AddPoint(int graphNum, QPoint point)
{  
    QCPDataMap* map = ui->customPlot->graph(graphNum)->data();
    if(true == map->isEmpty())
    {
        map->insert(point.x(), QCPData(point.x(), point.y()));
    }
    else if(true == map->contains(point.x()))
    {
        if(map->value(point.x()).value > point.y() )
        {
            map->insert(point.x(), QCPData(point.x(), point.y()));
        }
    }
    else
    {
        QList<double> keys = map->keys();
        if((keys.first() > point.x()) || (keys.last() < point.x()))
        {
            map->insert(point.x(), QCPData(point.x(), point.y()));
        }
        else
        {
            int prev_key = point.x();
            while(false == map->contains(--prev_key));
            int x1 = prev_key;
            int y1 = map->value(prev_key).value;
 
            QMap<double, QCPData>::const_iterator next = map->upperBound(point.x());
            int x2 = next.key();
            int y2 = next.value().value;
 
            int p = (y2 - y1) / (x2 - x1);
            int y_virtual = p * (point.x() - x1) + y1;
 
            if(y_virtual > point.y())
                map->insert(point.x(), QCPData(point.x(), point.y()));
 
 
            if(prev_key > keys.first())
            {
                while(false == map->contains(--prev_key));
                int x0 = prev_key;
                int y0 = map->value(prev_key).value;
                if((y1 > y0) && (y1 > point.y()))
                    map->remove(x1);
            }
 
 
            next++;
            if(next.key() < keys.last())
            {
                int x3 = next.key();
                int y3 = next.value().value;
                if((y2 > y3) && (y2 > point.y()))
                    map->remove(x2);
            }
        }
    }
    ui->customPlot->rescaleAxes();
    ui->customPlot->replot();
}

[tbc92]

Dans ton raisonnement, tu te places dans le cadre scolaire : J'ai une fonction f, et pour chaque valeur de x, j'ai un f(x) qui devrait être unique... x a donc un rôle différent de y.

Ici, x et y ont le même rôle.
si tu prends ton dessin et que tu le fias tourner d'un quart de tour... les points restent tels quels, la courbe devrait elle aussi tourner d'un quart de tour.

Ce que tu peux faire, c'est à partir d'un point, chercher le point le plus proche. Mais le point le plus proche, c'est celui qui a la distance euclidienne D la plus petite ( D = racine ((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) )
Et au fur et à mesure, tu retires de l'ensemble des points les points déjà utilisés.
Ca marchera parfaitement sur toute la partie en haut à droite de la courbe. Ca risque de faire un truc bizarre en bas à gauche.
L'autre difficulté de cet algorithme, c'est qu'idéalement, il faut choisir une des 2 extrémités de la courbe comme 1er point. Sinon, on peut adapter l'algo pour qu'il marche quelque soit le point de départ.

Poste ton jeu de données si tu veux plus d'aide.

[totolito]

Merci pour ta réponse.

Oui excellente idée. Voici donc en pièces jointes un jeu de données et le résultat en screenshot en utilisant l'algo ci-dessus.

Je précise que le point de départ peut être n'importe où...
dataset.txt

[totolito]

Fin de l'exercice et correction

La solution qui-marche-bien est de mémoriser le dernier point ajouté. Par la suite, lorsqu'un nouveau point est ajouté, je parcours tous les points de ma courbe compris entre ce nouveau point et le dernier ajouté, si les y de ces anciens points sont au dessus de la droite reliant le nouveau et le dernier point, je le supprime.

that's all !


Merci et à la prochaine

[totolito]

et ça donne ça:

[CliffeCSTL]

Fin de l'exercice et correction

La solution qui-marche-bien est de mémoriser le dernier point ajouté. Par la suite, lorsqu'un nouveau point est ajouté, je parcours tous les points de ma courbe compris entre ce nouveau point et le dernier ajouté, si les y de ces anciens points sont au dessus de la droite reliant le nouveau et le dernier point, je le supprime.

that's all !


Merci et à la prochaine

ça me paraît simple et évident pourtant :

Code :

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

1
2
3
4
5
6
7
8
9
Pour chaque point P de coordonnées (x, y) faire
    Si un point Q de même coordonnée x est déjà sélectionné alors
        Si la nouvelle coordonnée y de P est plus petite que celle de Q alors
            On garde P et on supprime Q
        fsi
    sinon
        On garde P
    fsi
fait

[totolito]

Salut à toi,


Oui à première vue c'est très simple et c'est comme ça que je l'avais codé. Mais c'est sans prendre en compte différents phénomènes comme celui ci-dessous:

- Soit deux points A et B déjà ajoutés de coordonnées [4;10] et [6;12]. Deux nouveaux points C et D "arrivent" avec comme coordonnées [3;49] et [5;50]: avec ton algo je vais voir un "pic" entre A et B (voir mes anciennes captures d'écran).