Sélection de points parmis une table

[coqp-ox]

Tout d'abord, excusez-moi pour le titre qui ne reflète pas totalement ce dont j'ai besoin. Je vais essayer d'être un peu plus explicite dans sa description.

Dans le cadre d'un stage, je dois réaliser un projet qui demande de réaliser un algorithme en C (chose dont je ne suis pas capable puisque ce n'est "pas" un enseignement dispensé par mon école).

Ce projet (programme) a pour but de lier grâce à une fonction, le mouvement d'un axe maitre à celui d'un axe secondaire (en gros :bad: ). L'utilisateur qui utilise ce programme doit fournir une liste de points (position axe maitre, position axe secondaire) afin qu'on puisse définir une fonction capable de relier ces points.

Voila donc les problèmes qui se posent.
Dans un premier temps, l'utilisateur peut donner autant de points qu'il le souhaite, cependant, le robot qui va utiliser la fonction ne peut en mémoriser que 32. Ainsi, une première partie de l'algorithme servirait à "choisir" les 32 points les "plus représentatifs" (ou les points donnés s'il y en a moins de 32) de la table de points fournie. Pour se faire, je propose ici de calculer un "écart relatif" entre deux points consécutifs. (Plus d'explication sur l'image)



Ensuite vient le gros du problème : la résolution du système. En effet, pour construire la fonction j'utilise la méthode des splines cubiques encastrés (puisque j'ai besoin d'avoir des dérivées nulles aux bords de "la" fonction), or, cette méthode demande de résoudre qui varie forcément en fonction du nombre de points choisis auparavant. Après résolution du système, on trouve les "principaux" coefficients des splines qui nous permettent de trouver les coefficients manquants.

En sortie, on doit obtenir n-1 fonctions (ou leur dérivée qui représentent donc la vitesse) qui puissent etre utilisées par un variateur pour définir la vitesse à adopter par l'axe secondaire.



Comme vous l'aurez compris, le problème n'est pas la représentation de la fonction finale mais bien son "écriture".

Merci d'avance pour votre aide et bonne journée!
(Je reste disponible pour toute précision)

Edit : Je viens de me rendre compte d'une petite erreur dans mon "premier" ordinogramme. Dans la condition k=31, il faut en fait écrire k=n qui signifie que si on a atteint de dernier point (donc de coordonnée (xn,yn)) alors on repart du début (sans les points qui ont donc étés supprimés).

[fatal_error]

hello,

ben tu peux deja distinguer la partie qui est loadee dans le robot de la partie ou tu preformattes tes points

Voila donc les problèmes qui se posent.
Dans un premier temps, l'utilisateur peut donner autant de points qu'il le souhaite, cependant, le robot qui va utiliser la fonction ne peut en mémoriser que 32. Ainsi, une première partie de l'algorithme servirait à "choisir" les 32 points les "plus représentatifs" (ou les points donnés s'il y en a moins de 32) de la table de points fournie. Pour se faire, je propose ici de calculer un "écart relatif" entre deux points consécutifs. (Plus d'explication sur l'image)

a priori, tu fais ton tambouie avec tes points dans n importe quel language, ET
une fois que tu as definis tes splines (qui sont caracterisees par quelque coefficients) tu peux loader ces coefficients dans ton robot.

c est assez important a noter, car des lors, ya plus de contraintes de memoire ou de temps vu qu on peut precalculer les coefficients des splines avant de les envoyer au robot

[coqp-ox]

Il est fortement possible que je n'ai pas bien compris ta remarque. Cependant le robot(variateur) n'a pas de problème de mémoire puisqu'il a seulement pour but de traduire les splines qu'on lui envoie en variation de vitesse. Cependant le servo (peut-etre que je me mélange les pinceaux) lui ne peut mémoriser que 32 points et c'est ce même servo qui effectuera les calculs.
Enfin, de ce que j'ai compris ca doit etre ca...

