DÉTECTION D'INTERSECTION DE DEUX LIGNES

Commentaire de bali_balo le 21/10/2007 14:47:25

P1(x1,y1) , P2(x2,y2) , P3(x3,y3) et le segment [P1,P2]
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

Commentaire de bali_balo le 21/10/2007 15:04:38

Ah j'oubliais ^^, si un point fait partie d'un "segment".
Vérifie aussi si le point est dans l'intervale du segment.
(dsl pour tous ces post)

Commentaire de bali_balo le 21/10/2007 18:15:28

MMDDRR tu nous sort une classe remplie de calcul tous tordue les uns que les autres, et tu me dis que ton niveau de math est relativement bas... hum hum... ^^

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) ) );

Commentaire de top30 le 21/10/2007 18:38:03

Et uq'est-ce que cela veut dire "si le point est dans le même intervale que le segment "
Désolé de pas savoir...

Commentaire de bali_balo le 21/10/2007 18:51:24

Bah...tu veux savoir si un point fait partie d'un segment.
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....=]

Commentaire de top30 le 21/10/2007 19:22:25

Problème résolu de facon facile :

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....

Commentaire de top30 le 21/10/2007 20:38:40

Ben donne moi le plus "rapide"...
= )

Commentaire de rambc le 22/10/2007 16:37:30

Compléments : pour éviter des arrondis hazardeux dus aux divisions, on peut noter grâce à un simple produit en croix que  k_1=k_2  si et seulement si  (x_M-x_B)*(y_A-y_B) = (y_M-y_B)*(x_A-x_B).

Commentaire de rambc le 22/10/2007 18:50:53

Pour calculer un angle, on fait des arrondies et pas des moindres, et pour une distance c'est la même chose. A programmer la méthode ci-dessus est TRES facile, et de plus rapide. Programmer n'est pas penser. A toi de voir si tu trouves plus simple et efficace, fais moi signe...

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...).

Commentaire de top30 le 22/10/2007 20:57:41

Sauf que RAMBC, il a parlé chinois pour moi....
Si il etais sympa il nous la traduirais en AS non ?

; )

Commentaire de bali_balo le 23/10/2007 00:50:02

Voilà de quoi on m'a gavé lorsque j'étais encore un pauvre étudiant en informatique :(

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

Commentaire de Slagt le 24/10/2007 22:46:34

Pour ne pas avoir à calculer les distances, on peut aussi se servir de l'équation d'une courbe de bézier linéaire, dans ce cas, il faut simplement que ces termes soient compris entre 0 et 1 (inclus) :

   (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)

Commentaire de Slagt le 25/10/2007 22:56:37

Je l'ai pas tester mais ça devrait fonctionner logiquement. Sauf si justement j'ai fait une erreur de logique.

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 :)

Commentaire de rambc le 25/10/2007 23:32:49

C'est juste ce que j'ai mis juste avant.... ;-)

Commentaire de Slagt le 26/10/2007 15:30:37

Désolé RAMBC, j'avais pas vu ton commentaire.

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 :)

Commentaire de Slagt le 26/10/2007 22:01:02

>> 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.

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.

Commentaire de top30 le 26/10/2007 22:04:55

Et ca marche !
Donc le gagnant est : SLAGT !

Commentaire de bali_balo le 26/10/2007 23:12:36

Top30 tu te rends compte à quel point ta "petite" question fait débat :D
Pour savoir comment on détermine si un point est sur un segment...
MMDDRR!


bali_balo....=]