typedef struct point {
    int x;
    int y;
} point;

typedef struct line {
    point p1;
    point p2;
} line;

/* 
 * check_lines:
 * This is based off an explanation and expanded math presented by Paul Bourke:
 *
 * It takes two lines as inputs and returns 1 if they intersect, 0 if they do
 * not.  hitp returns the point where the two lines intersected.  
 *
 * This function expects integer value inputs and stores an integer value
 * in hitp if the two lines interesect.  The internal calculations are fixed 
 * point with a 14 bit fractional precision for processors without floating
 * point units.
 */
int check_lines(line *line1, line *line2, point *hitp)
{
    /* Introduction:
     * This code is based on the solution of these two input equations:
     *  Pa = P1 + ua (P2-P1)
     *  Pb = P3 + ub (P4-P3)
     *
     * Where line one is composed of points P1 and P2 and line two is composed
     *  of points P3 and P4.
     *
     * ua/b is the fractional value you can multiple the x and y legs of the
     *  triangle formed by each line to find a point on the line.
     *
     * The two equations can be expanded to their x/y components:
     *  Pa.x = p1.x + ua(p2.x - p1.x) 
     *  Pa.y = p1.y + ua(p2.y - p1.y) 
     *
     *  Pb.x = p3.x + ub(p4.x - p3.x)
     *  Pb.y = p3.y + ub(p4.y - p3.y)
     *
     * When Pa.x == Pb.x and Pa.y == Pb.y the lines intersect so you can come 
     *  up with two equations (one for x and one for y):
     *
     * p1.x + ua(p2.x - p1.x) = p3.x + ub(p4.x - p3.x)
     * p1.y + ua(p2.y - p1.y) = p3.y + ub(p4.y - p3.y)
     *
     * ua and ub can then be individually solved for.  This results in the
     *  equations used in the following code.
     */

    /* Denominator for ua and ub are the same so store this calculation */
    int d   =   (line2->p2.y - line2->p1.y)*(line1->p2.x-line1->p1.x) -
                (line2->p2.x - line2->p1.x)*(line1->p2.y-line1->p1.y);
                
    /* n_a and n_b are calculated as seperate values for readability */
    int n_a =   (line2->p2.x - line2->p1.x)*(line1->p1.y-line2->p1.y) - 
                (line2->p2.y - line2->p1.y)*(line1->p1.x-line2->p1.x);
                
    int n_b =   (line1->p2.x - line1->p1.x)*(line1->p1.y - line2->p1.y) -
                (line1->p2.y - line1->p1.y)*(line1->p1.x - line2->p1.x);
              
    /* Make sure there is not a division by zero - this also indicates that
     * the lines are parallel.  
     *
     * If n_a and n_b were both equal to zero the lines would be on top of each 
     * other (coincidental).  This check is not done because it is not 
     * necessary for this implementation (the parallel check accounts for this).
     */
    if(d == 0)
        return 0;
        
    /* Calculate the intermediate fractional point that the lines potentially
     *  intersect.
     */
    int ua = (n_a << 14)/d;
    int ub = (n_b << 14)/d;
    
    /* The fractional point will be between 0 and 1 inclusive if the lines
     * intersect.  If the fractional calculation is larger than 1 or smaller
     * than 0 the lines would need to be longer to intersect.
     */
    if(ua >=0 && ua <= (1<<14) && ub >= 0 && ub <= (1<<14))
    {
        hitp->x = line1->p1.x + ((ua * (line1->p2.x - line1->p1.x))>>14);
        hitp->y = line1->p1.y + ((ua * (line1->p2.y - line1->p1.y))>>14);
        return 1;
    }
    return 0;
}