Sign in to follow this  

Closest point on line segment to another segment... 2D

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I’m at a stage where I need to determine the closest point on a line segment to another line segment in two dimensions (for the greater purpose of determining the closest point on a 2D triangle to a line segment). I’ve searched around using Google but can’t seem to yield any particularly useful results. I’ve tried a few things that didn’t seem to work, though it might merely have had something to do with problems in other parts of my program. I am hoping someone here might be able to give me a hand with this one. Thanks, Jackson Allan

Share this post


Link to post
Share on other sites
You can find an explanation of line-line intersection on this page. If there is an intersection within the segments, you have the closest point. Otherwise, clamp Ua and Ub (variables on that page) to 0..1 and you have the closest points.

Share this post


Link to post
Share on other sites
I have used the methods described here and they seemed to work out fairly well. I'm sure someone will be along shortly to tell you a dozen more efficient methods though.

Also you will have to adapt it to compare two line-segments instead of a segment and a point. I suppose you could use the method above to check the distance of each endpoint of line segment A against segment B to see which is closer. I guess check for perpendicularity or parrallel...ness... between the two segments first. If they are exactly parallel there may be many points which are the same distance apart.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
If there is an intersection within the segments, you have the closest point. Otherwise, clamp Ua and Ub (variables on that page) to 0..1 and you have the closest points.
Are you sure about that last bit? For two non-intersecting segments in 2d, there are orientations where clamping the parameters to [0,1] won't give the closest points (but maybe I'm misinterpreting).

@ the OP: In any case, if you want an easy solution in 2d, I think you can just find the closest point on each segment to each endpoint of the other (4 tests in all) and take the pair with the minimum (squared) distance. I've never actually done it this way, so I can't swear by it. The generic method is probably about equally efficient, and has the advantage that it will work in 3d also without any change to the code (other than using 3d vectors instead of 2d). You do have to handle the parallel case, which can cause robustness problems if not tested for correctly. The overall algorithm can be fomulated in a number of ways (perpendicular segment, minimization of a function, etc.) but each approach reduces to the same thing, more or less. For example implementations, check out Graham's article in GPG, or the source code section at geometrictools.com.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
If there is an intersection within the segments, you have the closest point. Otherwise, clamp Ua and Ub (variables on that page) to 0..1 and you have the closest points.
As jyk indicated, this is not a correct approach. There are configurations where the supporting lines of the line segments intersect outside the segments, but the closest points on the segments are the endpoint of one segment and an interior point of the other segment.

Quote:
Original post by jyk
@ the OP: In any case, if you want an easy solution in 2d, I think you can just find the closest point on each segment to each endpoint of the other (4 tests in all) and take the pair with the minimum (squared) distance.
Almost. You need to include the zeroth (aka fifth) case: intersecting the supporting lines of the line segment and reporting intersection if they intersect inside both segments (and if not, performing the other four tests).

In 3D the zeroth test corresponds to testing if the closest points between the lines both lie inside their corresponding line segments, so the 2D and 3D cases aren't really similar in that case, so it's not as simple as just switching "Vector2D" to "Vector3D" in the code to turn 2D code into 3D code. (But if you're willing to let the 2D code do extra work it wouldn't need to have, then you can make them the same.)

Share this post


Link to post
Share on other sites
Of course your points are correct Christer (as always!), but just to come to my own defense:
Quote:
Almost. You need to include the zeroth (aka fifth) case: intersecting the supporting lines of the line segment and reporting intersection if they intersect inside both segments (and if not, performing the other four tests).
That's actually what I meant (that the 4 point-segment tests should follow the intersection test), but I realize I didn't make that entirely clear.
Quote:
In 3D the zeroth test corresponds to testing if the closest points between the lines both lie inside their corresponding line segments, so the 2D and 3D cases aren't really similar in that case, so it's not as simple as just switching "Vector2D" to "Vector3D" in the code to turn 2D code into 3D code. (But if you're willing to let the 2D code do extra work it wouldn't need to have, then you can make them the same.)
Yes, I'll again try to rephrase in a better way: you can use the same code in 2d and 3d, but I don't mean to imply that you necessarily should. In my own code I have a single function that handles distance tests between lines, rays, and segments in 2d and 3d (the function is templated by dimension, and by linear component type for correct handling of the boundary cases). Whether this is a good approach is probably somewhat context-dependent, but I think it has some advantages.

As for efficiency, I haven't carefully compared the general method with the 2d-specific version, but I'm sure the latter is a little faster. I suppose if segment-segment distance tests in 2d ever became a bottleneck I would consider a different approach, but in general I tend to opt for genericity where possible. I don't know whether the efficiency issue would be a factor in the OP's application, but I just wanted to make him aware that using the general dimension-independent algorithm was an option.

Share this post


Link to post
Share on other sites
I think the solution is pretty straighforward. Since we are dealing with segments, an end point of the first segment must be the closest point to the second segment. Just compute the distance from the second segment to both first segment's end points and use the one which is closer.

Peace

Share this post


Link to post
Share on other sites
Quote:
Original post by bboyBladeJ
I think the solution is pretty straighforward. Since we are dealing with segments, an end point of the first segment must be the closest point to the second segment.
Draw a couple of examples and you'll quickly see that this is not the case. As has already been explained, if the segments do not intersect you have to test both endpoints of each segment against the other segment, for a total of 4 tests in all, to find the closest pair of points. This is the brute-force approach, which has the advantage of being easy to code and is probably not that much slower than the optimized version. However, a more efficient implementation will use the results of the intersection test to determine the actual closest points in a more direct manner.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this