Intersecting Line Segments (part 1)

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 start with an example to make sure that we understand this problem.  Pic 1 shows an example where two lines intersect and pic 2 shows when they do not.  

We need to return true in the case of pic1 and false in the case of pic 2.

Let's see if the pictures help to guide us to the solution.  In pic 1, we see that the two lines intersect -- and we can start to think about what it means to intersect.  Essentially, on the path from start to end, they go through each other.  


This intuitive definition can hint at a solution.  If the starting x points pass each other when going to the ending x points, and the starting y points pass each other while going to the ending y points, that would seem to suggest that the two lines intersect.  While in English that seems intuitive, let's think about what we mean by 'starting', passing and ending.


It turns out to be really hard to define starting and ending, but look again at pic1 and pic2, and try to think about how we can define starting and then see if something else passes.


Well, what starts to come out is starting and ending don't actually matter; we can choose either point and then see if we pass (or arrive at) the range of x and the range of y values of line2.  If we do, we intersect.  If we don't then we don't intersect.  


We can code this up as:



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




    /* If both x values of line2 are to the left or both
     * are to the right of line1's x values,
     * lines cannot intersect. */
   if ((start2->x <= start1->x && start2->x <= end1->x &&
        end2->x <= start1->x && end2->x <= end1->x) ||
       (start2->x >= start1->x && start2->x >= end1->x && 
        end2->x >= start1->x && end2->x >= end1->x))
            return(false);


    /* If both y values of line2 are above or both are
     * below  line1's y values, lines cannot intersect. */
   if ((start2->y <= start1->y && start2->y <= end1->y &&
        end2->y <= start1->y && end2->y <= end1->y) ||
       (start2->y >= start1->y && start2->y >= end1->y && 
        end2->y >= start1->y && end2->y >= end1->y))
            return(false);


    /* Otherwise, lines must intersect */
    return true;
}


Let's try this with our test examples in pic 1 and pic 2 and see if this works.  They do!


However, there are two major bugs in this code. See if you can find them; we'll get to them tomorrow.


/* Please let me know if you find bugs (other than the two that are part of this problem).  Thank you, Noah */