Ensuite, pour la première partie de mon algorithme (trier les points) j'ai essayé un truc à partir d'un tableau n (donné par l'utilisateur) lignes 2 colonnes (x et y) :
(c'est plus lisible en php...)
[php]#include
#include


const int m = 2;
using namespace std;

int main()
{
int n,r=200,u,v ;

cout > n;
int t[n][m], i, j, k=0;
for (i=0; i> t[i][j];

}
if (n>=3)
{
i=0;
while (i32.

Maintenant, j'aurais voulu savoir s'il quelqu'un saurait comment répondre à mon problème en rouge. Et si mes formules pour u et v correspondent bien à ce que je cherche...

J'avais trouvé un exemple sur wikibooks pour décaler les lignes:

Code: Tout sélectionner

#include
#include
using namespace std;
 
int main()
{
    int t[6], i, j = 0;
 
    for (i=0 ; i> t[i];
    }
 
    for(i=0 ; i<6 ; i++) if (t[i] != 9) { t[j] = t[i]; j++; }
    for(i=j ; i<6 ; i++) t[i] = 0;
 
    for(i=0 ; i<6 ; i++) cout << "La valeur numéro " << i << " est " << t[i] << endl;
    return 0;
}

Merci !

Edit : Je modifie mon code a chaque fois que je remarque une erreur flagrante ^^'

[fatal_error]

je comprends pas

Cependant le robot(variateur) n'a pas de problème de mémoire puisqu'il a seulement pour but de traduire les splines qu'on lui envoie en variation de vitesse.

Si l'utilisateur saisis 100 points. C'est le robot qui va filtrer pour ne garder que 32 points?

C'est le robot qui va donner les 32 points au servo?
Ces 32 points sont définitifs? Idem une fois que l'utilisateur a saisi ses points, il en saisira pas d'autres?

Et enfin, c'est ou que depuis les points, tu convertis en spline. Dans le robot ou dans le servo? Quelles sont les contraintes du robot: mémoire, vitesse? quelles sont les contraintes du servo, mémoire, vitesse?

Concrètement, le servo il a besoin de quoi pour faire des calculs?
Il fait quoi concrètement comme calcul? entrée, sortie

Egalement, tu vas loader un exécutable, tu le loades ou sur le robot, sur le servo (je présume sur le robot)? le robot peut-il stocker des fichiers txt? Parce que saisir 100 points c'est un peu fastidieux, lire un fichier c'est moins fatigant.

[coqp-ox]

Je pense que ce que mon tuteur entend par "robot" c'est plutot un moteur, en tout cas pour ce cas la

Si l'utilisateur saisis 100 points. C'est le robot qui va filtrer pour ne garder que 32 points?

C'est le robot qui va donner les 32 points au servo?
Ces 32 points sont définitifs? Idem une fois que l'utilisateur a saisi ses points, il en saisira pas d'autres?

J'aurais plutot dit que c'est le servo qui va transmettre les points au robot.
Effectivement, après "sélection", les 32 points sont définitifs

Et enfin, c'est ou que depuis les points, tu convertis en spline. Dans le robot ou dans le servo? Quelles sont les contraintes du robot: mémoire, vitesse? quelles sont les contraintes du servo, mémoire, vitesse?

C'est le servo qui utilisera l'algorithme pour convertir les points en splines. Pour les contraintes on ne m'en a pas parlé mais je peux me renseigner.

Concrètement, le servo il a besoin de quoi pour faire des calculs?
Il fait quoi concrètement comme calcul? entrée, sortie

Concrètement, je pense qu'il a simplement besoin du programme (ainsi que des librairies à utiliser pour résoudre le système)
Le calcul c'est à l'entrée : n coordonnées (x,y) à la sortie n-1 splines

Egalement, tu vas loader un exécutable, tu le loades ou sur le robot, sur le servo (je présume sur le robot)? le robot peut-il stocker des fichiers txt? Parce que saisir 100 points c'est un peu fastidieux, lire un fichier c'est moins fatigant.

Encore une fois je pense que c'est sur le servo. Effectivement, il serait judicieux de pouvoir stocker des fichiers txt et ca doit être réalisable.
De ce fait, je me demande si mon algorithme de départ tient toujours la route

Désolé pour l'imprécision de ma recherche, je n'ai pas été grandement renseigné auparavant !

[fatal_error]

en fait, avant de te lancer dans l optimisation de ton algorithme, commence deja par savoir si l optimisation est necessaire.
Par exemple, sera-t-il possible de telecharger des librairies dans le servo.
Generalement quand tu fais de l embarque tu as pas acces aux meme librairies que sur ton pc normal. De meme le compilateur est un peu different et tout.
Il se peut que tu ne puisses pas utiliser de librairies externes. Renseigne toi pour voir si c est possible. Sinon il faudra y aller a la mano ou copier/coller des fichiers...

Mais de maniere generale, si tu n as pas de contraintes d espaces ou de temps dans ton servo (mais uniquement dans ton robot auquel tu soumets qq coeff representant tes splines), tu peux le faire a la mano, c est pas bien complique!

[coqp-ox]

Bon, je suis au fond du seau, j'essaye tant bien que mal de faire fonctionner mon algorithme mais sans succès :mur:

Je vais me renseigner pour ce qu'il en est des contrainte.

Merci de tes réponses !

[Dlzlogic]

Bonjour coqp-ox,
On en a déjà longuement parlé.
Je crois que tant que vous n'aurez pas dit et expliqué ce que vous voulez faire, on n'arrivera à rien.
Par exemple :
- quelles sont le données de base ?
- quels sont les notions, caractéristiques mathématiques indispensables ? il y a déjà eu un indice : les tangentes horizontales au début et à la fin. Vous avez dit le cycle, ne serait-ce pas plutôt le processus ?
- y a-t-il d'autres constantes de base, comme vitesse maximum, accélération maximum ?
- autres points concernant les éléments de base ..
- quelles sont les données à produire, sous quel format ?
- ces données sont à produire en continu, c'est à dire en temps réel, ou à intervalle. Autrement dit, ce sont des données d'exécution (temps réel) ou de préparation ?
- autres points concernant les données à produire ...
- entre les éléments de base et les données à produire, il y a le traitement.
- vous avez parlé l'interpolation : il y a une petite ambiguïté que le sens de ce terme, qu'est-ce que c'est pour vous ?
- en fait quand vous aurez bien défini les éléments de base et les données à produire, la partie intérieure (le traitement) se dessinera d'elle-même.

[coqp-ox]

Bonjour coqp-ox,
On en a déjà longuement parlé.
Je crois que tant que vous n'aurez pas dit et expliqué ce que vous voulez faire, on n'arrivera à rien.
Par exemple :
- quelles sont le données de base ?
- quels sont les notions, caractéristiques mathématiques indispensables ? il y a déjà eu un indice : les tangentes horizontales au début et à la fin. Vous avez dit le cycle, ne serait-ce pas plutôt le processus ?
- y a-t-il d'autres constantes de base, comme vitesse maximum, accélération maximum ?
- autres points concernant les éléments de base ..
- quelles sont les données à produire, sous quel format ?
- ces données sont à produire en continu, c'est à dire en temps réel, ou à intervalle. Autrement dit, ce sont des données d'exécution (temps réel) ou de préparation ?
- autres points concernant les données à produire ...
- entre les éléments de base et les données à produire, il y a le traitement.
- vous avez parlé l'interpolation : il y a une petite ambiguïté que le sens de ce terme, qu'est-ce que c'est pour vous ?
- en fait quand vous aurez bien défini les éléments de base et les données à produire, la partie intérieure (le traitement) se dessinera d'elle-même.

Je vais essayer de répondre précisément et dans l'ordre à vos questions.

- Les données de bases sont les points donnés par l'utilisateur (qui sont "triés" ensuite si nécessaire).
- Les données à production sont des splines définies pour chaque intervalle entre les points (j'éditerai quand je connaitrai le format)
- Je n'ai pas bien compris le terme "à intervalle" mais je suppose que ce sont des données puisqu'après obtention elles n'ont plus besoin d'etre modifiées
- L'interpolation dans le cas présent consisterait à faire passer une fonction (en l'occurence composée de plusieurs splines) par chacun des points, et qui serait de classe C²

Voila, j'espère que j'ai bien répondu à vos questions et que vous serez en mesure de m'aider.

[Dlzlogic]

Sauf le fait que cette liste de points sera traité au moment du traitement, que représentent ces points ?
Par exemple pour chaque point, l'X pourrait être un temps et l'Y une vitesse : c'est ça qu'il faudrait préciser, pour qu'on comprenne.
L'utilisateur donne ces points, où les trouve-t-il ?

Il faut s'entendre sur le vocabulaire : une spline est une ligne constituée d'arcs. Une spline cubique est une suite d'arcs représentatifs de fonctions de degré 3. C'est ce qu'on appelle une fonction définie par morceaux. Il faut 4 points pour déterminer un tel arc. Comme on peut considérer que le dernier point d'un arc sera aussi le premier point de l'arc suivant, pour une ligne donnée, le nombre d'arcs sera égal au nombre de points divisé par 3.

Donc, si j'ai bien compris, il ne s'agit pas d'un traitement en temps réel, mais il s'agit de préparer des données.

Tant qu'on ne saura pas ce que représentent les données fournies par l'utilisateur, où il les trouve, pourquoi il risque de fournir une liste supérieure à 32 points etc., on ne pourra pas continuer. Que la liste doive être simplifiée pour être, au plus, longue de 32 points est un tout autre problème dont ou pourra parler quand on saura d'où viennent ces points et ce qu'ils représentent.

[coqp-ox]

L'utilisateur qui utilise ce programme doit fournir une liste de points (position axe maitre, position axe secondaire)

Je me suis peut-etre mal exprimé. L'axe maitre est un arbre qui troune à une vitesse constante, sa circonférence est divisée en une certaine quantité d'incréments (par exemple 360), de même pour l'axe secondaire (on prendra 360 aussi mais ils ne sont pas forcément identiques)

Un point (x,y) par exemple (90,180) signifie que lorsque l'axe maitre aura fait un quart de tour (90e incrément) alors l'axe secondaire aura lui fait un demi-tour (180e incrément)

L'utilisateur défini en gros le mouvement que doit adopter l'axe secondaire quand l'axe maitre tourne à vitesse constante

[Sylviel]

Il faut 4 points pour déterminer un tel arc. Comme on peut considérer que le dernier point d'un arc sera aussi le premier point de l'arc suivant, pour une ligne donnée, le nombre d'arcs sera égal au nombre de points divisé par 3.

Faux. Il y a 4 paramètres pour chaque arc, il faut donc 4 conditions (indépendantes).
Pour un arc "intérieur" entre a et b il y a :
- la donnée de f(a)
- la donnée de f(b)
- la donnée de f'(a)
- la donnée de f"(a)

les deux dernières étant obtenues à partir de la dérivée première et seconde du morceau de spline précédent. C'est ce qui fait que la fonction est C². (J'en ai déjà parlé ici : http://www.maths-forum.com/condition-f-x-une-interpolation-spline-cubique-147773.php)

Il reste, sur l'ensemble de la spline 2 paramètres à fixé, qui sont donnés (par exemple) par deux éléments parmis : la dérivée au premier point, la dérivée au dernier point, la dérivée seconde au premier point, la dérivée seconde au dernier point.

le nombre d'arcs sera égal au nombre de points divisé par 3

Et donc ceci est faux aussi : si on veux une fonction C² le nombre d'arc sera égal au nombre de points -1.

[Dlzlogic]

Bon, si on sait que la vitesse de l'axe maitre est constante et que la vitesse de l'axe secondaire ne peut varier que très peu pendant un court instant, le rapport x/y est un rapport de vitesse, donc une coordonnées, il en manque une autre pour faire un point.
@ Sylviel, lu ton message, je te laisse la main.

[coqp-ox]

Bon, si on sait que la vitesse de l'axe maitre est constante et que la vitesse de l'axe secondaire ne peut varier que très peu pendant un court instant, le rapport x/y est un rapport de vitesse, donc une coordonnées, il en manque une autre pour faire un point.

Je n'ai pas compris, il suffit d'avoir la position d'un axe et celle de l'autre pour avoir un point non ?

Edit : Pour la première partie j'essaye encore de me débrouiller pour mon code mais sans réussite, voila ce que ca donne...

Code: Tout sélectionner

#include
#include


const int m = 2;
const int a = 3;
using namespace std;

int main()
{
    int n;
    double r=10,u,v,w ;

    cout > n;
    double t[n][m];
    int i, j, k;
    for (i=0; i> t[i][j];

        }
    while (n>a)
    {

        i=-1;
        k=0;
        i++;
        u=abs((t[i][0]-t[i+1][0]));
        u=u/t[i][0];
        u=u*100;
        v=abs((t[i][1]-t[i+1][1]));
        v=v/t[i][1];
        v=v*100;
        w=(u+v)/2;

        if  (r<=w)
        {
            t[k][0]=t[i][0];
            t[k][1]=t[i][1];
            k++;
            n=n-1;
        }

        else
        {
            r=r+0.5;
        }
    }

    cout<<"Voici le tableau :"<<endl;
    for (i=0; i<n; i++)
    {
        for (j=0; j<m; j++)
            cout<<"|"<<t[i][j] <<"|";
        cout<<endl;
    }
}

[fatal_error]

J'ai pas trop regardé ton algo encore, mais voilà deux trois bonnes pratiques que tu peux appliquer pour voir ou tu as mal codé:

1)

Code: Tout sélectionner

    for (i=0; i> t[i][j];//on s'en tape de saisir les points, pour l'instant on
        //les hardcore stupidement, quand ca marchera on pourra proposer de les
        //saisir
    }


2')

Code: Tout sélectionner

double t[3][2];//on remplit arbitrairement
t[0]={1,2};
t[1]={3,2};
t[2]={1,5};


3)

Code: Tout sélectionner

//i n'est modifié nulle part ailleurs, donc en gros il vaut toujours 0 dans la
boucle while..
        i=-1;//devrait etre en dehors de la boucle while
        k=0;
        i++;


4)

Code: Tout sélectionner

//renommes m en dimension, enfin, un nom explicite...
        u=abs((t[i][0]-t[i+1][0]));
        v=abs((t[i][1]-t[i+1][1]));


5)

Code: Tout sélectionner

//es tu sur de vouloir prendre la norme1 pour calculer la distance entre deux points consécutifs?
//sinon u=pow(t[i][0]...) v=pow(t[i][1]...) w=sqrt(u+v)
        w=(u+v)/2;


6)

