-
January 29th, 2010, 06:35 AM
#16
Re: Distance between point and line segment
This thing shows up on google if you search for this, and I really hate getting 15 search results that give you "Here's an algorithm that's got your solution in it somewhere! If you can find it! Maybe!" The most important problem here is that while this equation here ALMOST works:
http://mathworld.wolfram.com/images/...dEquation8.gif
It actually treats your segment as a line, which is useless. I found the answer buried in some obscure c code that does a variation on this technique: http://local.wasp.uwa.edu.au/~pbourk...tline/source.c - this contains a check that tells us if the point is within the line segment or not. Due to the similarity of the approaches i was able to integrate this into the previous equation for a function that, after almost 6 freaking hours of research, actually does exactly what we want it to do, under all circumstances.
Code:
float DistanceToPointSquared(float X, float Y)
{
float vx = x1-X, vy = y1-Y, ux = x2-x1, uy = y2-y1;
float length = ux*ux+uy*uy;
float det = (-vx*ux)+(-vy*uy); //if this is < 0 or > length then its outside the line segment
if(det<0 || det>length)
{
ux=x2-X;
uy=y2-Y;
return std::min<float>(vx*vx+vy*vy, ux*ux+uy*uy);
}
det = ux*vy-uy*vx;
return (det*det)/length;
}
-
November 2nd, 2011, 04:45 AM
#17
Re: Distance between point and line segment
keke, Necropost, but.
The code described above fails on the case point: 0,0. Line point0: 1,1, Line point1: 2,2.
The code:
public float DistanceSquared(float X, float Y)
{
float vx = v0.x - X, vy = v0.y - Y, ux = v1.x - v0.x, uy = v1.y - v0.y;
float length = ux * ux + uy * uy;
float det = (-vx * ux) + (-vy * uy); //if this is < 0 or > length then its outside the line segment
if (det < 0)
return (v0.x - X) * (v0.x - X) + (v0.y - Y) * (v0.y - Y);
if (det > length)
return (v1.x - X) * (v1.x - X) + (v1.y - Y) * (v1.y - Y);
det = ux * vy - uy * vx;
return (det * det) / length;
}
takes this into consideration. I think ( run a couple of tests, when point is outside the segment from both ends, above and below).
Also, v0 is first vertex of the segment. v1 is the second one.
-
November 2nd, 2011, 05:41 AM
#18
Re: Distance between point and line segment
This page mentions some useful info too.
Look for 'Line-Point Distance', second paragraph.
http://community.topcoder.com/tc?mod...s&d2=geometry1
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
November 2nd, 2011, 07:21 AM
#19
Re: Distance between point and line segment
This thread is over 9 years old.
-
December 13th, 2012, 08:19 PM
#20
Re: Distance between point and line segment
Originally Posted by Richard.J
can anyone explain why you are digging out a seven year old thread?
Because the distance between a point and a line segment was only relevant pre-2003, right?
-
February 25th, 2015, 11:06 AM
#21
Re: Distance between point and line segment
Originally Posted by JohnW@Wessex
Thank you! Finally! Exactly what I have been looking for for quite a while now.
PS: 2015, and the thread is still relevant
-
March 5th, 2015, 07:45 AM
#22
Re: Distance between point and line segment
For calculating the distance between the point and line http://queforum.com/c-cpp-programs/9...nctions-c.html
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|