Coordonée des cellules qui intersectent un segment

[MiniK]

Bonjour,

Je ne suis plus au lycée mais j'ai besoin des mathématiques pour mon travail.

J'ai une grille ou les cellules ont des coordonées.
La grille s'inscrit aussi dans un repere plus grand (le systeme de coordonées Lat-Long), ou je connais les coordonées de chaque coin d'une cellule


J'aimerai savoir si il y a une méthode mathématique simple pour connaitre les coordonées des celulles qui sont sur la trajectoire d'un segment.

regardez le schema si dessou qui représente en faire 2 segments d'une polyligne.



Je pense pouvoir coder tout seul un algorithme pour y arriver, mais si une méthode mathématique sera toujours plus propre et éfficace.

Merci beaucoup pour votre aide.

[Huppasacee]

Bonjour

en fait , ce sont simplement 2 "fonctions affines"
Chacune des 2 lignes sera représentée par une fonction telle que

ax + bx + c = 0

a, b et c seront trois constantes dépendant du segment
Est ce que cela vous aide ?

[MiniK]

En fait je ne connait pas la formule des segments (leur inclinaison).

J'ai seulement 2 points dans l'espace.

Je peut facilement déterminer sur quelle case se trouve chacun des deux points.
Ce que je cherche à determiner c'est toutes les cases qui coupent le segment qui relie ces deux points (les cases que jai colorié en rouge sur le dessin)

Ma méthode serai de :
repérer le restangle dans lequel est inscrit le segment voir dessin) et ensuite calculer pour chaque segment qui compose le coté d'une case faire un test d'intersection.

C'est un peu nul et tres lent. C'est pourquoi je demande si il n'existe pas ue méthode mathématique pour ce genre de problemes

[bombastus]

Bonsoir,

En fait je ne connait pas la formule des segments (leur inclinaison).

J'ai seulement 2 points dans l'espace.

Tu travailles bien dans un plan en 2D? Si oui,tu peux facilement déterminer l'équation de la droite avec ces 2 points. D'ailleurs comment fais-tu tes tests d'intersection si tu ne connais pas l'équation de la droite?

Sinon, je pensais à faire :
pour chaque colonne de ton rectangle global :
pour chaque case d'une colonne, faire des tests d'appartenance car si on a l'équation de la droite et les abscisses des côtés de chaque colonne, on peut calculer les ordonnées minimale et maximale de la droite sur cette colonne.

Je sais pas si c'est très clair, et surtout je sais pas si c'est plus rapide que ta technique, mais si tu veux que je développes, dis-le moi.

[Huppasacee]

Donc, si on connaît deux points du segment par leurs coordonnées

premier point : (i1; j1), avec i en horizontal et j en vertical par exemple

deuxième point : (i2;j2)

et un point quelconque de la droite (i ; j)

ce point appartient au segment si

(j - j1)/(i - i1) = (j2 - j1)/(i2 - i1)

[Luc69]

Si tu as un grand nombre de cellules, tu peux faire ce que l'on appelle un traitement par paquets (buckets en anglais) qui consiste à faire un premier découpage de ton espace en cellules plus grosses.
Un premier traitement permet de déterminer dans quelles "grosses" cellules passe ta droite puis, connaissant les petites cellules contenues dans les grosses, de refaire le traitement uniquement dans ces "grosses" cellules pour déterminer ce que tu cherches.
En cas de grand nombre de cellules (éléments finis par exemple) cela peut considérablement réduire le nombre d'itérations (le nombre optimal de cellules par paquet dépendant de ton système, mais il existe de méthodes simplifiées pour faire grosso-modo).

Le traitement proprement dit doit à mon avis se faire sur les coins hauts gauches des cellules, vérifier si leur coordonnée y est > ou < à ax+b (équation du segment), si c'est supérieur, vérifier si le coin inférieur droit à un y > ou < à ax+b, si il est inférieur alors la droite passe dans la cellule !