Code: Tout sélectionner

    //plus grave. tant que n>a, idem n>3, tu boucles.
    //en particulier, pour arriver à n==3, si mettons n=6, tu vas boucler pour
    //n=6, n=5,n=4,n=3, idem tu auras bouclé au moins 4 fois.
    //MAIS, imagine qu'à chaque fois, tu rentres dans le else.
    //tu vas boucler plus de 4 fois, et si tu as le malheur de boucler 7 fois,
    //i va dépasser la taille de ton tableau t, et c'est comportement non défini.
    while (n>a)


Cette partie là de l'algorithme est à revoir.

Hormis ton algorithme qui est faux, (du coup) voilà une version plus lisible et plus utile pour debugger.

Code: Tout sélectionner

const int m = 2;
const int a = 3;
//normalement on veut plus avoir une variable du genre: nombreDePointsAGarder
using namespace std;

int main()
{
    int n;
    double r=10;
    double point[2]={0,0};
   
    //saisir plus tard
    n=3;
    double t[3][2];//on remplit arbitrairement
    t[0]={1,2};
    t[1]={3,2};
    t[2]={1,5};
    //--fin saisir plus tard
   

    i=0;
    while (n>a && i<n)//noter i<n
    {

        k=0;
        //normalement ce bloc de code devrait etre un appel de fonction:
        //calculerDistance(t,i,i+1);//qui retourne la valeur de w
        for(j=0;j<m;++j){
          point[j]=abs((t[i][j]-t[i+1][j]));
          point[j]/=t[i][j];
          point[j]*=100;
        }
        //fin bloc
        w=(u+v)/2;

        if  (r<=w)
        {
          //de meme ce bloc devrait etre un appel:
          //inplaceCopy(t,i,k)
          for(j=0;j<m;++j){
            t[k][j]=t[i][j];
          }
          //fin bloc
          k++;
          n=n-1;
        }

        else
        {
            r=r+0.5;
        }
        i++;
    }
//blabla
}


