Discussion :

[qventura]

Bonjour,
Pour la réalisation d'un projet, je cherche à coder la trajectoire d'une cible, et je cherche la meilleure manière de coder cela.

Mon objet Cible aura un attribut Position Vector3(x,y,z), ou x et y sont les coordonnées sur le plan et z l'étage, ainsi qu'un attribut Trajectory.

Quelle est la meilleure manière de concevoir cette trajectoire ? Sachant que le temps logiciel sera variable, dans le sens ou l'utilisateur pourra naviguer dans le temps t+ et t-.

Il s'agit d'un couple <time t, position p>
Est il mieux de faire une list classique triée par t ? une hashtable indexée sur t ?
1 seule ou deux listes (ici listes est utilisée comme un terme générique) avec les positions à t+ et les positions à t- stockées séparément ?

Autre questions, un peu différentes, mais toujours au sujet de ces trajectoires. En supposant que j'ai une position toutes les 2 secondes par exemples, je voudrais tout de même avoir une trajectoire continue et pas des lignes brisées. Quelqu'un pourrait-t-il m'indiquer un algorithme pour faire cela ? Comme ça je dirai que c'est de "l'extrapolation" mais je suis pas sûr du terme du tout ...

Merci d'avance !

[qventura]

(J'ai probablement pas posté le sujet au bon endroit en fait ...)

Petite réflexion que je fais à moi même:
Si j'utilise une hastable, je stocke les positions a intervalle de temps 2s, soit à:

t-4, t-2, -, t+2, t+4
Quand je serai à t+3 je pourrais pas donc pas y accéder directement par la valeur clé, donc la hashtable est pas forcément la meilleure solution ...

[androz]

Ben je sais pas si c'est la meilleure façon, mais tu pourrais simplement te faire une petite classe ayant la position et le temps du point comme variables. Ensuite, tu fais une liste de points qui constitue ta trajectoire. Comme ça, le temps pourrait être une propriété même et ainsi tu pourrais faire un foreach sur ta liste avec le temps comme paramètre.

Autre chose, si tu prends un temps toutes les 2s et que tu cherches comme tu dis la position au temps t+3, c'est pas bien sorcier, tu fais juste une interpolation linaire sur deux points t+2 et t+4 (une droite qui passe par deux points, ça devrait pas être trop compliqué ).

Enfin, tu dis ne pas vouloir une courbe en ligne brisée.... tous les graphiques sont des graphiques en ligne brisée ! Tout dépend après du pas entre chaque point qui te donne l'illusion d'une ligne continue. Maintenant, si par ligne continue tu entends une courbe lisse, tu peux toujours faire une interpolation de plus haut degré ou avec des polynômes/bases de fonctions plus ou moins exotiques. Une petite recherche sur google te donnera de nombreux exemple, en voici un, le premier que j'ai trouvé :
http://paulbourke.net/miscellaneous/interpolation/

[qventura]

Merci de ta réponse (confrère résidant du Canada )

En fait pour la trajectoire c'est effectivement ce que je comptais faire. Le truc c'est que je me demandais comment la stocker efficacement
C'est supposé être un logiciel robuste qui va traiter pas mal de données. Dans ce cas, j'me vois mal parcourir une liste complete pour trouver la position d'un point. (Par exemple, si on reste sur l'intervalle de temps i = 2s, sur une journée ca fait quand même presque 50000 points sur une journée ...) donc je me demandais qu'est ce qui serait le plus pratique pour accéder aux données rapidement. (D'ou ma remarque sur les hashtable d'ailleurs)

Pour ce qui est de la trajectoire en elle même, effectivement ca serait une ligne brisée, j'voudrais juste que ça soit le moins visible possible et je connais pas les spécificités back office exactes (l'intervalle de temps en fait) Donc ouais ca sera surement de l'interpolation ! Merci d'ailleurs, je connais pas du tout je savais pas si c'était le terme que je devais chercher

[androz]

Salut !

Tu dis vouloir accéder rapidement aux données... 50000 points c'est pas tant que ça non plus, ça se fait assez rapidement. Maintenant si tu veux aller chercher exactement la valeur disons à 12h 34min 04s, ben t'as juste à compter le nombre d'intervalles de 2s depuis le début de la journée ! Je pense qu'utiliser une hashtable n'est pas nécessaire du tout.
Par curiosité, tu parles de back office..... ton code c'est pour une institution financière ?

