# Deux lignes se croisent-elles ?



## peon.master (6 Février 2005)

Bonjour,

Ma question traite plus d'un problème l'algoritme/math que d'un language. Toutefois, j'utilise xCode / obj-c et mon projet est en 2D.

J'aimerai pouvoir tester si deux lignes se croisent. J'ai les points P1 et P2 pour la première ligne et disons P3 et P4 pour la deuxième.

Est-ce qu'il existe une fonction pour ça ? (NSLignesSeCroisent(NSPoint p1...))

Sinon, qqn a une idée pour faire ça mathématiquement ?


----------



## molgow (6 Février 2005)

Lorsque tu dis de "lignes", parle-tu de _segments de droites_ ou de _droites_ ?
Dans le deuxième cas, c'est plus facile, car il te suffit de tester que les droites ne soient pas parallèles.


----------



## peon.master (6 Février 2005)

Ben justement, les lignes sont finies. Ce sont des segments tels que l'on peut les afficher avec

```
[NSBezierPath strokeLineFromPoint:P1 toPoint:P2];
```


----------



## [MGZ]Slug (6 Février 2005)

Le plus général serait de determiner les équations des deux droites correspondant à tes segments, calculer leur point d'intersection si c'est possible, et tester pour savoir si les coordonnées de ce point appartiennent à un domaine correct.


----------



## _gael (6 Février 2005)

la formul d' intersection:


```
bool intersection_lineaire(float a1,float b1,float a2,float b2,point * resulta) {
	if(a1==a2 )return false;
	resulta->y=(b1*a2-a1*b2)/(a2-a1);
	resulta->x= (resulta->y-b1)/a1;
	return true;
}
```
le formul de miz en equation d' un segment en droite du type y=Ax+b:

```
void droite_avec_segment(point *p1,point *p2,float * rA,float * rB) {//du type y= xA + B
	if(p1->x == p2->x) *rA=10000;
	else if(p1->y == p2->y) *rA=0.0;
	else
		*rA= (p2->y-p1->y)/(p2->x - p1->x);
	*rB= p2->y - *rA * p2->x;//-(p2->y-p1->y)*(p2->x/(p2->x - p1->x));
		
}
```
pour simplifier un peut mon code g triche un peu, une droite construite avec 2 point donc les x sont =, en gros une droite vertical donne une droite se raprochant de la vertical mais pas parfaite: genre 89.998 degres..
voila si cette imperfection te genne tu peut toujours faire un test sur les segments et si 1 des 2 est vertical traiter le problem d' une autre maniere(intersection d' un segment avec une valeur y,ce qui tres simple a faire)
autre chose si le point que tu trouvera est bien sur les 2 droite qui s' intersectionne, rien ne garanti qu' il le soit aussi sur t 2 segment.. y faut que tu fasse le test apres du genre 
if((resulta.y <= seg1.point1.y != resulta.y <= seg1.point2.y) && (resulta.y <= seg2.point1.y != resulta.y <= seg2.point2.y)) return true;
else return false;
voila bonne continuation a+


----------



## peon.master (6 Février 2005)

Okay, merci pour les réponses...

_Gael, ton code m'aide beaucoup et je vais m'en inspirer pour le projet.
Et si le prog final n'est pas trop buggé et qu'il marche bien, j'en ferai profiter tout le monde sur ces forums.

a plus.


----------



## [MGZ]Slug (7 Février 2005)