J'ai pas trop regardé les fautes de syntaxes mais ca devrait etre pas trop mal.
Les modifications ci-dessus, peuvent donner des cas ou tu auras rien remplacé dans t.

Mais comme j'ai pas trop compris ton algo... et ce à quoi il doit répondre, je peux pas le critiquer.

edit: j'ai lu la description de ton algo genre la mais en fait ton algorithgramme est faux parce que tu testes n<32, sauf que tu modifies jamais n...
donc tu t'arreteras jamais de boucler

[fatal_error]

Une autre idée d'algorithme, c'est de faire du clustering sur 32 groupes.
Suppose que tu veux pas 32 points mais 3 points.
En entrée tu as 5 points.

Tu crèes trois groupes:
A:p1
B:p2
C:p3,p4,p5

Tu calcules la distance intergroupe par :
M représente un groupe quelconque, donc A,B, ou C
k représente le nombre de points du groupe M, donc k=1 pour A et B, k=3 pour C
d(M) = somme_k(distance(p_m,p_m+1))/k

Code: Tout sélectionner

Faire
  ilYaEuDeLaction=false
  Pour tous les groupes, groupe courant est (C)
   Si le groupe suivant (S) a un seul point
    // tu passes au suivant
   Sinon
    Tu essaies de prélever des points de S et de les ajouter à C avec un critere:
    Faire
      Soit P le premier point de S.
      Si CriterePourBougerPSatisfait(C,S,P)
        Prélever P de S et l'ajouter à C
        ilYaEuDeLaction=true
      Finsi
    TantQue on a prélevé un point de S pour l'ajouter dans C
    //il n'y a pas/plus de points à prélever de S pour C, passer au groupe suivant
   Finsi
  FinPour
