OT: 2D/3D math

[narf poit chez BOOM]

Anyone know how to determine the closest point on a line to a point? Rapidly running out of ideas...

Thanks.

[Aiken]

crossing of perpendicular from this point with a line itself?

[Slick]

yeah for 2D:

line: Ax + By + C = 0
Point: (x1, y1)

[saving you the gory details]

<font class="small">Code:</font><hr /><pre>

|Ax1 + By1 + C|
distance between point and line: D = -----------------
square root (A^2 + B^2)

</pre><hr />
notation: | | is absoute value, ^2 is raised to power 2


For 3D, it takes a little more...


Slick.

[TerranC]

Mathematics! Formulas! Variables! Discussion!

Run away! Run away! Math is taking over the world! http://forum.shrapnelgames.com/images/smilies/happy.gif

[narf poit chez BOOM]

<font class="small">Code:</font><hr /><pre>

|Ax1 + By1 + C|
distance between point and line: D = -----------------
square root (A^2 + B^2)

</pre><hr />
So...
<font class="small">Code:</font><hr /><pre>

|A*x1 + B*y1 + C|
distance between point and line: D = -----------------
square root (A^2 + B^2)

</pre><hr />
??

In that case, what are A, B and C?

[Slick]

use some algebra to transform the equation of the line to:

line: Ax + By + C = 0

then use whatever you came up with for A, B &amp; C in the formula I gave to find the distance between the point and the line.

Slick.

[narf poit chez BOOM]

Or, you know, I could do that thing I almost never think of and explain myself...

I'm programming. I have the start XY of the line, the end XY of the line and the XY of the point. And I have no idea how to teach a computer algebra derivation.

[Aiken]

If P1(x1,y1) - startpoint
and P2(x2,y2) - endpoint
Then equation of the line will be:
x*(y2-y1) - y*(x2-x1) - x1*y2 + x2*y1 = 0

so A = y2-y1; B = -(x2-x1); C = -(x1*y2 - x2*y1).

But how to find coordinates of the point in the cross of line and perpendicular?

[narf poit chez BOOM]

Thanks. I'll try to figure it out tommorrow; my brain just crashed.

[Slick]

here's the long story (note that this assumes a knowledge of algebra):

you start with a line and a point. find the slope of the line and call it "m".

the slope of all lines perpendicular to that line now have a slope of -1/m.

next you find the equation of the line going through the point with the slope of -1/m. Here is that equation in the "point-slope" form: (y-y1) = (-1/m) (x-x1)

now you solve the equations for both lines simultaneously to get the point where the perpendicular line meets the original line. There are various algebraic methods for this (too cumbersome for this forum's text editor). you will end up with the solution (x2, y2) which is the intersection of the original line and the perpendicular line going through the point (x1, y1). it also is the closest point on the original line to (x1, y1).

now you use the distance formula to find the distance beween (x1, y1) and (x2, y2).

Distance = square root ((x2-x1)^2 + (y2-y1)^2)

and there you go. I had taken out all the intermediate stuff in the original solution. All it takes is putting the original line into the form: Ax + By + C = 0 then using the formula I gave. This is one of the standard algebraic forms for a line.

=========================================

As far as doing this on a computer, just step through the procedure I laid out here. If you only start with 2 points instead of an equation for the line that joins them, you can easily figure out the equation:

given 2 points: (x3, y3) and (x4, y4)

the slope "m" of the line that joins them is: m = (y4-y3) / (x4-x3)

the equation of the line can be written using either of the original points. I'll use the first one:

(y-y3) = m (x-x3)

using some algebra, you can transform this into:

mx - y + (y3-mx3) = 0

therefore
A = m = (y4-y3) / (x4-x3)
B = -1
C = (y3-mx3) = (y3-[(y4-y3)/(x4-x3)]x3)


Slick.

[narf poit chez BOOM]

Thanks.

[TurinTurambar]

http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif uhg.... horrible nightmares of years past... http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif http://forum.shrapnelgames.com/images/smilies/Sick.gif