Well lets see... Here''s what I''d do

First calculate the line''s origin ((x1, y1) or (x2, y2)) and its direction (difference of points):

// point: px, py
dx = x1 - x2;
dy = y1 - y2;
// we''ll use x2 and y2 as origin.

The easiest way, I think, to calculate the distance of the point from the line, is expressing the distance from a point on the line in another variable, compute the derivate of this formula, and find the intersection point this way.

//This function won''t take squares as I don''t care about the distance just yet.
DistanceOfPoint(v) = (x2 + dx * v - px)^2 + (y2 + dy * v - py)^2
Now compute the derivate:
2 dx (-px + dx v + x2) + 2 dy (-py + dy v + y2)
// this should cross zero somewhere.. I can''t think of a case where this is not true. I''m not really sure though.

Solving this to v, we find that v = (dx px + dy py - dx x2 - dy y2) / (dx^2 + dy^2).
I used Mathematica for this as I don''t want to spend hours on this. Besides that, I make errors as Mathematica does not.


Now you have v... finding the closest point is easy:
closestx = x2 + dx * v
closesty = y2 + dy * v

But, if v < 0 or v > 1, the closest point lies outside the line segment!. So if v<0, closesty and closesty are actually x2 and y2. If v>1 then the closest point is x1, y1.

Now you can calculate the distance between those points and you''re done. I think/hope (can''t hurt to try).


[ Galactic Conquest | Bananas | My dead site | www.sgi.com | Goegel ]

Here''s how to do it in 3D:

// Return the closest point on the line segment start_end to point.triple Closest(triple start, triple end, triple point){	triple A, B, C;	float t, d;		// Acquire a vector from the start point to the point in question.	A.x = point.x - start.x;	A.y = point.y - start.y;	A.z = point.z - start.z;		// Acquire a vector from the start point to the end point.	B.x = end.x - start.x;	B.y = end.y - start.y;	B.z = end.z - start.z;		// Determine the length of the segment start_end.	d = NonrootLength(B);		// Normalize the vector.	Normalize(&B);		// Calculate the dot product between the two vectors.	t = A.x * B.x + A.y * B.y + A.z * B.z;		// Rule out some special cases.		// t <= 0, meaning behind the start point.		if(t <= 0)			return start;		// t >= the length of start_end, meaning past the end point.		else if(t*t >= d)	// t squared, to avoid an unnecessary square root operation.			return end;				// If the closest point on start_end to point is somewhere along the segment, determine exactly where.	C.x = B.x * t + start.x;	C.y = B.y * t + start.y;	C.z = B.z * t + start.z;		// Return the final value.	return C;}

You can then check the distance between the returned point and the point you''re testing or whatever.

"Baby-killer is a bad word though. Notice how as soon as you say it, you think negative things." - Peon

Yep that works but as far as I can tell it assumes a ray instead of a line segment. Mine does . However, if you don't need these special cases I'd definately go for Zorodius' method as it's way faster.

My method could be extended to 3D, you just need to work out the formulas first. Could be a problem...

By the way, HkySk8r187, does your function return 0.707 instead of 7.07 for the given situation (0.5 * sqrt(2))? In that case try mine, I just tried it and it works.


[ Galactic Conquest | Bananas | My dead site | www.sgi.com | Goegel ]

[edited by - Kurioes on January 6, 2004 1:38:45 PM]

The problem is actually quite simple;

Let the point be P and the line go from A to B.
Build a normalized vector representing the direction of the line, N = ||B-A||
Now the closest point on the line AB, Q, is of a distance (N.P - N.A) from A on the line. If you know how the dotproduct works that''s fairly easy to show. I am a bit too lazy to do that now. Anyway, here''s the formula:

N = ||B-A||
Q = A + N(N.P - N.A)

Here, I took the time to draw a little picture:
[img]http://tjoppen.mine.nu/pointonline.png[/img]

Should work for any arbitrary combination of A, B and P in any dimension.
Oh, and if the point must be between A and B, make sure that it isn''t "behind" A( keep A.N <= P.N ) and it isn''t "in front of" B( keep B.N >= P.N ) either.

That''s all. Hope it helps.

quote:Original post by Kurioes
as I can tell it assumes a ray instead of a line segment.

I believe the second special case (t²>d) should limit it to a line segment.

"Baby-killer is a bad word though. Notice how as soon as you say it, you think negative things." - Peon

Heh I''m sorry.. you''re completely right of course I should''ve looked more carefully.

quote:Original post by HkySk8r187
Seems like that should work Zorodius! Thanks! What is NonrootLength and what does it do? My visual studio .net doesn''t know of the function. Do I need to make it?

NonrootLength is just a function to find the length of a vector.

If you think of a vector as the hypotenuse of a right triangle, then you can use the Pythagorean Theorem to figure out how long it is:

          .         /|        / |       /  |  v   /   |     /    |    /     |   b   /      |  /       | /      ._|/_______|_|     a 

In this illustration, a² + b² = v²
hence, v = √(a²+b²)

If v is a vector, then a is the x-component of v, and b is the y-component of v.

You can extend this into 3D by adding a z-coordinate, then x²+y²+z²=v²

This is great, except that square roots take a while to compute - longer than it takes to square a number. If you don''t need to take one, you shouldn''t. So, here''s the code for that function:

inline float NonrootLength(triple v){	return v.x * v.x + v.y * v.y + v.z * v.z;}

By the way, the ratio between two numbers squared is the square of the ratio between those two numbers:
(a²)/(b²)=(a/b)²

"Baby-killer is a bad word though. Notice how as soon as you say it, you think negative things." - Peon