#### Archived

This topic is now archived and is closed to further replies.

# Closest point to a line segment

This topic is 5308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I know this has been asked before and I''ve read all those posts but I still cannot make a function that works properly. I need to give the function a point (x,y) and a line segment (x1,y1) and (x2,y2) and have it tell me the distance from the point to the closest point on the line segment. Here is what I have, it works sometimes but not always.
float DistanceToLine(float PX,float PY,float X1,float Y1,float X2,float Y2)
{
float A = Y1 - Y2;
float B = X2 - X1;
float C = X1 * Y2 - X2 * Y1;
float Distance = fabs((A * PX + B * PY + C) / (A ^ 2 + B ^ 2) ^ 0.5);
// If the line is running left to right

if (X1 < X2)
{
if (PX < X1)
return (X1 - PX);
else if (PX > X2)
return (PX - X2);
else
return Distance;
}
// If the line is running right to left

else if (X1 > X2)
{
if (PX > X1)
return (PX - X1);
else if (PX < X2)
return (X2 - PX);
else
return Distance;
}
// If the line is vertical

else if (X1 == X2)
{
// If the vertical line is top to bottom

if (Y1 < Y2)
{
if (PY < Y1)
return (Y1 - PY);
else if (PY > Y2)
return (PY - Y2);
else
return Distance;
}
// If the vertical line is bottom to top

else if (Y1 > Y2)
{
if (PY > Y1)
return (PY - Y)1;
else if (PY < Y2)
return (Y2 - PY);
else
return Distance;
}
}
}

I tried putting in point (6,9) and line (5,11)(6,10). The result should be 1 but it gives me 7.07 instead. Dont know what the problem is. If someone can rewrite this function and explain this to be a little more that would be great. I''ve looked at so many math formulas but can''t seem to get a working function written. Thanks guys.

##### Share on other sites
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 ]

##### Share on other sites
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

##### Share on other sites
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]

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
Heh I''m sorry.. you''re completely right of course I should''ve looked more carefully.

##### Share on other sites
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?

##### Share on other sites
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

##### Share on other sites
I got it all working now. Thank you very much.

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 19
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631761
• Total Posts
3002177
×