Ahh, il me semblait bien avoir fait un truc dans le genre pour aider mon frere dans ses révisions en C. J'ai retrouvé le fichier source ... c'est un poil plus lourd que l'exemple de Gael, et c'est un peu crade (pas de vérification que les mallocs se sont bien passés, quelques bidouilles pour expliquer certains points particuliers au frerot, limitation à ce qu'il avait vu en cours...), mais normalement ça marche 


```
#include <stdio.h>
#include <stdlib.h>

#define NOT_FOUND 1
#define FOUND 0

#define DEBUG

/* point du plan */

typedef struct _point
{
	float x;
	float y;
} *point;


/* equation de droite dans le plan */
/* ax + by + c = 0 */

typedef struct _equation
{
	float a;
	float b;
	float c;
} *equation;

/* vecteur du plan */

typedef struct _vector {
	float x;
	float y;
} *vector;

/* domaine */

typedef struct _domain {
	float sX;
	float gX;
	float sY;
	float gY;
} *domain;


/* construction de l'equation d'une droite a partir d'un vecteur */
/* directeur et d'un point */

int vectorToEquation ( vector v, point p, equation result )
{
	result->a = v->y;
	result->b = -v->x;
	result->c = -result->a * p->x -result->b * p->y;
	return 0;
}

/* construction du vecteur directeur. */

int pointsToVector ( point p1, point p2, vector result )
{
	result->x = ( p1->x > p2->x ) ? p1->x - p2->x : p2->x - p1->x;
	result->y = ( p1->x > p2->x ) ? p1->y - p2->y : p2->y - p1->y;
	return 0;
}

/* intersection de deux droites donnees sous forme de leur equation */

int intersection ( equation line1, equation line2, point result )
{
	float temp1, temp2;
	
	/* est-ce que les droites sont parallelles ou coincidentes ? */ 
	/* si oui pas de point communs, ou infinite de points       */
	/* si non, droites incidentes, et elles n'ont qu'un unique    */
	/* point d'intersection	*/

	if ( ( line1->a / line2->a ) == ( line1->b / line2->b ) ) return NOT_FOUND; 

	/* resolution du systeme d equation line1 line2	 */
	
	if ( line1->a == 0 ) {
		result->y = - line1->c / line1->b;
		result->x = ( line2->b == 0 ) ? - line2->c / line2->a :
							( - line2->c - line2->b * result->y ) / line2->a;
	}
	else if ( line2->a == 0 ) {
		result->y = - line2->c / line2->b;
		result->x = ( line1->b == 0 ) ? - line1->c / line1->a :
							( - line1->c - line1->b * result->y ) / line1->a;
	}
	else if ( line1->b == 0 ) {
		result->x = - line1->c / line1->a;
		result->y = ( - line2->c - line2->a * result->x ) / line2->b;
	}
	else if ( line2->b == 0 ) {
		result->x = - line2->c / line2->a;
		result->y = ( - line1->c - line1->a * result->x ) / line1->b;
	}	
	else {
		result->x = ( ( ( line2->b * line1->c ) / line1->b ) - line2->c )
				/ ( line2->a - ( ( line2->b * line1->a ) / line1->b ) );

		result->y = ( -line1->c - line1->a * result->x ) / line1->b;
	}
	
	return FOUND;
}

/* domaine dans lequel doit se trouver l'intersection des segments */
/* [p1, p2] et [p3, p4]	*/

int domainIntForPoints( point p1, point p2, point p3, point p4, domain result )
{

	if ( p1->x >= p2->x ) {
		result->sX = p2->x;
		result->gX = p1->x;
	}
	else {
		result->sX = p1->x;
		result->gX = p2->x;
	}
	
	if ( p1->y >= p2->y ) {
		result->sY = p2->y;
		result->gY = p1->y;
	}
	else {
		result->sY = p1->y;
		result->gY = p2->y;
	}
	
	if ( p3->x >= p4->x ) {
		if ( p3->x < result->gX ) result->gX = p3->x;
		if ( p4->x > result->sX ) result->sX = p4->x;
	}
	else {
		if ( p4->x < result->gX ) result->gX = p4->x;
		if ( p3->x > result->sX ) result->sX = p3->x;
	}

	if ( p3->y >= p4->y ) {
		if ( p3->y < result->gY ) result->gY = p3->y;
		if ( p4->y > result->sY ) result->sY = p4->y;
	}
	else {
		if ( p4->y < result->gY ) result->gY = p4->y;
		if ( p3->y > result->sY ) result->sY = p3->y;
	}

	return 0;
}


/* intersection des segments [p1,p2], [p3,p4] ?	 */ 

int intersectionSegments ( point p1, point p2, point p3, point p4, point result )
{
	equation eq1, eq2;
	vector v1, v2;
	domain d;
	int r;
	
	/* allocations memoire	*/
	eq1 = malloc ( 3 * sizeof ( float ) );
	eq2 = malloc ( 3 * sizeof ( float ) );
	v1 = malloc ( 2 * sizeof ( float ) );
	v2 = malloc ( 2 * sizeof ( float ) );
	
	/* conversion point -> vector	*/
	pointsToVector ( p1, p2, v1 );
	pointsToVector ( p3, p4, v2 );

#ifdef DEBUG
	printf ( "vector 1 : [ %.2f, %.2f ]\n", v1->x, v1->y );
	printf ( "vector 2 : [ %.2f, %.2f ]\n", v2->x, v2->y );
#endif
	
	/* conversion vector -> equation */
	vectorToEquation ( v1, p1, eq1 );
	vectorToEquation ( v2, p3, eq2 );

#ifdef DEBUG
	printf ( "equation 1 : %.2f * x + %.2f * y + %.2f = 0\n", eq1->a, eq1->b, eq1->c );
	printf ( "equation 2 : %.2f * x + %.2f * y + %.2f = 0\n", eq2->a, eq2->b, eq2->c );
#endif

	/* calcul de l'intersection */
	r = intersection ( eq1, eq2, result );
	
	/* liberation memoire */
	free ( eq1 );
	free ( eq2 );
	free ( v1 );
	free ( v2 );

	if ( r == FOUND) {	
		/* verification point dans le domaine ad hoc */
		d = malloc ( 4 * sizeof ( float ) );
		domainIntForPoints( p1, p2, p3, p4, d );
		
		if (
			result->x < d->sX
			|| result->x > d->gX
			|| result->y < d->sY
			|| result->y > d->gY
		   ) r = NOT_FOUND;
		
		free ( d );
	}
		
	return r;	
}

int main ()
{
	point p1, p2, p3, p4;
	point result;

	p1 = malloc ( 2 * sizeof ( float ) );
	p2 = malloc ( 2 * sizeof ( float ) );
	p3 = malloc ( 2 * sizeof ( float ) );
	p4 = malloc ( 2 * sizeof ( float ) );
	result = malloc ( 2 * sizeof ( float ) );

	fflush( stdout );
	fflush( stdin );
	
	printf ( "Entrez les coordonnees des extremites du premier segment ( x y x y ) : " );
	scanf( "%f %f %f %f", &(p1->x), &(p1->y), &(p2->x), &(p2->y) );
	
	fflush ( stdin );
	
	printf( "Segment 1 : [ %.2f, %.2f ] [ %.2f, %.2f ]\n", p1->x, p1->y, p2->x, p2->y );

	printf ( "Entrez les coordonnees des extremites du second segment ( x y x y ) : " );
	scanf( "%f %f %f %f", &(p3->x), &(p3->y), &(p4->x), &(p4->y) );
	
	fflush ( stdin );
	
	printf( "Segment 2 : [ %.2f, %.2f ] [ %.2f, %.2f ]\n", p3->x, p3->y, p4->x, p4->y );

		
	if ( intersectionSegments ( p1, p2, p3, p4, result ) == FOUND ) {
		printf( "Les segments se croisent en ce point : [ %.2f, %.2f ]\n", result->x, result->y );	
	}
	else {
		printf( "Les segments n'ont pas de point commun\n" );
	}

	free ( p1 );
	free ( p2 );
	free ( p3 );
	free ( p4 );
	free ( result );

	return 0;
}
```


----------



## arnolix (8 Février 2005)

Voici du code que j'utilise dans un prog en Obj-C.
La méthode setPointAvecDroitePuisDroite est à implémenter dans l'objet qui calcule le point d'intersection.
Elle fait appel à deux objets figureParent1 et figureParent2, en leur demandant par quels points elles passent. Ces objets peuvent être des segments, des demi-droites ou des droites.
Ensuite elle calcule les coordonnées du point d'intersection, résultats stockés dans coordPoint.
Elle sollicite ensuite les objets figureParent1 et figureParent2 avec la méthode déléguée -(BOOL)pointHorsBorneNSPoint)point, pour savoir si le point théorique n'est pas sur la figure. Une droite répond toujours NO, mais un segment ou une demi-droite peut répondre YES. Ces méthodes déléguées sont à placer dans les objets figureParent qui sont des droites, demi-droites ou segments.
Dans tous les cas le booléen estConstructible précise si il y a un point d'intersection entre les deux figures.
Tous les cas de figures sont traités par l'algo. (droite verticale, droites parallèles, segments disjoints, etc.).