TantQUe il y a eu de laction


Avec
CriterePourBougerPSatisfait(C,S,P):
 oldDistanceInterGroupeC=d(C)
 oldDistanceInterGroupeS=d(S)
 newDistanceInterGroupeC=d(C+P)
 newDistanceInterGroupeS=d(S+P)
 si la distanceInterGroupe de S diminue plus que l'erreur intergroupe de C n'augmente
  retourner true
 sinon
  retourner false
Finprocedure


Au final, tu récupère les 32 groupes, avec des points plus ou moins rapprochés.
L'idée c'est juste t'en prends un au milieu de chaque groupe, et tu récupères ainsi
tes 32 points plutot répartis.

L'algo est pas super optimisé, en gros, tu vas déplacer des points de la droite vers la gauche en les changeant de groupe.
je suis un peu fatigué/pas capable de faire un calcul de complexité, mais en gros pour 100 points ca ira. Faut voir combien t'en as à trier

Il faut voir également comment tu définis la distance intergroupe, ici, c'est l'erreur relative, on sent bien que un mega groupe, si tu lui enleves un element sa distance intergroupe va pas beaucoup bouger, alors que le groupe d'un element si tu lui en ajoute un, oui, du coup, tu vas jamais bouger d'élément.

Faut approfondir un peu les clusters...
par exemple le classique kmeans

