DÉTECTION D'INTERSECTION DE DEUX LIGNES

Signaler
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010
-
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010
-
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

top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

C'est ca l'interessant de la source au fond...
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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....=]
BananaTree
Messages postés
337
Date d'inscription
vendredi 15 octobre 2004
Statut
Membre
Dernière intervention
2 novembre 2010

>> Slagt
exact (j'ai pris mon crayon pour vérifier ;) )
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

Et ca marche !
Donc le gagnant est : SLAGT !
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

La gagnante est :

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 !
Slagt
Messages postés
232
Date d'inscription
mercredi 2 avril 2003
Statut
Membre
Dernière intervention
29 mars 2011

>> 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.
BananaTree
Messages postés
337
Date d'inscription
vendredi 15 octobre 2004
Statut
Membre
Dernière intervention
2 novembre 2010

et bla, et bla, et bla...
"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" ! "
Slagt
Messages postés
232
Date d'inscription
mercredi 2 avril 2003
Statut
Membre
Dernière intervention
29 mars 2011

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 :)
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

OOH ! Encore plus fort !
Je te note après test !
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

C'est juste ce que j'ai mis juste avant.... ;-)
Slagt
Messages postés
232
Date d'inscription
mercredi 2 avril 2003
Statut
Membre
Dernière intervention
29 mars 2011

Ah... on a 2 conditions en fait :
- 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
Slagt
Messages postés
232
Date d'inscription
mercredi 2 avril 2003
Statut
Membre
Dernière intervention
29 mars 2011

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 :)
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

OOOUH !! à tester, mais ca parait un tres "joli" coup !!!
Slagt
Messages postés
232
Date d'inscription
mercredi 2 avril 2003
Statut
Membre
Dernière intervention
29 mars 2011

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)
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

Après mise en application je confirme le bon
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 !
= )
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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
BananaTree
Messages postés
337
Date d'inscription
vendredi 15 octobre 2004
Statut
Membre
Dernière intervention
2 novembre 2010

si la somme des distances (p1,p2) et (p2,p3) est egale à la longueur (p1,p3) alors p2 est sur le segment [p1, p3].
dixit flash.geom.Point.
(je peux me tromper, j'y entrave que d'alle en math)
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

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

; )
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

"Je n'arriverais jamais à comprendre les programmeurs qui ne veulent pas faire un minimum de maths (ceci réduit beaucoup les possibilités...)."
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....=]
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

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...).
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

pas trop...
j'ai juste l'impression que c'est un peu "lourd" non ?
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

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).
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

Voici une méthode mathématique possible.

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.
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

Ben donne moi le plus "rapide"...
= )
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

Oui, je pense aussi que cela marche, il y a bien des théorèmes en géométrie pour résoudre ce genre de problème.
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

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....
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

De plus la fonction "hitTest" ajouté ne fonctionne pas à 100% !!!!
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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....=]
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

Ahhh oui...
Et si mon niveau de math n'était pas si bas, mes calculs se seraient pas tordus...

= )
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

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...
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

J'oubliais qu'il fallait vérifier aussi si le point est dans le même intervale que le segment : j'ai la flemme de re-écrire le code ^^.
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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) ) );
top30
Messages postés
1158
Date d'inscription
vendredi 21 février 2003
Statut
Membre
Dernière intervention
6 août 2010

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

= (
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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)
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

Jcrois que je vais me faire une ptite classe dans le genre dans mon package geom. J'en ai marre de re-écrire ces fonctions dans mes classes. Limite je reprend la tienne ^^.
(C'est promis pour cette semaine je met enfin un morceau de mon package ^^)

bali_balo....=]
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

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
cs_bali_balo
Messages postés
1381
Date d'inscription
samedi 9 octobre 2004
Statut
Membre
Dernière intervention
1 novembre 2010

"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" !
= )"

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