Archived

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

HkySk8r187

Closest point to a line segment

Recommended Posts

HkySk8r187    122
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 this post


Link to post
Share on other sites
Kurioes    250
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 this post


Link to post
Share on other sites
Zorodius    259
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 this post


Link to post
Share on other sites
Kurioes    250
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 this post


Link to post
Share on other sites
Tjoppen    122
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 this post


Link to post
Share on other sites
Zorodius    259
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 this post


Link to post
Share on other sites
HkySk8r187    122
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 this post


Link to post
Share on other sites
Zorodius    259
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 this post


Link to post
Share on other sites