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:
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))


Comments
Post a Comment