[coqp-ox]

Merci pour tes commentaires Fatal, je vais regarder ca en détail !

J'ai réussi à obtenir quelques informations supplémentaires. Dans un premier, l'algorithme est effectué par le pc.

On doit avoir, en sortie de celui-ci, les coefficients des différents polynomes (et pas la fonction entièrement écrite, mais le principe est le même).

La contrainte des 32 points tiens toujours, en fait le programme du variateur a besoin de polynomes définis sur des intervalles mais ne peut pas contenir + de 32 intervalles(segments).

Edit : J'ai lu ton deuxième message, et je ne pense pas que ca convienne à mon problème puisque je dois obligatoirement prendre des points donnés par l'utilisateur (puisqu'ils représentent les positions exactes qu'il désire pour l'axe secondaire)

[fatal_error]

ben si tu prends 32 points parmi les n de l'utilisateurs, k means marche très bien. Tu prends un point de chaque groupe..
je dis pas que c'est la solution vers laquelle s'orienter, c'était juste une proposition genre alternative potentielle

par exemple,..., en cherchant kmeans C sur google.
Et un bon vieux copier coller plus du défoncage de code:

Code: Tout sélectionner

/*****
**http://www.google.fr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&cad=rja&ved=0CE4QFjAE&url=http%3A%2F%2Fcs.smu.ca%2F~r_zhang%2Fcode%2Fkmeans.c&ei=LPeYUp7yOcyX7QaB2oCoDw&usg=AFQjCNHC9s6WD3_GIZTFpLRFpaLljDJ7YQ&sig2=zlR_-sWMR4EwM58VPaJFXw&bvm=bv.57155469,d.ZGU
** kmeans.c
** - a simple k-means clustering routine
** - returns the cluster labels of the data points in an array
** - here's an example
**   extern int *k_means(double**, int, int, int, double, double**);
**   ...
**   int *c = k_means(data_points, num_points, dim, 20, 1e-4, 0);
**   for (i = 0; i
#include
#include
#include
#include

#define N 10
#define DIM 2
int *k_means(double data[N][DIM], int k, double t, double **centroids)
{
   int n=N;
   int m=DIM;
   /* output cluster label for each data point */
   int *labels = (int*)calloc(n, sizeof(int));
   int h, i, j; /* loop counters, of course :) */
   int *counts = (int*)calloc(k, sizeof(int)); /* size of each cluster */
   double old_error, error = DBL_MAX; /* sum of squared euclidean distance */
   double **c = centroids ? centroids : (double**)calloc(k, sizeof(double*));
   double **c1 = (double**)calloc(k, sizeof(double*)); /* temp centroids */

   assert(data && k > 0 && k  0 && t >= 0); /* for debugging */

   /****
   ** initialization */

   for (h = i = 0; i  0; c[i][j] = data[h][j]);
   }

   /****
   ** main loop */

   do {
      /* save error from last step */
      old_error = error, error = 0;

      /* clear old counts and temp centroids */
      for (i = 0; i  0; distance += pow(data[h][j] - c[i][j], 2));
            if (distance  0; c1[labels[h]][j] += data[h][j]);
         counts[labels[h]]++;
         /* update standard error */
         error += min_distance;
      }

      for (i = 0; i  t);

   /****
   ** housekeeping */

   for (i = 0; i < k; i++) {
      if (!centroids) {
         free(c[i]);
      }
      free(c1[i]);
   }

   if (!centroids) {
      free(c);
   }
   free(c1);

   free(counts);

   return labels;
}
int main()
{
  double t[N][DIM]={
    {0.5,-2.5},{1.5,-2.5},{2.5,-2.5},{4,-1.5},{4,3},
    {2,4}     ,{-0.5,5}  ,{-2,3}    ,{-2,0}  ,{-1,-1}
  };
  int k=3;
  double errorTolerance=0.0001;
  int *labels=NULL;
  labels = k_means(t, k, errorTolerance, NULL);
  int i;
 
  for (i = 0; i < N; i++) {
    printf("data point %d is in cluster %d\n", i, labels[i]);
  }
  free(labels);
  return 0;
}



