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

## Recommended Posts

##### Share on other sites
You could try taking the distance between the end-points and doing least-squares to find the exact location on the line where the shortest distance is. That's kinda computationally intensive, though, and probably wouldn't be useful in realtime.

The other way I can think of would be converting the line segment into a vector, where the vector is equal to the coordinates of one of the end points of the line segment. You could then project the point onto the vector and use the pythagorean theorem to find the perpendicular distance from the point to the line. If the line segment were a line, that would be the closest distance. If the points projection is on the line segment itself, you have your answer. If the projection isn't on the actual line segment, then you can use the first solution I mentioned, only without least squares which makes it really quick (choose whichever end point gives you the smallest result).

There's probably a much simpler way of doing it, but it's Friday night and my brain's pretty fried. Anyone have a better idea?

##### Share on other sites
You want to project the vector between the point and the tailPoint onto the line segment. The value of this projection will then tell you where abouts the nearest point on the line segment lies. For ease of typing I'll give you this in vector format, just break this all down into the components if you dont have any vector classes to work with:

vec2 lineSegment = (headPoint - tailPoint);float proj = (point - tailPoint)dot(lineSegment) / lineSegment.dot(lineSegment);if(proj <= 0.0f)    // closest point on the line segment is the tailPoint{   distance = (point - tailPoint).length();}else if(proj >= 1.0f)    // closest point on the line segment is the headPoint{    distance = (headPoint - point).length();}else    // closest point lies on the line segment itself{    vec2 closestPoint = tailPoint + lineSegment*proj;    distance = (closestPoint - point).length(); }

Does this make sense?

[Edit:] Forgot to normalise the projection ... now fixed ^^

##### Share on other sites
Actually, unless I'm overlooking a programming error your math looks just fine. This is a nice simple way to calculate the distance by finding the perpendicular to the line segment at the given point, and then determining the distance between the two points.

The only odd thing I can see is that you appear to be mixing int's and float's together in your calculations. The compiler should probably convert things for you as you would expect, except for your very last GetMagnitude statement. You are losing any fractional information from the intersection.x and intersection.y values when you pass these to GetMagnitude (it converts them to ints). This will cause small errors in your distance calculation.

One thing I would recommend is to convert all your values to floats before you do any calculations. Other then that, just double check your data in the debugger as you step through the code and make sure the intermediate values are what you'd expect. You should be able to catch the error pretty quickly by doing that.

##### Share on other sites
This was recently discussed in some detail here; the thread includes several derivations of the closest-point-on-line algorithm. The code is very short, so I'll just write it out here (the segment version, since that seems to be what you're interested in):
vector3 ClosestPointOnSegment(vector3 p, vector3 p1, vector3 p2){    vector3 diff = p-p1;    vector3 dir = p2-p1;    float t = dot(diff,dir)/dot(dir,dir);    if (t <= 0.0f) {        return p1;    } else if (t >= 1.0f) {        return p2;    } else {        return p1 + t * dir;    }}
The distance from the point to the segment is then:
float distance = length(p - ClosestPointOnSegment(p,p1,p2));

##### Share on other sites
Both Motorherp and jyk bring up another excellent method of calculating the closest point and distance. Your approach is fine, but their examples are more efficient computationally (but more difficult to visualize what they are doing if your math skills are a little rusty).

If you are going for maximum efficiency, you should rewrite your function using their method. In addition, you can save a divide in some cases by (to use jyk's code sample):

vector3 ClosestPointOnSegment(vector3 p, vector3 p1, vector3 p2){    vector3 diff = p-p1;    vector3 dir = p2-p1;    float dot1 = dot(diff,dir);    if (dot1 <= 0.0f) {        return p1;    }        float dot2 = dot(dir,dir);    if (dot2 <= dot1) {        return p2;    }    float t=dot1/dot2;    return p1 + t * dir;}

[Edited by - FugueInCPP on June 16, 2006 8:31:11 PM]

##### Share on other sites
Hmmm -- sorry for the bad formatting in that last one... I should really learn how to post code samples.

##### Share on other sites
Quote:
 Original post by FugueInCPPHmmm -- sorry for the bad formatting in that last one... I should really learn how to post code samples.
You can use < pre >< /pre > for short samples, and [ source ][ /source ] for longer samples. Also, I'm aware of the 'avoid the divide' optimization, but I tend to favor clarity over efficiency when posting example code.

##### Share on other sites
Ah, so that's how you do it. Thanks for the tip jyk.

I agree, clarity is important -- I just thought you were going for efficiency as your example was 'slightly-more-difficult-to-understand-mathematically' then the algorithm he was using. I didn't mean to confuse the issue.

##### Share on other sites
Quote:
 Original post by FugueInCPPAh, so that's how you do it. Thanks for the tip jyk.I agree, clarity is important -- I just thought you were going for efficiency as your example was 'slightly-more-difficult-to-understand-mathematically' then the algorithm he was using. I didn't mean to confuse the issue.
You didn't confuse the issue; it was probably a good idea to mention that optimization. Although in many contexts that extra divide wouldn't make any difference, in some contexts (such as pixel operations, which the OP mentioned), it might be important that the function be as efficient as possible.

Another little gdnet tip: you can go back and edit your posts using the 'edit' button, so you could reformat the code you posted if you wanted.

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 10
• 16
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632929
• Total Posts
3009277
• ### Who's Online (See full list)

There are no registered users currently online

×