Après, quand on parle que ce soit le moins visible possible (ta ligne brisée), c'est donc juste une question de tracé, ce n'est plus remplir les trous comme je pensais au début. Dans ce cas, il te suffit d'utiliser le bon "style" de graphique. Par exemple, si tu utilises MSChart, plutôt que de tracer une Line ou Fastline, tu traces une Spline qui fait en réalité une interpolation cubic pour relier les points et donne une apparence plus lisse.

J'espère que ça t'aide un peu, si t'as besoin, hésites pas, tu peux aussi me joindre par MP.

[DonQuiche]

Je rejoins Androz : 50k points... Osef, pas besoin de se poser de questions de performances, il faut simplement chercher à faire le code le plus simple et clair, et le mieux conçu.

Maintenant, pour le plaisir de la discussion, une structure type hastable nécessiterait pour récupérer M points parmi N une complexité o(M.log(N)), tandis qu'un simple parcours sera grosso modo en N/2 : les deux ne sont pas très éloignés. Or, comme la hastable implique le calcul de hashcodes et une plus lourde empreinte en mémoire, pour un problème possiblement bandwidth-bound, je paries que le parcours serait finalement plus rapide. Le must serait un tableau trié avec recherche binaire, à condition que le tableau soit lu assez souvent pour compenser le coût du tri initial.

Mais encore une fois : osef. 50k points ne méritent pas que perde du temps à se poser la moindre question.

[qventura]

En fait j'ai dit 50k mais ca peut être relativement beaucoup plus ... Le backoffice (j'utilise le terme backoffice pour parler du moteur en fait, tout ce qui tourne derrière et qui entre autre rempli la bdd) tourne 7/7 24/24 donc le nombre de points possiblement à afficher est assez énorme ...

Mais je pense que je vais m'imposer un certain intervalle de temps à afficher (comme 2h) et accéder à la base de données pour récupérer les infos quand j'arrive dans une zone de temps critique ... Quelqu'un pourrait me donner le terme pour ça d'ailleurs ? Quand on charge qu'une partie des données, puis quand on arrive proche de l'extrémité de la plage de données qu'on vient de charger et qu'on veut charger la suite ?

Et donc non ça n'est pas pour une institution financière, c'est vraiment pour afficher des trajectoires physiques sur un plan (Des déplacements de "cibles" en fait)

Merci de vos réponses en tout cas

[DonQuiche]

Quelqu'un pourrait me donner le terme pour ça d'ailleurs ? Quand on charge qu'une partie des données, puis quand on arrive proche de l'extrémité de la plage de données qu'on vient de charger et qu'on veut charger la suite ?

Je ne sais pas à quoi tu songes, il n'y a pas de pattern pour ça il me semble. A tout hasard, les termes lazy loading, curseur, fenêtre, page me viennent à l'esprit mais...

[olivieram]

Bonjour,
La trajectoire des points doit être couplée en fonction du temps. Je veux dire que c'est un Dictionary<datetime, Vector3>. Il n'y a que cette solution et c'est la plus pratique.

[olibara]

must serait un tableau trié avec recherche binaire, à condition que le tableau soit lu assez souvent pour compenser le coût du tri initial.

Ben a mon avis la Liste est triée par nature puisque si j'ai bien compris elle grandit dans un intervalle de temps défini et que le temps sera l'index de recherche

Et comme le suggerait Andros, si un connait le temps T0 et l'intervalle on peut presque faire de l'acces direct dans une liste

[olivieram]

Bonjour,
J'ai dis Dictionary<datetime, Vector3> parce qu'un objet que l'on lance va lentement quand il monte et va beaucoup plus vite quand il descend => temps non linéaire.

[DonQuiche]

Ben a mon avis la Liste est triée par nature puisque si j'ai bien compris elle grandit dans un intervalle de temps défini et que le temps sera l'index de recherche

Oui, oui, simplement à l'époque du message que tu as cité l'info n'avait pas encore été donnée.

[olibara]

Oui, oui, simplement à l'époque du message que tu as cité l'info n'avait pas encore été donnée.

