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)