+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Algorithme] Trouver tous les couples de coordonées entier d'une droite (/showthread.php?tid=6381)
[Algorithme] Trouver tous les couples de coordonées entier d'une droite - Argorate - 12-09-2012
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:
Citation :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 ! ^^
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Argorate - 12-09-2012
Voilà, on m'a aider à trouver l'algorithme: http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_segment_de_Bresenham
Qui m'a permis de dénicher l'implémentation php : http://alex.moutonking.com/wordpress/?p=44
Si ça peut aider
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Sephi-Chan - 12-09-2012
Cool. Peut-être qu'un sujet épinglé listant divers algorithme récurrents (avec leur explication et leurs implémentations) serait intéressant.
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Argorate - 12-09-2012
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 !
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - niahoo - 12-09-2012
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.
![[Image: Bresenham.svg]](http://upload.wikimedia.org/wikipedia/commons/a/ab/Bresenham.svg)
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Argorate - 12-09-2012
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
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Angelblade - 13-09-2012
Merci beaucoup pour le partage, ça seras utile un jour
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - St_Machine - 13-09-2012
Oui c'est vrai que ça me sera utile aussi, merci
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - Argorate - 22-11-2012
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.
RE: [Algorithme] Trouver tous les couples de coordonées entier d'une droite - php_addict - 22-11-2012
tu peut pas les trier toi même au lieu de chercher une nouvelle implémentation?