How does this line-intersection work?

I'm building an Asteroids Game for a class assignement. To finish it I need a line-intersection algorithm/code. I found one that works, but i do not understand the math behind it. How does this work?

point* inter( point p1, point p2, point p3, point p4)
{
point* r;

//p1-p2 is the first edge. 
//p3-p4 is the second edge.
r = new point;
f开发者_JS百科loat x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

//I do not understand what this d represents.
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
// If d is zero, there is no intersection
if (d == 0) return NULL;

// I do not understand what this pre and pos means and
// how it's used to get the x and y of the intersection
float pre = (x1*y2 - y1*x2), pos = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * pos ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * pos ) / d;

// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) ||
        x < min(x3, x4) || x > max(x3, x4) ) return NULL;
if ( y < min(y1, y2) || y > max(y1, y2) ||
        y < min(y3, y4) || y > max(y3, y4) ) return NULL;

cout << "Inter X : " << x << endl;
cout << "Inter Y : " << y << endl;

// Return the point of intersection
r->x = x;
r->y = y;
return r; 
}

Determining the intersection of two lines in a two-dimensional plane, if any (they could be parallel) is a classical math problem. The algorithm you found is based on solving a system with two linear equations. This is done by computing the determinant (d). If zero, then the lines are parallel. Otherwise the point of intersection is computed.

See for example this tutorial for a detailed description of the formula: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2

They're determinants.

point* inter( point p1, point p2, point p3, point p4)
{
    point* r;

    //p1-p2 is the first edge. 
    //p3-p4 is the second edge.
    r = new point;

As others have already commented, the above can/will leak memory. Better use a smart pointer, e.g. std::auto_ptr.

    float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
    float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

    //I do not understand what this d represents.
    float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

First you need to know about dot product of two vectors.

Let X and Y be vectors of length 1 in the directions of x-axis and y-axis, respectively. Then define X*X = 1, Y*Y = 1, and X*Y = 0, which is a kind of multiplication (or just an operation) yielding the length of the projection of one vector onto the other, times the other's length (or in other words, the product of the lengths of the vectors times cosine of angle between them). Then if two vectors a and b are a = a.x*X + a.y*Y and b = b.x*X + b.y*Y, then a*b = a.x*b.x + a.y*b.y, because those terms with X*Y are zero, dropping out.

And amazingly that generalization yields the lengths of the vectors times cosine of angle between them for vectors in arbitrary directions, which means for parallel vectors, the product of their lengths, and for perpendicular vectors, 0. :-)

Let edge1 = p1-p2, and edge2 = p3-p4. Then the above computes edge1.x*edge2.y - edge1.y*edge2.x = [edge1.x, edge1.y]*[edge2.y, -edge2.x]. The latter vector is edge2 rotated 90 degrees. Now if that rotated edge2 is perpendicular to edge1 then edge1 and edge2 must be parallel and can't intersect. And in that case this dot product is 0.

    // If d is zero, there is no intersection
    if (d == 0) return NULL;

    // I do not understand what this pre and pos means and
    // how it's used to get the x and y of the intersection
    float pre = (x1*y2 - y1*x2), pos = (x3*y4 - y3*x4);
    float x = ( pre * (x3 - x4) - (x1 - x2) * pos ) / d;
    float y = ( pre * (y3 - y4) - (y1 - y2) * pos ) / d;


    // Check if the x and y coordinates are within both lines
    if ( x < min(x1, x2) || x > max(x1, x2) ||
            x < min(x3, x4) || x > max(x3, x4) ) return NULL;
    if ( y < min(y1, y2) || y > max(y1, y2) ||
            y < min(y3, y4) || y > max(y3, y4) ) return NULL;

    cout << "Inter X : " << x << endl;
    cout << "Inter Y : " << y << endl;

    // Return the point of intersection
    r->x = x;
    r->y = y;
    return r; 
}

Oh dear. I don't feel like analyzing that... But if it works, then it's solving set of two equations in two unknowns to determine intersection point of the infinite lines through the edges, then checking whether that intersection point is within edges.

Cheers & hth.,

You are basically calculating the slope of one line relative to (a coordinate system parallel to the) the other line. The d is zero, they're parallel. Then it calculates the intersection in that coordinate system, and then moves it back to the base coordinate system.