```
- (void)setPointAvecDroitePuisDroite
{
	NSPoint A1 = [figureParent2 point1];
	NSPoint A2 = [figureParent2 point2];
	NSPoint a1 = [figureParent1 point1];
	NSPoint a2 = [figureParent1 point2];
	
	NSPoint U = NSMakePoint(A2.x - A1.x,A2.y - A1.y) ;
	NSPoint u = NSMakePoint(a2.x - a1.x,a2.y - a1.y) ;
	
	float determinant = U.y*u.x - u.y*U.x ;
	if(determinant != 0){
		float x = ((a1.y*u.x - a1.x*u.y)*U.x - (A1.y*U.x - A1.x*U.y)*u.x)/determinant ;
		float y = (U.x == 0)? u.y/u.x*(x - a1.x) + a1.y : U.y/U.x*(x - A1.x) + A1.y ;
		coordPoint = NSMakePoint(x , y) ;
		estConstructible = !([figureParent1 pointHorsBorne:coordPoint] || [figureParent2 pointHorsBorne:coordPoint]) ;
	} else estConstructible = NO ;
}


//méthode déléguée pour un segment
- (BOOL)pointHorsBorne:(NSPoint)point
{
	NSPoint u ;
	u.x = point2.x - point1.x ; u.y = point2.y - point1.y ;
	float l = (u.x == 0 ? (point.y - point1.y)/u.y : (point.x - point1.x)/u.x) ;
	return l < 0 || l > 1 ;
}

//méthode déléguée pour une demi-droite
- (BOOL)pointHorsBorne:(NSPoint)point
{
	NSPoint u ;
	u.x = point2.x - point1.x ; u.y = point2.y - point1.y ;
	float l = (u.x == 0 ? (point.y - point1.y)/u.y : (point.x - point1.x)/u.x) ;
	return l < 0 ;
}

//méthode déléguée pour une droite 
- (BOOL)pointHorsBorne:(NSPoint)point
{
	return NO ;
}
```


----------

