Discussion :

[julian_ross]

Bonjour,

J'aimerais savoir s'il existe un algo efficace pour avoir un résultat booléen en sortie qui indique si 2 segments ont un point en commun ou pas (je n'ai pas besoin des coordonnées de ce point).
Actuellement, je résous le système d'équations des 2 droites qui portent ces segments et ensuite je vérifie que le résultat respecte les contraintes de position des 2 segments. Je pense qu'il y a plus efficace, surtout si on n'a pas besoin des coordonnées du point d'intersection.

Merci.

[Mat.M]

Basiquement on peut utiliser Bresenham et faire 2 boucles sur les 2 segments de droite.

Pour chaque y2, pour chaque x2,
Pour chaque y1, pour chaque x1,
Faire
si x1==x2 et y1==y2 alors les 2 segments se croisent.
Fin

Pour l'algorithme faire google et Bresenham sur Wikipedia cela doit se trouver.
C'est avec le coeff directeur d'une droite

[Laurent Gomila]

Pour chaque y2, pour chaque x2,
Pour chaque y1, pour chaque x1,

Pas facile à énumérer avec des coordonnées réelles

Je pense que l'algo suivant fonctionne :
- Tester si les deux extrémités du segment A sont bien de part et d'autre du segment B (avec son équation de droite)
- Tester si les deux extrémités du segment B sont bien de part et d'autre du segment A (avec son équation de droite)

Je pense que si ces deux conditions sont vérifiées alors il y a forcément intersection.

Reste à gérer le cas particulier où les deux segments sont portés par la même droite.

[bafman]

moi, je verifirait que les deux segments sont sur le même plan, et si il le sont, on verifie que les droites n'ont pas le même coefficient directeur

[Albenejean]

moi, je verifirait que les deux segments sont sur le même plan, et si il le sont, on verifie que les droites n'ont pas le même coefficient directeur

Oui mais dans ca cas, on calcul l'intersection de droite et pas de segments. Non?

Je pense que l'algo suivant fonctionne :
- Tester si les deux extrémités du segment A sont bien de part et d'autre du segment B (avec son équation de droite)
- Tester si les deux extrémités du segment B sont bien de part et d'autre du segment A (avec son équation de droite)

Oui.
Si tu as un segment [A1, A2] et un point P, le signe du déterminant de PA1^A1A2 permet de savoir de quel côté est le point P.
Tu dois donc avoir pour deux segments [A1, A2] et [B1, B2] :
_ det(A1B1 ^ B1B2) * det(A2B1 ^ B1B2) <= 0
et _ det(B1A1 ^ A1A2) * det(B2A1 ^ A1A2) <= 0

[bafman]

Oui mais dans ca cas, on calcul l'intersection de droite et pas de segments. Non?

ha oui, effectivement, j'avais perdu de vue le coté segment de la chose

[Mat.M]

Pas facile à énumérer avec des coordonnées réelles

eh bien il suffit de prendre la partie entière et de typer en int

[souviron34]

bon j'ai déjà donné dans le forum algo les pointeurs, je les remet ici :

Je donne le lien général pour tous ceux que ça peut intéresser : la FAQ des newsgroup comp.graphics.algorithms..

L'original :

http://www.faqs.org/faqs/graphics/algorithms-faq/

ou en reformatté HTML :

http://www.exaflop.org/docs/cgafaq/

plus :

GraphicsGems :

http://www.acm.org/tog/GraphicsGems/

Et Dr.Maths

http://mathforum.org/dr.math/

[orelero]

L'algo line-sweep ?


Sinon un vieux truc ressorti des placards mais qui marche trés bien :
(par contre il est plus destiné à te donner en plus l'intersection)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static boolean segment2segment(Point2D.Float A,Point2D.Float B,Point2D.Float C,Point2D.Float D)
	{
		float Ax = A.x;
		float Ay = A.y;
		float Bx = B.x;
		float By = B.y;
		float Cx = C.x;
		float Cy = C.y;
		float Dx = D.x;
		float Dy = D.y;
 
		double Sx;
		double Sy;
 
		if(Ax==Bx)
		{
			if(Cx==Dx) return false;
			else
			{
				double pCD = (Cy-Dy)/(Cx-Dx);
				Sx = Ax;
				Sy = pCD*(Ax-Cx)+Cy;
			}
		}
		else
		{
			if(Cx==Dx)
			{
				double pAB = (Ay-By)/(Ax-Bx);
				Sx = Cx;
				Sy = pAB*(Cx-Ax)+Ay;
			}
			else
			{
				double pCD = (Cy-Dy)/(Cx-Dx);
				double pAB = (Ay-By)/(Ax-Bx);
				double oCD = Cy-pCD*Cx;
				double oAB = Ay-pAB*Ax;
				Sx = (oAB-oCD)/(pCD-pAB);
				Sy = pCD*Sx+oCD;
			}
		}
		if((Sx<Ax && Sx<Bx)|(Sx>Ax && Sx>Bx) | (Sx<Cx && Sx<Dx)|(Sx>Cx && Sx>Dx)
				| (Sy<Ay && Sy<By)|(Sy>Ay && Sy>By) | (Sy<Cy && Sy<Dy)|(Sy>Cy && Sy>Dy)) return false;
		  return true; //or :     return new Point2D.Float((float)Sx,(float)Sy)
	}

(en java)

[Kicker]

Bonjour,

Désolé de déterrer ce vieux topic mais en fait j'aurais besoin de déterminer si 2 segments se croisent, sur une architecture ARM.
Le principal problème est la division. Il faut proscrire toute division pour que l'algorithme soit efficace (le décalage à gauche est toutefois autorisé).

Si quelqu'un a une idée, je suis preneur...
Merci d'avance !

[souviron34]

premier pointeur que j'ai donné (les FAQs) sujet 1.03


Faut regarder un peu ce qu'on donne...

[Kicker]

J'ai regardé : il y a deux divisions pour déterminer s et r...

[souviron34]

alors autre chose, mais cela n'envisagera pas sans doute tous les cas (le seul algo envisageant tous les cas est celui présenté ci-dessus) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
calculer le signe de l angle entre les 2 extrémités d un des segments et l une de l autre.
calculer le signe de l angle avec l autre extrémité.
 
 
si ils sont de même signe : ne se croisent pas.
si ils sont de signe différents : 
    refaire les 2 calculs d angles en inversant les segments. 
         Si ils sont de même signe : ne se croisent pas. 
         Si ils sont de signe différents  : se croisent

Pour connaître le signe d'un angle entre 3 points, c'est basé sur une routine du bouquin de Sedgewick (p. 350) :

"Algorithms in C"
Robert Sedgewick
Addison-Wesley 1990 . ISBN 0-201-51425-7

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#define ACCURACY_DOUBLE  1.e-06
 
int CounterClockWise ( double Pt0_X, double Pt0_Y, 
                       double Pt1_X, double Pt1_Y, 
                       double Pt2_X, double Pt2_Y )
{
 double dx1, dx2, dy1, dy2 ;
 
 dx1 = Pt1_X - Pt0_X ;
 dy1 = Pt1_Y - Pt0_Y ;
 dx2 = Pt2_X - Pt0_X ;
 dy2 = Pt2_Y - Pt0_Y ;
 if ( fabs(dx1) < ACCURACY_DOUBLE )
    dx1 = 0.0 ;
 if ( fabs(dx2) < ACCURACY_DOUBLE )
    dx2 = 0.0 ;
 if ( fabs(dy1) < ACCURACY_DOUBLE )
    dy1 = 0.0 ;
 if ( fabs(dy2) < ACCURACY_DOUBLE )
    dy2 = 0.0 ;
 
 if ( (dx1*dy2) > (dy1*dx2) )
     return (+1);
 
 if ( (dx1*dy2) < (dy1*dx2) )
     return (-1);
 
 if ( ((dx1*dx2) < 0.0) || ((dy1*dy2) < 0.0) )
     return (-1);
 
 if ( (dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2) )
     return (+1);
 
 return (0) ;
}

[popoms]

Bonjour,

je re-déterre le sujet parce que je viens de m'y plonger. Et j'ai fait un truc très compliqué avant de chercher ici . Je jure -comme à chaque fois- qu'on ne m'y reprendra plus!

Je voudrais juste préciser que le lien donné par souviron34 (sujet 1.03) permet de trouver si il y a intersection sans faire de division.

En effet le calcul de r et s n'est nécessaire que pour trouver effectivement le point d'intersection, sinon il suffit de savoir si r<0 ou r>1 ou s<0 ou s>1:
* pour comparer par rapport à 1, on compare le numérateur et le dénominateur
* pour comparer par rapport à 0, on compare le signe du numérateur et du dénominateur

Et voiloù...!

[fred.lokote]

pour éviter de calculer l'intersection et d'utiliser des divisions, il suffit de faire 2 ou 4 tests point/droite avec les produits scalaires

pour chaque droite, si les 2 points ne sont pas du même côté, ou si au moins l'un des deux points est exactement inclus dans la droite, alors il y'a un contact entre le point et la droite

mettons que mes deux segs sont définis par les points p1 p2 et p3 p4

en pseudo-code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
directeur = p4-p3
normale = vecteur( -directeur.y , directeur.x )
 
distance1 = dot( p1-p3 , normale ) -- distance orientée point/droite
distance2 = dot( p2-p3 , normale )
 
if ( (distance1>0) and (distance2<0) ) or ( (distance1<0) and (distance2>0) ) or  distance1=0 or distance2=0 --> refaire même test réciproque

je ne sais pas si c'est plus rapide que ta technique mais là il n'y a pas de division (donc pas de résultat approximatif)

[comtois]

solution issue d'un bouquin d'algorithme en C, faudrait que je le retrouve pour donner la référence.

Le code ci dessous correspond à mon langage préféré --> PureBasic.

Le principe : il faut d'abord tester les boîtes englobantes des segments avant de tester le chevauchement des segments.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  ;Test Collision boîtes englobantes
  If Box1\P2\x >= Box2\P1\x And Box1\P1\x <= Box2\P2\x And Box1\P2\y >= Box2\P1\y And Box1\P1\y <= Box2\P2\y

Bien que ça soit du BASIC, je vais détailler un peu la syntaxe.

S2\P1\x :

- S2 pour le segment n°2
- P1 pour le point n°1 du segment n°2
- x pour la position en x du point n°1 du segment n°2

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Structure Segment
  P1.point 
  P2.point
EndStructure
 
Procedure CollisionSegmentSegment(*S1.Segment,*S2.Segment)
  ;Test Collision encadrement
  If Box1\P2\x >= Box2\P1\x And Box1\P1\x <= Box2\P2\x And Box1\P2\y >= Box2\P1\y And Box1\P1\y <= Box2\P2\y
    ;Test chevauchement segments
    R1.f=((*S2\P1\x-*S1\P1\x)*(*S1\P2\y-*S1\P1\y))-((*S2\P1\y-*S1\P1\y)*(*S1\P2\x-*S1\P1\x))
    R2.f=((*S2\P2\x-*S1\P1\x)*(*S1\P2\y-*S1\P1\y))-((*S2\P2\y-*S1\P1\y)*(*S1\P2\x-*S1\P1\x))
    R3.f=((*S1\P1\x-*S2\P1\x)*(*S2\P2\y-*S2\P1\y))-((*S1\P1\y-*S2\P1\y)*(*S2\P2\x-*S2\P1\x))
    R4.f=((*S1\P2\x-*S2\P1\x)*(*S2\P2\y-*S2\P1\y))-((*S1\P2\y-*S2\P1\y)*(*S2\P2\x-*S2\P1\x))
    If (Signe(R1)*Signe(R2)<=0) And (Signe(R3)*Signe(R4)<=0)
      Resultat = #True
    EndIf
  EndIf
  ProcedureReturn Resultat
EndProcedure

[ben.oeilnoir]

Bonjour à tous,

Pour tout ceux qui tombent sur ce topic à la recherche d'un algo d'intersection, je tiens à dire que celui qui est donné plus haut n'est pas fiable à 100%, comme la plupart. Il est vrai que le probleme de l'intersection n'est pas trivial. Voici une explication et un début de solution :

(nota : je parlerai de droites mais tout est valable pour des segments.)

- Premièrement :
L'algorithme ne gère pas la plupart des cas de colinéarité. Pour rappel, deux droites sont colinéaires lorsqu'elles ont deux points en commun (elles sont "alignées", quoi). De plus, deux droites colinéaires sont effectivement sécantes, en une infinité de points. La réponse "NULL" est donc très discutable.

- Deuxièmement :
L'algorithme ne gère pas le cas des droites parallèle, ce qui est balot. Pour rappel, deux droites sont parallèle si elles ont la même pente(coef. directeur, dans le code pAB et pCD).
En effet, le calcul de l'abscisse du points d'intersection se fait avec une division par la soustraction des deux pentes qui, si elles sont égales, entraine une division par 0. Sur certains systeme cela fait planter, sur d'autre cela entraine un "NaN" (Not a Number) et non un "NULL".

- Troisièmement :
Pour trouver les coordonnées du point d'intersection, l'algorithme emploi une division pour calculer chaque pente et une troisième division pour l'abscisse. Cela provoque une perte de précision. De fait, on ne peux pas estimer que le point d'intersection se trouve sur la droite, quelque soit la precision de notre repère.

Les solutions :
selon moi, le calcul d'un point d'intersection se fait en deux phases :
- Déterminer l'état de l'intersection.
- Puis déterminer le ou les points d'intersection.

L'état peut être :
- Sécant dans les limites (segments sécants)
- Sécant hors des limites (droites sécantes)
- Colinéaire (possède un point de début et un point de fin de la zone d'intersection)
- Parallèle

Une bonne solution pour trouver l'état à été donnée dans ce fil, il s'agit de trouver de quel coté un des points se situe par rapport à l'autre segment. Voici une illustration en pseudo code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
intersection(a, b, c, d)
SI
  le tournant "abc" est horaire et le tournant "abd" est horaire
ALORS
  c et d se situent du même coté de la droite AB

Il existe différents moyen pour trouver le sens de rotation. le déterminant est sans doute le plus rapide. pour rappel, le déterminant de deux vecteurs représente l'aire du parallélogramme constitué par ces deux vecteur et leurs projections, à ceci prés que si elle est négative, alors les points du parallélogramme sont nommé dans le sens horaire.

Sur la plupart des systèmes, cela donne ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
tournant = b.soustraire(a).déterminant(c.soustraire(a))
SI tournant > 0 ALORS sens de rotation est anti-horaire
SI tournant < 0 ALORS sens de rotation est horaire
SI tournant = 0 ALORS colinéaire

A partir de là, nous pouvons comparer l'emplacement de tout les vecteurs et vérifier les lois qui ont été mentionnées plus haut :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
SI tournant abc = tournant abd = tournant acd = tournant bcd = 0
ALORS AB CD sont colinéaires
 
SI
  a et b sont de part et d'autre de CD ET
  c et d sont de part et d'autre de AB
ALORS
  AB CD sécant dans les limites
SINON SI
  a et b sont de part et d'autre de CD
ALORS 
  AB CD sécant hors des limites de CD 
SINON SI
  c et d sont de part et d'autre de AB
ALORS 
  AB CD sécant hors des limites de AB
 
SINON SI les pentes de AB et CD sont égales
ALORS AB CD sont parallèles.
SINON
  AB CD sécant hors des limites.
 
trouver point d'intersection (a, b, c, d)
...

etc etc. Vous l'avez compris, cette algorithme est encore long. Je vous prie de m'envoyer un e-mail si vous voulez aller plus loin.

Par ailleurs, je vous invite a consulter le code open source de la librairie java JTS qui contient un code très robuste et complet d'intersection 2D, et n'emploie aucune division.

Bon courage à tous.

[ac_wingless]

Ben.oeilnoir, je ne pense pas que les posts ci-dessus souhaitaient particulièrement être exacts, mais plutôt efficaces, en tenant compte de certaines contraintes d'architecture (par exemple pour l'embarqué).

Pour ce qui est de l'exactitude, vous êtes encore assez loin de la solution, pour un problème qui est certes reconnu comme ardu dans sa forme pure. De nombreux travaux universitaires existent pour "transformer" 2 lignes de maths au dos d'une enveloppe vers un algorithme utilisable sur ordinateur, en particulier pour ce à quoi vous vous attaquez ici. Certaines formations sensibilisent aussi les étudiants, comme ici. Enfin, des librairies impressionnantes ont été développées pour cette classe de problèmes, comme CGAL.

Dans le cas qui nous concerne ici, notre société utilise (comme base pour des algorithmes exacts sur des meshes) l'implémentation de Shewchuk (code inclus, attention aux erreurs dus à la surprécision en 80 bits sur architecture x86). 4000 lignes pour dire si un point est à droite ou à gauche d'un segment peut paraître impressionnant, mais c'est le prix à payer pour l'exactitude. En effet, comme il est dit dans l'overview de CGAL:

the underlying algorithms ask questions like "is a point to the left, to the right, or on the line through two other points?" Such questions have no answers that are "slightly off". Either you get it right, or you don't. And if you don't, the algorithm might go completely astray. Even the most fancy roundoff control techniques don't help here: it's primarily a combinatorial problem, not a numerical one

[souviron34]

Pour tout ceux qui tombent sur ce topic à la recherche d'un algo d'intersection, je tiens à dire que celui qui est donné plus haut n'est pas fiable à 100%, comme la plupart. Il est vrai que le probleme de l'intersection n'est pas trivial. Voici une explication et un début de solution :

D'abord, crois-tu être meilleur que ce qui est déposé sur Computational Geometry, où les meilleurs de la planète participent depuis plus de deux décennies ???


D'autre part, alors que je fais un usage intensif de la fameuse routine dont j'ai donné le lien ci-dessus, je ne l'ai jamais vu dysfonctionner depuis plus de 20 ans... Alors que je m'en sers plus de 10 000 fois par jour...

Il y a bien 2 divisions, mais le test :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( (r > 0.0) && (r < 1.0) && (s >= 0.0) && (s <= 1.0) )

donne bien la bonne solution.

- Premièrement :
L'algorithme ne gère pas la plupart des cas de colinéarité. Pour rappel, deux droites sont colinéaires lorsqu'elles ont deux points en commun (elles sont "alignées", quoi). De plus, deux droites colinéaires sont effectivement sécantes, en une infinité de points. La réponse "NULL" est donc très discutable.

- Deuxièmement :
L'algorithme ne gère pas le cas des droites parallèle, ce

Si on a besoin d'une fonction pour chercher des intersections, ce n'est pas pour savoir si les droites sont parallèles ou confondues. Il y a des moyens plus simples.

D'autre part, la fonction indiquée est suffisante, il suffit de modifier les critères sur r et s.



Comme vient de le dire ac_wingless (et tel que c'est mentionné dans les liens donnés), évidemment en informatique il y a un problème d'exactitude et d'arrondi.

C'est toute la différence entre les maths pures et les maths appliquées.

Si on veut tenir compte des imprécisions, il suffit d'ajouter (ce que je fais dans mes tests) des "marges" dépendant de la précision attendues :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( (r > ACCURACY) && (r < (1.0-ACCURACY)) && (s >= -ACCURACY) && (s <= (1.0+ACCURACY)) )

Cependant je prend ton post pour de la publicité pour ton soft, et à ce titre je souhaiterais qu'il soit supprimé, car encore une fois je n'ai pas dans mon expérience pu mettre en défaut la routine mentionnée..





Quant à la question de savoir si un point est à gauche ou à droite d'un segment, une excellente publication il y a peu (2000), a donné une solution élégante et plus simple que la fameuse routine ccw de Sedgewick :

http://softsurfer.com/Archive/algori...rithm_0101.htm



PS: et le coût de 2 divisions est inférieur de loin à éxécuter 4000 lignes de code..

[ac_wingless]

Les fameuses 4000 lignes implémentent de façon exacte les quelques lignes suivantes de votre lien:

// isLeft(): tests if a point is Left|On|Right of an infinite line.
// Input: three points P0, P1, and P2
// Return: >0 for P2 left of the line through P0 and P1
// =0 for P2 on the line
// <0 for P2 right of the line
inline int
isLeft( Point P0, Point P1, Point P2 )
{
return ( (P1.x - P0.x) * (P2.y - P0.y)
- (P2.x - P0.x) * (P1.y - P0.y) );
}

Il n'y a pas de problème de division pour ce cas. J'ai simplement voulu indiquer que dans le post de ben.oeilnoir, des morceaux comme "a et b sont de part et d'autre de CD" ne font que déplacer le vrai problème d'exactitude, pas le résoudre.
Par ailleurs, l'utilisation d'espilons est parfaitement justifiée dans la plupart des cas d'ingénierie. La différence avec les cas où on a besoin de géométrie exacte est bien expliquée dans ce lien (paragraphes "The Numerical Approach" et "The CGAL Approach").
Ces derniers cas ne sont pas hypothétiques: pour une simple addition de flottant, on peut avoir des choses étonnantes, comme une perte de topologie par déplacement. C'est un problème concret qu'on retrouve dans des applications aussi peu exotiques que les pièces avion, qui après exportation sous format CNC sont topologiquement correctes si elles sont exportées dans le repère de conception, mais incorrectes (trous, plis, etc.) si elles sont exportées en coordonnées avion.

Si il y a un message que j'aimerais faire passer dans cette discussion, c'est que l'exactitude est un problème très difficile et fortement sous-estimé. Les solutions sont de trois classes:
- l'exactitude "algorithmique", comme dans le post de ben.oeilnoir. En l'occurrence pour le problème en question c'est très simple, mais ce n'est pas toujours le cas. Ceci est évidemment un pré-requis, en général non suffisant.
- l'exactitude "numérique", qui met en œuvre des techniques souvent peu couteuses, comme des intervalles de confiance. Il est dommage de s'en passer, et c'est normalement suffisant.
- l'exactitude parfaite, qui est normalement inutile, très lourde, mais parfois indispensable. Les approches triviales (précision infinie) sont inutilisables sur des formules avec beaucoup d'opérations, à cause de l'explosion combinatoire.

A mon avis, l'approche de CGAL est très saine, car elle ne déclenche les solutions lourdes que quand on en a besoin, c'est à dire quand les epsilons ne garantissent plus un résultat exact.