#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;
}
![[MGZ]Slug](/data/avatars/m/0/55.jpg?1089234184){kind=avatar}