output:

Code: Tout sélectionner

$ gcc main.c &&  ./a.out         21:56
data point 0 is in cluster 0
data point 1 is in cluster 0
data point 2 is in cluster 1
data point 3 is in cluster 1
data point 4 is in cluster 1
data point 5 is in cluster 2
data point 6 is in cluster 2
data point 7 is in cluster 2
data point 8 is in cluster 0
data point 9 is in cluster 0


Les points que j'ai saisis sont en gros un cercle tracé à la mano, plus une lecture vite fait des coordonnées. Ce qui explique pourquoi point 0,1,8,9 sont dans le même cluster.

il faut noter que ca marche sur l'assomption que dans le temps on repasse pas par le même point (sauf si on boucle). Du coup, les groupes qui se font sont cohérents temporellement parlant. (idem on va avoir uniquement des points accolés dans le temps dans un même groupe) mais par sécurité, dans
/* identify the closest cluster */
on devrait pas chercher dans tous les clusters, mais uniquement dans le cluster du point d'avant, le cluster courant, et le cluster du point d'apres

[Ben314]

La contrainte des 32 points tiens toujours, en fait le programme du variateur a besoin de polynomes définis sur des intervalles mais ne peut pas contenir + de 32 intervalles(segments).

Salut,
C'est pas bien mon domaine et fatal sera bien plus à même de t'aider que moi, mais il y a quand même un truc qui me turlupine : vu la limite de stockage de ton robot à 32 segments, tu es sûr qu'il faut éliminer les points suplémentaires donné par l'utilisateur ?
(j'aurais trouvé ça plus logique de les garder et de les envoyer au robot lorsque son "buffer" de segments commence à se vider).

bon, aprés, moi je dit ça, je dit rien...

[fatal_error]

slt Ben,

en fait dans l'image que j'ai en tete, c'est genre:
les gars ont une machine (genre un bras robot).
Pis l'utilisateur il prend des positions dans le temps du bras robot.
Puis il file ces points à un programme.

Et le programme il donne 32 objets qui représentent des splines.
Jusqu'à maintenant j'ai fait l'hypothèse que:
soit le programme est hosté sur le pc, soit il est hosté sur le robot, mais que dans tous les cas une fois les points donnés par le client, les 32 splines ne seront plus modifiables (sans intervention de l'utilisateur (et bien sûr que l'intervention de l'utilisateur est pénalisante pour le bon fonctionnement du robot).
Après effectivement, si le programme est hosté sur le robot, et que le robot est easy en mémoire, il peut envoyer de temps en temps 32 points au servo!

ps: c'est pas du tout mon domaine non plus :we: