Check finite line interception C

Question

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!

Answer 1

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?"

Answer 2

I'd restructure the code entirely if I were you. You can lose efficiency quickly the way that you're doing it now. Try something like this;

/* 2D point */
typedef struct _Point{
  float x;
  float y;
} point;
/* 2D line data */
typedef struct _LineSegmentData{
  point* a;
  point* b;
} lineSegmentData;

/* General shape structure */
typedef struct _Shape shape;
typedef struct _Shape{
  void* shapeData;
  char(*shapeIntersect)(shape*,shape*);
};
    /* Shape hierarchy data */
typedef struct ShapeTree{
  shape* left;
  shape* right;
} shapeTree;

Or something similar, then use a bounding box hierarchy and function pointers to make everything a lot more simple. Or, if you're not a big fan of function pointers, just use the same points you'd use to define a segment to define a box, and have a char isLine variable as part of the structure.

The efficiency of your code will go way way up (binary search), and be way easier to debug.

All the best!

Answer 3

1. on the assignment part, we know that you want to know is two line segment cross or not.
2. I don't know the numVertex means in the struct you defined, and the comment is really hard to read for me, so I rewrite one, I hope it can help u.

first, two points(start point and end point) can determine a straight line, If two line segment crossed(line A and line B), we can see two points of line A is on the different sides of line B (or one point is a port of line B), else they are not crossed.

typedef struct {
    int x, y;
} point;

typedef struct {
    point sp;    // start point
    point ep;    // end point
} line;

int is_segment_line_cross(line l1,  line l2)
{
    int sidea, sideb, side;     

    int l1_x_vector = l1.sp.x - l1.ep.x;
    int l1_y_vector = l1.sp.y - l1.ep.y;

    int l1_l2_ax_vector = l1.sp.x - l2.sp.x;
    int l1_l2_ay_vector = l1.sp.y - l2.sp.y;

    int l1_l2_bx_vector = l1.sp.x - l2.ep.x;
    int l1_l2_by_vector = l1.sp.y - l2.ep.y;

    sidea = l1_x_vector * l1_l2_ay_vector - l1_y_vector * l1_l2_ax_vector;
    sideb = l1_x_vector * l1_l2_by_vector - l1_y_vector * l1_l2_bx_vector;

    side = sidea * sideb;

    if (side <= 0) {
       return 1;
    } else {
       return 0;
    }

}

Why? You can get more from here