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