Wednesday, March 5, 2014

Code Bits: Linear Equation From Two Points

These days, I've been building a simple 2D physics engine to test with. While I was programming the collision detection, I needed to find the equation of the line between two points. I show a little bit of the Algebra here and write some code. I want the linear equation to be in standard form because I find it to be more useful than slope-intercept form.

Here is the standard form of a 2D linear equation:

\[\begin{aligned} Ax + By + C = 0 \end{aligned} \]
How do we calculate A, B, and C?

Method One: Calculating from Slope-Intercept
One way to calculate A, B, and C is to start with the slope-intercept form of the line and use some Algebra until its in the standard form. The following is the slope intercept form:
\[\begin{aligned} y = mx + b \end{aligned} \] In this form, m is the slope of the line and b is the y-intercept. This is m and b are fairly easy to figure out. For points (x_0, y_0) and (x_1, y_1) \[\begin{aligned} m = \frac{y_1 - y_0}{x_1 - x_0} \end{aligned} \] \[\begin{aligned} b = y_0 - x_0(\frac{y_1 - y_0}{x_1 - x_0}) \end{aligned} \] After filling in the variables and manipulating it so it is in the form whereby the equation equals zero, we get this: \[\begin{aligned} (y_1 - y_0)x + (x_0 - x_1)y + ((x_1 - x_0)y_0 - (y_1 - y_0)x_0) = 0 \end{aligned} \] so ... \[\begin{aligned} A = (y_1 - y_0) \\ B = (x_0 - x_1) \\ C = (x_1 - x_0)y_0 - (y_1 - y_0)x_0 \\ \end{aligned} \] 
Method Two:
The second method takes some special properties of the linear equation into account. Notice the picture below:

The direction of the normal vector is the direction of the vector from (x0, y0) to (x1, y1) rotated 90 degrees. A and B in the linear equation can be thought of as a vector whose direction is the same as the normal vector. So we can calculate A and B just by calculating the normal vector. If we normalize this vector (make the magnitude 1.0), it will also be more useful when doing collision detection calculations. C is the dot product of the the normal vector and any point on the line.

Here's the code for method two:

typedef float vec2[2];

void Normalize2(const vec2 in, vec2 out)
    float inv_length = 1.0f / sqrtf((in[0] * in[0]) + (in[1] * in[1]));
    out[0] = in[0] * inv_length;
    out[1] = in[1] * inv_length;

float DotProduct2(const vec2 a, const vec2 b)
    return (a[0] * b[0]) + (a[1] * b[1]);

void LineFromTwoPoints(const vec2 p1, const vec2 p2, float &A, float &B, float &C)
    // first calulate and normalize a vector from p1 to p2
    vec2 dir;
    dir[0] = p2[0] - p1[0];
    dir[1] = p2[1] - p1[1];
    Normalize2(dir, dir);

    // calculate the normal vector of the segment this will be our A and B
    vec2 normal;
    A = normal[0] = -dir[1];
    B = normal[1] = dir[0];

    C = -DotProduct2(normal, p1);
The two methods give the same formula. In method two I make sure the magnitude of the vector (A B) is 1. This can be done using method one as well by dividing A, B, and C by the square root of ((A * A) + (B * B))