Et pourtant ...
Si tu relis bien !

[DonQuiche]

Je viens de relire et nada, la mention d'une DB contenant les points déjà triés n'apparaît qu'au message #7.

[qventura]

Je pensais pas que ça serait un topic sujet à débat !

Donc oui, il s'agit grosso modo d'un couple < DateTime, Object > (L'objet est pas défini concrètement, pour le moment effectivement il s'agit juste des positions X, Y et Z, mais d'autres information se rajouteront)

Je suppose que les informations seront tirées d'une DB ! Mais j'en ai pour le moment aucune idée. On va partir sur le principe que les données seront triées à la base, au pire j'adapterai le prototype si c'est pas

Pour ce qui est du temps non-linéaire c'est pas tout a fait vrai olivieram. En fait il s'agit plus d'un "chemin" que d'une trajectoire, il s'agit des trajectoires de déplacement de personnes / objet ... La position des émetteurs est captée par intervalle de temps régulier par un récepteur. En gros toutes les X+E secondes j'ai une position pour un points ... C'est ce petit E qui fait que le temps sera non linéaire, parce que le matériel est pas forcement fiable a 100% donc les intervalles de temps peuvent varier légèrement, du fait que j'peux pas considéré des intervalles consécutifs comme ayant des clés t0, t0+X, t0+2X, etc ... Et je peux donc pas accéder directement en calculant l'index par rapport au temps. Donc tu avais raisons au sujet de la non linéarité
Donc pour faire simple, les points sont triés, mais pas régulier ...
J'vais regarder du côté des dictionnary, merci !


Pour le pattern dont je parlais précédement, je pense que c'est quelque chose d'assez répendu quand même ! J'arrive peut être pas à trouver le bon terme ...
Ca serait comme du chargement itératif ? Ou du pré-chargement ?
Au lieu d'avoir un seul accès a la base de donnée ou je charge tout, je charge qu'une petite plage de données et quand j'arrive aux limites de cette plage (comme à 75%) je refais une accès à la base de donnée sur une nouvelle plage ... Ca évite d'avoir trop d'accès à la DB et d'avoir trop de mémoire utilisée aussi ... Je suis tellement pas clair ?

Merci de votre attention en tout cas !

[DonQuiche]

@qventura
Si, si, tu es tout à fait clair. C'est juste qu'à ma connaissance ça n'a pas de nom bien précis même si on peut toujours lui mettre des étiquettes comme lazy loading ("chargement paresseux" en français, me semble t-il).

Pour le dictionnaire, non, ce n'est vraiment pas une bonne idée (clés triées par hashcode).

Restes-en donc au bon vieux tableau trié comme je te le suggérais avec un algo dichotomique (plus précisément des tableaux chaînés vu que tu chargeras dynamiquement les plages). Essaie tout de mêem de savoir exactement quelles seront tes contraintes (nb de données, DB ou non) mais ne cherche à faire de l'optimisation prématurée : utilise des abstractions afin de te laisser des possibilités pour optimiser le code ultérieurement (changer de structure de donnée), tu verras bien si des problèmes se posent. Au pire tu voudras peut-être évoluer vers une skiplist, voire un arbre si tu as besoin d'insérer des valeurs rapidement à des positions arbitraires. Mais j'insiste sur le fait que la bonne structure de données dépendra de tes scénarios et contraintes.

[olibara]

J'vais regarder du côté des dictionnary, merci !

Inutile et meme "encombrant" ici
Comme il a déja été dit : un parcours de 50K objet dans une liste c'est tres rapide
Et si tu veux rafiner, meme si ta linéarité n'est pas parfaite tu peux certainement facilement definir une "fenetre" d'inspection dans ta liste

[qventura]

@DonQuiche: Parfait je vais regarder du coté du lazy loading donc ! En fait je vois très bien comment l'algorithme va fonctionner, ça devrait vraiment pas être compliqué ... C'est juste pour voir si des études ont été faites pour voir le rapport optimal (quel taille de plage et quelles limites choisir en fait

@Tous: Ok donc je vais rester sur les listes avec un algorithme solide pour la recherche effectivement en fait, même si c'est pas linéaire, j'dois pouvoir trouver l'index à +- 1 assez facilement ...

Merci de vos conseils en tout cas !