Hi guys, I'm having problems trying to code a fairly simple geometry problem into a C++ project. I've tried many times without success and now I really need some assistant from some better coders/mathmaticians than myself. I am trying to write some code that will calculate the float distance of a known point from a known line in 2D. The data available is the beginning and end points of the line startPx and endPx and the point, called point. These are in my own CPixel object format which have their x and y co-ordinates. Below is the relavent code I have already written using resources on the internet for help but my maths are very rusty (I havent had to use it in a while). If you can help in any way at all I will be eternally greatful, and will do my best to help others on this board (my C++ and general software engineering are better than my maths!). // Begin code sample // I've taken this and simplified it from an online article, I will replace it // with my own structures if I can get this to work! typedef struct tagXY { float x, y; } XY; float CPixelRow::GetMagnitude(int startX, int startY, int endX, int endY) { XY vector; vector.x = endX - startX; vector.y = endY - startY; return (float)sqrt(vector.x * vector.x + vector.y * vector.y); } int CPixelRow::DistancePointLine(CPixel *point, float *distance) { float LineMag; float U; XY intersection; CPixel *headPx = surface.GetHead (); CPixel *tailPx = surface.GetTail (); LineMag = GetMagnitude(headPx->x, headPx->y, tailPx->x, tailPx->y); U = ( ( ( point->x - headPx->x ) * ( tailPx->x - headPx->x ) ) + ( ( point->y - headPx->y ) * ( tailPx->y - headPx->y ) ) ) / ( LineMag * LineMag ); if( U < 0.0f || U > 1.0f ) return 0; // closest point does not fall within the line segment intersection.x = headPx->x + U * ( tailPx->x - headPx->x ); intersection.y = headPx->y + U * ( tailPx->y - headPx->y ); *distance = GetMagnitude(point->x, point->y, intersection.x, intersection.y); return 1; } // End sample code Your expert help will be greatly appreciated. Thankyou, Alex

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?

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.

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));

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]

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

Quote:Original post by FugueInCPP
Hmmm -- 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.

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.

Quote:Original post by FugueInCPP
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.

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.