DÉTECTION D'INTERSECTION DE DEUX LIGNES
cs_bali_balo
Messages postés
1378
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010
-
21 oct. 2007 à 14:30
top30 Messages postés 1158 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 6 août 2010 - 27 oct. 2007 à 02:04
top30 Messages postés 1158 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 6 août 2010 - 27 oct. 2007 à 02:04
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/44449-detection-d-intersection-de-deux-lignes
https://codes-sources.commentcamarche.net/source/44449-detection-d-intersection-de-deux-lignes
27 oct. 2007 à 02:04
26 oct. 2007 à 23:12
Pour savoir comment on détermine si un point est sur un segment...
MMDDRR!
bali_balo....=]
26 oct. 2007 à 23:03
exact (j'ai pris mon crayon pour vérifier ;) )
26 oct. 2007 à 22:04
Donc le gagnant est : SLAGT !
26 oct. 2007 à 22:03
public function hitTest ($oP1 : Point, $oP2 : Point, $oP3 : Point )
: Boolean{
var n :Number= ($oP3.x - $oP1.x) / ($oP2.x - $oP1.x ) ;
return !( n< 0 || n > 1 ) ;
}
Sachant que l'on cherche à savoir si le point est sur un segment de droite !
26 oct. 2007 à 22:01
et y est compris dans l'intervalle défini par les ordonées des extrémités du segment
alors le point (x,y) est sur le ségment.
Faux :) En fait, si les deux expressions sont comprises entre 0 et 1, le point est compris dans le rectangle défini par le segment (qui est sa diagonale). Le point appartient au segment si et seulement si, ces deux expressions sont égales.
>> ça serait pas de l'algèbre de base sur les intervalles et un peut de géométrie dans le plan tout ça ?
Si si, juste deux façon, identique dans le fond, de voir les choses.
26 oct. 2007 à 18:22
"l'équation d'une courbe de bézier linéaire [...]
"(X3 - X1) / (X2 - X1)
et (Y3 - Y1) / (Y2 - Y1)
Avec {X1, Y1} les coordonnées du point 1
{X2, Y2} les coordonnées du point 2
{X3, Y3} les coordonnées du point à tester (3)"
ça serait pas de l'algèbre de base sur les intervalles et un peut de géométrie dans le plan tout ça ?
si x est compris dans l'intervalle défini par les abscisses des extrémités du segment
et y est compris dans l'intervalle défini par les ordonées des extrémités du segment
alors le point (x,y) est sur le ségment.
bref, les vraies questions (aux quelles je suis sur que top30 va répondre ;)):
-1) quel est l'algorythme le plus simple à coder ?
-2) quel est l'algo le plus performant ?
ce qui répondra à :
"En passant si quelqu'un type "AFAD", pouvais me donner la fonction permettant de savoir si un point fait partit d'un segment... Je me permettrais de lui retourner "au propre" ! "
26 oct. 2007 à 15:30
Ce que tu dis est vrai, mais tu pars de zéro ! Les maths c'est aussi savoir partir de ce qui a déjà été fait pour aller plus vite, et surtout pour que ceux qui n'y comprennent rien puisse y comprendre enfin quelque chose.
Les courbes de béziers sont absolument génial ! Elle permette de tracer une courbe "propre" d'un point à un autre en se rapprochant vaguement de ceux qu'on a mis entre les deux. C'est l'outils "plume" de Photoshop ou de Flash... Mais quand on a que 2 points, ça trace une simple droite.
L'avantage des courbes de bézier, c'est qu'elles ne sont pas définie en fonction des coordonées, mais en fonction d'un paramètre, "t", qui varie de 0 à 1. Quand t=0, on est sur le premier point, quand t="1", on est sur le dernier point.
Wikipédia (notre ami commun ;)), nous donne, pour 2 points, que l'équation d'une courbe de bézier est (on travaille avec des points, donc dans flash il faudra 2 équations en réalité, une avec X, et une avec Y, chacun remplacant simplement P dans l'équation) :
P3 = (1-t)*P1 + t*P2 (pour tout t de 0 à 1)
Donc logiquement, si P3 appartient au segment, on a P3 = (1-t)*P1 + t*P2
On se débrouille pour isolé t, et on trouve que t = (P3 - P1) / (P2 - P2)
Or on sait que t est compris entre 0 et 1, donc on a aussi (P3 - P1) / (P2 - P2) compris entre 0 et 1.
L'autre condition est logique, puisqu'on a 1 seul "t", donc il est forcément identique dans les 2 équations (ça serait stupide pour un même point, d'avoir un "t" différent selon X ou Y...)
2 façon de voir les choses, au fond... identique, mais bon, ça peut intéresser certains d'entre vous :)
25 oct. 2007 à 23:47
Je te note après test !
25 oct. 2007 à 23:32
25 oct. 2007 à 23:04
- Deux valeur égale
(X3 - X1) / (X2 - X1) = (Y3 - Y1) / (Y2 - Y1)
- Compris entre 0 et 1
0 <= (X3 - X1) / (X2 - X1) <= 1
ou 0 <= (Y3 - Y1) / (Y2 - Y1) <= 1
25 oct. 2007 à 22:56
L'avantage, c'est que le nombre trouvé correspond à la position (en pourcent) du point.
si (X3 - X1) / (X2 - X1) = 0.5, ça veut dire que SUR X, on se trouve à 50% entre P1 et P2
donc si les deux sont égales à 0.5, on se trouve... au milieu du segment :)
25 oct. 2007 à 01:58
24 oct. 2007 à 22:46
(X3 - X1) / (X2 - X1)
et (Y3 - Y1) / (Y2 - Y1)
Avec {X1, Y1} les coordonnées du point 1
{X2, Y2} les coordonnées du point 2
{X3, Y3} les coordonnées du point à tester (3)
23 oct. 2007 à 08:45
fonctionnement, dansla mesure ou la compraison est faite avec des arrondis des distances.
Simple et efficace.
BananaTree, je te remercie de me faire sentir aussi con !
= )
23 oct. 2007 à 00:50
http://fr.wikipedia.org/wiki/Espace_vectoriel
(je pense que BananaTree nous a tous scillé avec sa soluce toute bète et simple à implémenter avec la fonction distance de la classe Point)
shame on us... :P
23 oct. 2007 à 00:10
dixit flash.geom.Point.
(je peux me tromper, j'y entrave que d'alle en math)
22 oct. 2007 à 20:57
Si il etais sympa il nous la traduirais en AS non ?
; )
22 oct. 2007 à 19:29
Tout simplement parce que j'en ai bavé pendant 2 ans en DEUG MIAS :D. C'était limite si c'était pas de la philo... (Soit E un ensemble magma infini compris dans un ensemble infini qui lui est compris dans un ensemble infini....Et f une fonction homomorphisme... PLUS JAMAIS SA!!! :S)
Pourtant c'est vachement interessant! Math & Physique, j'adore, mais loin des théorèmes:P
Sinon toi qui a une méthode de barycentre dans ta classe Top30, le tour est joué ^^.
bali_balo....=]
22 oct. 2007 à 18:50
Sans méchanceté, je trouve que les adeptes du Flash devraient un peu réviser leur classique.
Pour finir, la méthode des barycentres peut aussi servir à détecter si un point est dans un triangle ou non. Je n'arriverais jamais à comprendre les programmeurs qui ne veulent pas faire un minimum de maths (ceci réduit beaucoup les possibilités...).
22 oct. 2007 à 18:39
j'ai juste l'impression que c'est un peu "lourd" non ?
22 oct. 2007 à 16:37
22 oct. 2007 à 16:29
M appartient au segment [AB]
si et seulement si
M est le barycentre de (A,k) et (B,1-k) avec 0<=k<=1
si et seulement si
x_M=k*x_A+(1-k)*x_B et y_M=k*y_A+(1-k)*y_B avec 0<=k<=1
si et seulement si
x_M=k*(x_A-x_B)+x_B et y_M=k*(y_A-y_B)+y_B avec 0<=k<=1
si et seulement si
x_M-x_B=k*(x_A-x_B) et y_M-y_B=k*(y_A-y_B) avec 0<=k<=1
Quel est alors le programme ?
TEST 1 : Si x_A=x_B, on regarde si y_M est entre y_A et y_B.
TEST 2 : Si y_A=y_B, on regarde si x_M est entre x_A et x_B.
Cas Général : On a x_A<>x_B et y_A<>y_B. Dans ce cas, on calcule k_1=(x_M-x_B)/(x_A-x_B) et k_2=(y_M-y_B)/(y_A-y_B) . On doit avoir k_1=k_2 et ensuite 0<=k_1<=1 .
En espérant avoir été clair.
21 oct. 2007 à 20:38
= )
21 oct. 2007 à 20:29
21 oct. 2007 à 19:22
Remplacer la fonction "hitTest" de "IntersectionExample"
par ceci :
public function hitTest ( $oP1 : Point, $oP2 : Point, $oP3 : Point )
: Boolean
{
var nRnd : Number = 100000000 ;
var nA12 : Number = LibNum.round (LibGeom.angle ($oP1, $oP2) , nRnd );
var nA13 : Number = LibNum.round (LibGeom.angle ($oP1, $oP3) , nRnd );
var nD12 : Number = LibGeom.distance ($oP1, $oP2 );
var nD13 : Number = LibGeom.distance ($oP1, $oP3 );
//
return (nA12 == nA13) && (nD13 <= nD12) ;
}
En gros, si l'angle "P1-P2" est le même que "P1-P3", et que la distance de P1 à P3 est inférieure ou égale à la distance de P1 à P2, est alors en théorie sur le segment....
21 oct. 2007 à 18:58
21 oct. 2007 à 18:51
Ma fonction détermine si un point est sur une droite, pas un segment.
Donc pour savoir si un point est sur le segment, il faut qu'il soit dans l'intervale formé par ses deux points.
Quand je disais que tes calculs sont tordus, je voulais dire par là qu'ils sont complexes :)
bali_balo....=]
21 oct. 2007 à 18:47
Et si mon niveau de math n'était pas si bas, mes calculs se seraient pas tordus...
= )
21 oct. 2007 à 18:38
Désolé de pas savoir...
21 oct. 2007 à 18:36
21 oct. 2007 à 18:15
import flash.geom.Point;
function isOnTheSegment( p1:Point,p2:Point,p3:Point ) :Boolean {
//calcul de l'équation de la droite des 2 points du segment
var a:Number = (p2.y-p1.y)/(p2.x-p1.x);
var b:Number = p1.y-a*p1.x;//OU bien b=p2.y-a*p2.x;
trace( a );
trace( b );return ( a*p3.x+b p3.y );// OU return ( (p3.y-b)/a p3.x );
}
//retourne false
trace( isOnTheSegment( new Point(0,2) , new Point(2,0) , new Point(2,2) ) );
//retourne true
trace( isOnTheSegment( new Point(0,2) , new Point(2,0) , new Point(1,1) ) );
21 oct. 2007 à 15:36
Mais pourrais-tu le traduire à un language plus claire pour moi, car comme tu as pu le remarquer, mon niveau de math/algèbre est relativement bas !!!!
= (
21 oct. 2007 à 15:04
Vérifie aussi si le point est dans l'intervale du segment.
(dsl pour tous ces post)
21 oct. 2007 à 14:54
(C'est promis pour cette semaine je met enfin un morceau de mon package ^^)
bali_balo....=]
21 oct. 2007 à 14:47
Equation d'une droite : y=ax+b
a=(y2-y1)/(x2-x1)
et b=y1-ax1 OU b=y2-ax2
Ensuite tu vérifie si ax3+b=y3 ou que (y3-b)/a=x3
21 oct. 2007 à 14:30
= )"
Mais lol ^^, rien de plus simple.
Avec deux points , tu peux calculer l'équation de la droite passant par cela. Ensuite tu vérifie tout simplement si le point vérifie l'équation trouvée... Dois-je t'écrire le code où ça ira?... :P
Tiens, regarde cela http://www.iag.asso.fr/articles/intersection.htm, ou bien tapes tout simplement "intersection point segment" dans gougueuleux.
bali_balo....=]