Intersecting Line Segments (part 3)

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: Let's wrap this up. Yesterday, we took this to the case where two lines are parallel (we ignored epsilon addition and dividing by 0, but these are easy error conditions to add if you'd like and if you can get this far, let's say that you could.


So, yesterday we had:


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. 
  }



}


Now, let's finalize this to get the parallel part.  First, if the two line segments are parallel, they must be the same line to intersect, which we can determine by checking the 'b' value as we did above.  Then, if either end point (x or y) falls within the range of the other, they must intersect.  


Coded, the full solution (minus the two caveats 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
        // if the b values are not the same, cannot intersect
        if (b1 != b2) return (false);
        /* if they are the same, see if the x value of the   
         * first line segment falls inside that of the second */
        return ((start1->x >= start2->x && start1->x <= end2->x)    
            || (start1->x <= start2->x && start1->x >= end2->x));
     
  }

}


Now, except for the two caveats of: 1) comparing longs, which should be done with epsilon comparison, and 2) not dividing by zero, we're in good shape.  If you would like, add the error conditions -- and you always should in an interview.


In fact, this is an example of a particularly tricky problem.  The first solution in part 1 did not get us anywhere and we had to start over -- which is fairly common in interviews.  Then, when we figured out how to do the problem, the math was fairly involved.  Coding turned out to be relatively simple, but long with many places to slip up.  And, there are lots of error conditions to check too.


/* Please let me know if you find any bugs or have alternate solutions.  Thank you, Noah */