Line segment collision in C?

[Joseph Duchesne]

Here's the code I've been using:

int lineCollide(float ax,float ay, float bx, float by, float cx, float cy, float dx, float dy)
{
float t=((bx-ax)*(dy-cy)-(by-ay)*(dx-cx)); //since this is used in 2 equasions as the demoninator I get it here
float r=0.0f,s=0.0f; //declare r and s
if (t!=0.0f){ //stops the divide by zero error
r=((ay-cy)*(dx-cx)-(ax-cx)*(dy-cy))/t; //this is a strange formula
s=((ay-cy)*(bx-ax)-(ax-cx)*(by-ay))/t; //but very optomised, and very not-quite mine
}else{
return 0; //if nothing happens
}
if (0.0f<r<=1.0f && 0.0f<s<=1.0f){ return 1; } //if the lines collide
return 0; //if there is no colission
}

For some reason its not working any more, or at least in all cases, any ideas or other line collision functions?

I'm trying to simply find out if the two lines intersect. I don't care about the intersection point.

[Edgar]

I dunno what yours is trying to do but check out: http://www.geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
Specifically the SweepLine::intersect() and isLeft() functions.

[isgoed]

I'm trying to simply find out if the two lines intersect. I don't care about the intersection point.
If that's all you want , all you have to do is check wether the lines are parallel. If they are they don't intersect; else, they do.

[Steven]

I would guess that he means two line segments ;)

[FCCovett]

typedef struct Vector3D
{
float x;
float y;
float z;
}
Vector3D, *Vector3DRef, **Vector3DHdl;

Boolean CheckIntersect_LineSegments( Vector3D a1, Vector3D a2, Vector3D b1, Vector3D b2 )
{
//----------------------------------------------------------------------

float a1yb1y, a1xb1x, a2xa1x, a2ya1y;
float crossa, crossb;

//----------------------------------------------------------------------

a1yb1y = a1.y-b1.y;
a1xb1x = a1.x-b1.x;
a2xa1x = a2.x-a1.x;
a2ya1y = a2.y-a1.y;

//----------------------------------------------------------------------

crossa = a1yb1y * ( b2.x - b1.x ) - a1xb1x * ( b2.y - b1.y );
crossb = a2xa1x * ( b2.y - b1.y ) - a2ya1y * ( b2.x - b1.x );

//----------------------------------------------------------------------

if ( crossb == 0 )
{
return FALSE;
}
else if ( fabs( crossa ) > fabs( crossb ) || crossa * crossb < 0.0f )
{
return FALSE;
}
else
{
crossa = a1yb1y * a2xa1x - a1xb1x * a2ya1y;

if ( fabs( crossa ) > fabs( crossb ) || crossa * crossb< 0.0f )
{
return FALSE;
}
}

//----------------------------------------------------------------------

return TRUE;
}

[Joseph Duchesne]

Thanks all, but instead of watching this post I actually sat down and wrote my own. It works perfectly and is quicker than the polygon collision method I had used before. Here's my code:


int lineCollide(float ax,float ay, float bx, float by, float cx, float cy, float dx, float dy)
{
float tarray[4][2]; //<===== Find the inner bounding of rect ABCD
if (ax<bx){
tarray[0][0]=ax;
tarray[1][0]=bx;
}else{
tarray[0][0]=bx;
tarray[1][0]=ax;
}
if (ay<by){
tarray[0][1]=ay;
tarray[1][1]=by;
}else{
tarray[0][1]=by;
tarray[1][1]=ay;
}
if (cx<dx){
tarray[2][0]=cx;
tarray[3][0]=dx;
}else{
tarray[2][0]=dx;
tarray[3][0]=cx;
}
if (cy<dy){
tarray[2][1]=cy;
tarray[3][1]=dy;
}else{
tarray[2][1]=dy;
tarray[3][1]=cy;
}
float tarray2[2][2]; //<===== Sort Section Two
if (tarray[0][0]<tarray[2][0]) { tarray2[0][0]=tarray[2][0]; }else{ tarray2[0][0]=tarray[0][0]; } //biggest of the small ones
if (tarray[0][1]<tarray[2][1]) { tarray2[0][1]=tarray[2][1]; }else{ tarray2[0][1]=tarray[0][1]; } //biggest of the small ones
if (tarray[1][0]<tarray[3][0]) { tarray2[1][0]=tarray[1][0]; }else{ tarray2[1][0]=tarray[3][0]; } //biggest of the small ones
if (tarray[1][1]<tarray[3][1]) { tarray2[1][1]=tarray[1][1]; }else{ tarray2[1][1]=tarray[3][1]; } //biggest of the small ones
float mab=(ay-by)/(ax-bx); //<===== Find Slopes of Lines
float mcd=(cy-dy)/(cx-dx);
if (mab==mcd) return 0; //the lines are paralell
float yiab=((ax-bx)*ay-ax*(ay-by))/(ax-bx); //<===== Find the y Intercept of Lines
float yicd=((cx-dx)*cy-cx*(cy-dy))/(cx-dx);
float x=(yicd-yiab)/(mab-mcd); //<===== Find the Intersection Points of the Line
float y=mab*x+yiab;
if (x>tarray2[0][0] && x<tarray2[1][0] && y>tarray2[0][1] && y<tarray2[1][1]) { return 1; }else{ return 0; }
}