Im trying to make a function that checks if two finite lines cross each other ( returns 0 or 1 ).
First of all I declare these structs
typedef struct _Point{
double x;
double y;
}point;
typedef struct _Line{
int numVertex;
point *vertex;
}line;
Than, here I start the function.
int lineInterceptsLine(line L1, line L2){
double b1,b2,a1,a2,xi,yi;
// First of all Im using both vertex to get each line equation in the form -> y=bx + a. And I start making an exception because if both vertex have the same value for x, b will be 0, but in the equation Ill endup dividing by 0 and will cause error.
if((L1.vertex[1].x-L1.vertex[0].x)==0){
b1 = 0; // Check line1
}else{
b1 = (L1.vertex[1].y-L1.vertex[0].y)/(L1.vertex[1].x-L1.vertex[0].x);
}
if((L2.vertex[1].x-L2.vertex[0].x)==0){
b2 = 0; // Check line 2
}else{
b2 = (L2.vertex[1].y-L2.vertex[0].y)/(L2.vertex[1].x-L2.vertex[0].x);
}
a1 = L1.vertex[0].y-b1*L1.vertex[0].x;
a2 = L2.vertex[0].y-b2*L2.vertex[0].x;
// Now I have both lines equation
if(a1==a2){
if(b1==b2){
}else{
if(((L1.vertex[0].x<0)&&(L1.vertex[1].x>0)&&(L2.vertex[0].x<0)&&(L2.vertex[1].x>0)) ||
((L1.vertex[0].x>0)&&(L1.vertex[1].x<0)&&(L2.vertex[0].x>0)&&(L2.vertex[1].x<0)) ) {
return 1;
}else{
return 0;
}
}
return 0;
}else if(b1==b2){
return 0;
}else{
xi = (b2-b1)/(a1-a2);
yi = ((a2*b1)-(a1*b2))/(a2-a1);
if(((L1.vertex[0].x-xi)*(xi-L1.vertex[1].x))>=0 &&
((L2.vertex[0].x-xi)*(xi-L2.vertex[1].x))>=0 &&
((L1.vertex[0].y-yi)*(yi-L1.vertex[1].y))>=0 &&
((L2.vertex[0].y-yi)*(yi-L2.vertex[1].y))>=0 )
{
return 1;
}
else{
return 0;
}
}
}
I don't know why some tests are not working, like the ones with the following values:
L1.vertex[0].x=0;
L1.vertex[0].y=1;
L1.vertex[1].x=3;
L1.vertex[1].y=1;
L2.vertex[0].x=2;
L2.vertex[0].y=2;
L2.vertex[1].x=2;
L2.vertex[1].y=0;
If you can't find the problem and know an algorithm that works, it would be great as well. Thanks in advance!
The vertical lines will cause challenges, recommend another approach: Parametrized lines L(t) = (Ax,Ay) + t*(Dx,Dy)
// Pseudo code
// D slope
D1 = (L1[1].x - L1[0].x, L1[1].y - L1[0].y)
D2 = (L2[1].x - L2[0].x, L2[1].y - L2[0].y)
// Parametric line
L1(t1) = (L1[0].x, L1[0].y) + t1*D1
L2(t2) = (L2[0].x, L2[0].y) + t2*D2
// Simultaneous equation
// Solve the 2 equations with 2 unknowns t1, t2
(D1.x -D2.x)(t1) = (L2[0].x – L1[0].x)
(D1.y -D2.y)(t2) = (L2[0].y – L1[0].y)
// If determinant is 0, lines are parallel. Special handling
// Else if 0.0 <= t0 & t1 <= 1.0, lines intersect
Details
L1[0] and L1[1] are 2 points that define a segment. (OP uses L1.vertex[0].x, I use the shorten L1..x notation.) L1(t1) is a function defines a line that goes through those two points as a function of t1. Notice when t1 is 0, L1 is (L1[0].x, L1[0].y) and when t1 is 1, (L1 is L1[1].x, L1[1].y). Similar for L2. Now we have 2 Parametric line equations as a function of t1 and t2.
The next step is to find the values of t1 and t2 that generate the same (x,y) point for both lines, in other words, the intersection. Thus:
D1.x = L1[1].x - L1[0].x
D1.y = L1[1].y - L1[0].y
D2.x = L2[1].x - L2[0].x
D2.x = L2[1].y - L2[0].y
L1[0].x + t1*D1.x = L2[0].x + t2*D2.x
L1[0].y + t1*D1.y = L2[0].y + t2*D2.y
// or
DX = L2[0].x - L1[0].x
DY = L2[0].y - L1[0].y
D1.x*t1 - D2.x*t2 = DX
D1.y*t1 - D2.y*t2 = DY
// or in matrix notation
(D1.x - D2.x)(t1) = (DX)
(D1.y - D2.y)(t2) = (DY)
//
d = D1.x*D2.y - (-D2.x)*(-D1.y)
// if d is 0, lines are parallel and need to determine if co-incident or distinct.
t1 = ( DX(-D2.y) - DY*(- D2.x) )/d
t2 = ( DX(-D2.x) - DY*(- D1.x) )/d
Finally we have t1 and t2. If there are both in the range 0 to 1, then the intersection occurred in the original segments. This answers the question "if two finite lines (segments) cross each other?"