Intersecting Line Segments (part 2)

Problem: Determine if two line segments, defined by their end points, intersect.

bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
...
}

Solution:  Yesterday, we looked at trying to solve this problem by figuring out whether all of one line segment was entirely below, above, to the left or to the right of the other (Yesterday's post at:  Intersecting Line Segments (part 1).


However, there were two major bugs in that solution as indicated first, consider the case in pic 1, where part of one line segment is between the x values and y values, but the line segments to do not intersect.  Here, we had a bug yesterday.  

Also, consider where one line segments points are 'inside' the other points, as in pic 2.  Here is another case where we do not have intersection, but we would return true.

So, yesterday's method of trying to figure out how the line's intersect doesn't seem to be getting anywhere.  When this happens in an interviews, it's good to admit defeat and start over at the beginning.


Well, let's look at pic 1 and pic 2, and yesterday's pics (pic 1 and pic 2 below reprinted).  We need to make sure that we cover at least these cases. 

Intuitively, we can see if the points intersect or not pretty simply, they just cross or they don't.  When they don't cross, it's as if the lines aren't long enough to cross.


This is a critical insight.  We can imagine what it means to be 'long enough.'  From a math standpoint, this means that if the line segments are extended to lines, there is a point where they cross.  If the points is on both line segments, they cross, otherwise, they do not.  


This seems to work, but does it cover all cases -- are there cases where two lines will never cross?


Well, there is one -- and it's the special case shown in pic 5 -- parallel lines.  These only intersect when they are part of the same line and the segment overlaps (either the x or the y must).  If we test for this case, we can develop a solution if we remember our high school geometry.

A line is defined as y = mx + b.  Where m is the slope, or (y2-y1) / (x2-x1).  Two lines are parallel if they have the same slope.  If we define two lines, we can then solve the simultaneous equation to see at what x and y values they intersect, and then see if that x or why is part of the same line.


We can use the algorithm:


- Get slopes of both lines


-If not parallel:
    Determine equation for line 1
    Determine equation for line 2
    Solve for the point where they intersect
  if point is part of line segment 1 and line segmeent  2, return true, otherwise return false

If parallel:
    determine b value (constant in line equation) for each line.
    if b values are not the same, return false.
    determine if the x values (or the y values) fall within each other) -- if so, return true, otherwise return false


That's it.


There's some math to determine the equation for each line.  


Diagram 1 shows that we first determine the slope for each line, then solve for the b for each line.  We then figure out the x intercept by setting the lines equal, then the y intercept by plugging any point back in.  We can then see if the intercept point is within both lines.  If it is, they intercept.  If it is not, they do not.

Lots of algebra, and an interviewer may have you muddle through it or not.  Also, depending on the language, there is some epsilon math you may have to do.  You should mention this to the interviewer, but let's ignore that for now as the problem is already somewhat  complicated.  


Coded, this is:
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){

  long m1, m2, b1, b2, xi, yi;


  // Determine slopes
  m1 = (end1->y - start1->y) / (end1->x - start1x);
  m2 = (end2->y - start2->y) / (end2->x - start2x);


  // If not parallel
  if (m1 != m2) {
        b1 = start1->y - (m1 * start1->x);
        b2 = start2->y - (m2 * start2->x);
        xi = (b2-b1)/(m1-m2);
        yi = m1*xi + b1;
    
        // Now we check if (xi, yi) is on segment 1
        if (((start1->x <= xi && end1->y >= xi)&& 
             start1->y <= yi && end1->y >= yi))||

            (start1->x >= xi && end1->y <= xi)&& 
             start1->y >= yi && end1->y <= yi))&&
           //now we check if (xi, yi is on segment 2

           ((start2->x <= xi && end2->y >= xi)&& 
             start2->y <= yi && end2->y >= yi))||

            (start2->x >= xi && end2->y <= xi)&& 
             start2->y >= yi && end2->y <= yi))) 
             return(true);
        else
             return (false);
  } else { // if parallel
       // We'll do this part tomorrow. 
  }



}


There is another bug here around potentially dividing by zero, which we can check for and invert if needed, but let's ignore that for now as this is already a pretty long problem for an interview.  Remaining solution coming tomorrow of for the parallel case.