Tracer une droite dans un quadrillage

Bonjour,

je fais appel à vous car je suis en face d'un problème, et je ne sais pas quels sont les outils Python avec lesquels je peux le résoudre... Je m'explique :

On considère un mobile qui se déplace dans un espace 2D. On discrétise cet espace par pas de 1 mètre (par exemple), on obtient donc un quadrillage (une matrice en fait). Toutes les secondes, on récupère une information sur le mobile : une direction, en degrés, qui correspond à la direction probable d'une antenne émettrice (je ne m'étends pas sur le sujet, on sait que l'on peut récupérer cette info).

J'aimerais pouvoir, à chaque seconde, tracer une droite dans mon quadrillage correspondant à la direction récupérée, et incrémenter de 1 chacune des cases que ma droite traverse. Ainsi, si on répète ce procédé sur plusieurs secondes, on sait que les cases qui ont la plus grande valeur correspondent à l'endroit le plus probable où se trouve mon antenne émettrice.

Comment puis-je résoudre un problème pareil sous Python ? Y a-t-il des outils adaptés pour le traiter (c'est un problème plus "graphique" que calculatoire...) ?

Merci d'avance pour votre réponse. :)

Salut,

Citation:

---

Envoyé par AladdinSane

Comment puis-je résoudre un problème pareil sous Python ? Y a-t-il des outils adaptés pour le traiter (c'est un problème plus "graphique" que calculatoire...) ?

---

Toutes les bibliothèques graphiques ont un objet de type canvas qui permet de dessiner rectangles et lignes. Vous pouvez utilisez la bibliothèque standard tkinter ou installer celle de votre choix.

- W

Bonjour,

on considère une grille définie par les vecteurs x = [0, 1, 2, ..., 100] et y = [0, 1, 2, ..., 100].

J'ai un point de coordonnées (x₀, y₀), et un angle θ donné (en degrés, pas rapport au nord).

J'aimerais pouvoir récupérer les coordonnées des points composant la droite qui part de (x₀, y₀) avec l'angle θ, et uniquement ceux contenus dans ma grille (autrement dit dont les coordonnées sont entre 0 et 100).

Comment puis-je faire pour obtenir un tel résultat ?

J'avais réussi à obtenir quelque chose, mais ça prend bien trop de temps... En fait, je cherchais un deuxième point que la droite traverse, puis j'appliquais l'algorithme de Bresenham entre ces deux points, mais généralement le deuxième point est en dehors de ma grille alors c'est un peu le bordel, il faut ensuite jeter tous ces points et on les a calculés pour rien... S'il y a une méthode pour ne pas avoir à passer par du Bresenham entre deux points, je suis preneur. :)

D'avance merci.

Je verrais un truc comme ça :
t est l'angle de ta droite

Code:

---

1 2 3 4 5 6 7 8 9 10

pour x = 0 a 100 Delta_x = x-x0 delta_y = delta_x * tan(t) y = y0 + delta_y si y = arrondi(y,0) alors // y est un entier , coup de chance ! print ( x,y ) fin fin

---

A Vérifier. J'hésite entre la fonction tan() ou cotan().
Si ce traitement est trop lent, alors il va falloir réfléchir fortement !
Est-ce que x0 et y0 sont des entiers, ou des nombres quelconques ?
Et je pense que ta question serait mieux dans un sous-forum algorithme ou mathématiques.

Haha, c'est malin, mais il se peut très bien que je ne trouve pas de valeur entière pour y :)

x0 et y0 sont entiers, oui !

Tout à fait , assez souvent, il n'y aura pas de valeurs entières pour (x,y) ; Dans ce cas, il faut en inventer ? en faisant des approximations ?

Bonjour,

Si on considère que la mesure est faite «au centre» de la case, qu'il n'y a pas de marge d'erreur sur la mesure de l'angle alors ta droite traverse une autre case si au moins deux coins sont de part et d'autre de la droite, avec les cas particuliers où la droite ne coupe qu'un coin ou carrément un côté.