[Algorithme] Trouver tous les couples de coordonées entier d'une droite

[Argorate]

Bonjour,

j'aurais besoin de savoir si l'un de vous dispose d'un algorithme qui permet de trouver tous les couples de coordonnées entier d'une droite lorsqu'on donne un couple (x1;y1) de départ et un autre (x2;y2) d'arrivé en paramètre.

Pour contextualiser la chose:

j'ai besoin de savoir sur mon jeu si je prend deux cases séparé, de connaitre toutes les cases sur le chemin qui sépare les deux (c'est à dire la droite relié le point de départ et d'arrivé).
Bien sur, en ligne droite ou diagonale, c'est facile, tout le probleme est lorsque la droite est "de biais".

Exemple:

Point A
x1 = 3
y1 = 1

et

Point B
x2 = 9
y2 = 5

(prenez un papier et un crayon si c'est plus visuel)

L'algo doit donner la réponse suivante:

4 ; 1
4 ; 2
5 ; 2
5 ; 3
6 ; 3
7 ; 3
7 ; 4
8 ; 4
8 ; 5
9 ; 5

En gros, il me faut toutes les cases par lequel la droite imaginaire (reliant le Point A et le Point B) passe.

Ceci étant, j'aurais besoin d'une fonction générique qui ne soit pas borné à un système orthonormé, puisque sur mon jeu ce n'est pas le cas, les y vont dans le positif vers le bas et non vers le haut.
Donc histoire de compliqué un peu plus, il faudrait un paramètre précisant le sens des axes du repère.

Je pense qu'un tel algo pourrait servir a pas mal de monde, donc si vous en connaissais un ou pouvez et voulez en partager un, n'hésitez pas ! ^^

[Argorate]

Voilà, on m'a aider à trouver l'algorithme: http://fr.wikipedia.org/wiki/Algorithme_..._Bresenham

Qui m'a permis de dénicher l'implémentation php : http://alex.moutonking.com/wordpress/?p=44

Si ça peut aider

[Sephi-Chan]

Cool. Peut-être qu'un sujet épinglé listant divers algorithme récurrents (avec leur explication et leurs implémentations) serait intéressant.

[Argorate]

En effet, car je ne doutais pas qu'il existait un algo, mais quand tu connais pas le nom, là ça pourrait aider en effet !

[niahoo]

Tu t'en fous que les Y soient positifs vers le bas ou le haut, les coordonnées concordent toujours


Attention, comme on peut le voir cela ne retourne pas exactement toutes les cases.

[Argorate]

Oui, j'ai découverts ça avec l'algo, le repère n'a pas d'importance, et je cherchais justement un algo qui admet une marge d'erreur comme celui-ci le fait puisque je vais l'utiliser pour le champs de vision de mes joueurs^^

Cet algo est bcp plus rapide que celui que j'avais tenté de commencer et il prend justement pas toutes les cases, ce qui est mieux je pense

[Angelblade]

Merci beaucoup pour le partage, ça seras utile un jour

[St_Machine]

Oui c'est vrai que ça me sera utile aussi, merci

[Argorate]

Hello,

je reviens sur le sujet car j'ai un petit problème à présent, à savoir que l'algo en question ne retourne pas forcement les différents points dans le bon ordre!

En effet j'aimerais que l'ordre des couples x;y obtenu soit toujours depuis x1,y1 vers la cible x2,y2, hors selon la position de la "cible", les coordonnées ne sont pas dans le bon ordres.

Savez-vous s'il existe une implémentation qui conserve l'ordre?

thx.

[php_addict]

tu peut pas les trier toi même au lieu de chercher une nouvelle implémentation?