Sign in to follow this  

Looking for an implementation of finding the closest two points of 2 3D line segments

This topic is 2543 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

I would like to determine the 2 closest points between 2 3D line segments, even if they are intersecting.

I have already tried this:

http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/

It doesn't work in all cases.

I have also tried this one but I cannot get the "points" - only the distance.

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

I am using XNA 4.0 and C#. A solution in any language is fine - I should be able to translate it to C#.

Thanks

Share this post


Link to post
Share on other sites
Try these values: pp1=1,0,1, pp2=4,0,4 and pp3=1,0,3, pp4=-1,0,5 AND then try these values: pp1=1,0,1, pp2=4,0,4 and pp3=1,0,3, pp4=-2,0,5.

They should yield the same results unless I don't understand how it is supposed to work.

Share this post


Link to post
Share on other sites
Well, it seems that you don't understand how coordinates work...


-2,0,5 and
-1,0,5

are NOT on the same line.

And the algorithm works on infinite lines. In case of segments: what behaviour do you want? You have to define that. (what if the points you look for are outside a/the segment/segments?)

Share this post


Link to post
Share on other sites
Well, it seems you don't understand my question and the "solutions" I have tried.

The link that I referred to is an algorithm for finding the shortest line segment between two line segments. Of course the points aren't on the same line. They are not supposed to be. That is the point (no pun intended).

While I don't understand all of the math involved the link I provided clearly states that it is working on line segments not infinite lines. It is possible that the code and the description are not in sync with each other. But I wouldn't be able to tell.

If you use grid paper and a pencil and plot the line segments I have provided as an example you will clearly be able to see the closest line segment between the two in each example. You will also see that the slight change I made between each example should not affect the answer. (I am using a coordinate system that states right, up and toward the viewer is positive.)

If I am making some sort of mistake in either my interpretation of the algorithm or my expectations of what it is supposed to do please elaborate.

Share this post


Link to post
Share on other sites
No. The algorithm works on LINES.

The word "segment" only refers to the shortest segment between the two lines. Which are infinite. The algorithm doesn't handle segments (read the article again more carefully).

To your example: the segments lie on the same plane, so this shortest segment degrades to a point. The intersection point of the two LINES.

image

As you can see, the two intersection points are not the same.
If you want the algo to work on segments, you have to define the behaviour YOU want and you have to handle the different cases explicitly in the code.

This will involve shortest segment between POINT and line, and in some cases, the shortest segment will be between two endpoints of the two segments.

Share this post


Link to post
Share on other sites
You are correct - they are lines not line segments. I misread the description in the algorithm. (I have been looking for a solution for many days and found too many answers - again my math is obviously very weak or I would have realized my error myself.)

But I still think there is something wrong with the algorithm. It is not providing me with the shorest line segment between two lines. It is providing me the shortest line segment between two lines along a vector. Correct? Using the two points returned from the function I should not be able to create a right triangle relative to the line where the point does not match an endpoint.



Share this post


Link to post
Share on other sites
Quote:
Original post by WrongWayJerry
You are correct - they are lines not line segments. I misread the description in the algorithm. (I have been looking for a solution for many days and found too many answers - again my math is obviously very weak or I would have realized my error myself.)

But I still think there is something wrong with the algorithm. It is not providing me with the shorest line segment between two lines. It is providing me the shortest line segment between two lines along a vector. Correct? Using the two points returned from the function I should not be able to create a right triangle relative to the line where the point does not match an endpoint.


Sorry, but this doesn't make much sense... Would you rephrase it and probably some drawings would help too.

Does the algorithm provide the same results as the green points on the drawing I posted?

Do you thing the green points are wrong in the picture I posted?

Share this post


Link to post
Share on other sites
Let's take a step back. Forget everything you and I have said up to this point. Forget the algorithm I supplied. Here is my problem.

I have 2 line segments in 3D. I don't have lines. I don't want lines. Lines are useless to me. I would like to calculate the shorest line segment between the 2 line segments and I want to now what the two points are that would represent the shortest line segment. I provided a picture above of what I am trying to calculate.

Do you have a solution to the problem I have desribed above?

Share this post


Link to post
Share on other sites
No, I don't have code for you, and I don't have time to write it for you at the moment. Maybe you can find a complete solution, but as I stated in one of my posts: your problem has MANY CASES you have to handle explicitly. I even gave you some terms you have to look for. Like:

shortest segment between point and LINE.


I have an idea, but it's not optimised.

So:
*calculate the shortest segment between the two LINES with the algo.
*calculate the shortest segments between all endpoints to all LINES (obviously only to the other line).
*calculate all the segments between all endpoints.

You have all these POSSIBLE segments (1+4+4 = 9 segments), now get the shortest one that's VALID (both endpoints are inside both original segments)

I hope that's clear.

Share this post


Link to post
Share on other sites
Maybe this will help. In this picture there are 4 line segments drawn in black. I would like to know the shorest distance and the points between the 3 segments on top relative to the 1 segment on the bottom. I would expect the answer to be line segment "a" in all cases since that is the shortest distance. Line segment "c" is not the shortest distance. Does this explain better what I am looking for?



Uploaded with ImageShack.us

Share this post


Link to post
Share on other sites
I've already tried the "point to a line" it suffers from too many complications. I think if I just extend the algorithm i have and I solve for a right triangle when I have the two points I will have my answer.

Share this post


Link to post
Share on other sites
Is it 2D or 3D?

If it's 3D, I think you don't understand the shortest line thing and all the possible cases.

How about this case? (blue and red lines are the original)
image
What is the correct result then?
Your "right triangle" doesn't really make sense: the shortest segment is ALREADY perpendicular to BOTH LINES. Again: LINES. No magic algo will handle segments by itself. You have to EXPLICITLY handle the different cases.


And point to line is easy as breeze.

And in fact, the solution I gave IS an extension to the original algo.


Point to line:
P : point
A : point in line, B: other point
v : direction vector of line (unit length). v = normalise(B-A)
x : closest point on the line to the point

x = A + dot_product(P-A,v)

segment_p1 = P
segment_p2 = x

I don't see no complication...

Share this post


Link to post
Share on other sites
Quote:
I have also tried this one but I cannot get the "points" - only the distance.
You can get the points (that's how the distance is computed - from the points).

Regarding your most recent posts, you shouldn't have to mess around with right triangles or anything like that. If you need a reference implementation, you might try geometrictools.com (you can find documentation and code for various closest-point tests there - can't remember if segment-segment is included, but you might check and see).

Share this post


Link to post
Share on other sites
Yes - my math skills suck. I suspected that the right triangle thing my not work but I threw it out there to see if it would stick. :-) Clearly mine was not the correct answer.

I would like a solution which works in 3D.

I was unable to determine the points from the second algorithm. I believe the values are "normalized" and I was unable to figure out how to get them back into their original world cooridinates.

Share this post


Link to post
Share on other sites
From the algo's documentation:

int LineLineIntersect(
XYZ p1,XYZ p2,XYZ p3,XYZ p4,XYZ *pa,XYZ *pb,
double *mua, double *mub)
...


You have everything here!

*pa and *pb are the two points you are looking for.


I gave the formula to point-line.

I gave the idea, you have everything, you just have to put it together.

You even have the *mua, *mub values, that you can use to determine the validity of the segment.
if( mua >= 0 && mua <= 1.0 && mub >= 0 && mub <= 1.0 )
then valid
otherwise
invalid

The algo in the article is so good, I'll sleep with it.

Share this post


Link to post
Share on other sites
'szecs' - I already explained what my expectations are for this algorithm. If you use the coordinates that I provided as an example you will see that the result does not meet my expectations. This was independently confirmed by another person on another forum. I will demonstrate:

Using ‘int LineLineIntersect( XYZ p1,XYZ p2,XYZ p3,XYZ p4,XYZ *pa,XYZ *pb, double *mua, double *mub’.

Please explain to me these results:

Line segment A(1,0,1 : 4,0,4) compared to Line Segment B(1,0,3 : -1,0,5) returns the result (2,0,2 - 1,0,3) distance: 1.414214
Line segment A(1,0,1 : 4,0,4) compared to Line Segment B(1,0,3 : -2,0,5) returns the result (2.2,0,2.2 - 1,0,3) distance: 1.442221

This is basically a 2D calculation and all I changed was one of the furthest points. The closest point didn’t change and yet the answer did.

Here is the code:

bool LineLineIntersect(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4,
out Vector3 pa, out Vector3 pb, out double mua, out double mub)
{
Vector3 p13, p43, p21;
double d1343, d4321, d1321, d4343, d2121;
double numer, denom;

pa = Vector3.Zero;
pb = Vector3.Zero;
mua = 0;
mub = 0;

// calc the center of line(p3, p4)
p43.X = p4.X - p3.X;
p43.Y = p4.Y - p3.Y;
p43.Z = p4.Z - p3.Z;

// if we are only dealing with a point then exit
if (Math.Abs(p43.X) < double.Epsilon && Math.Abs(p43.Y) < double.Epsilon && Math.Abs(p43.Z) < double.Epsilon)
return (false);

// calc the center of line(p1, p2)
p21.X = p2.X - p1.X;
p21.Y = p2.Y - p1.Y;
p21.Z = p2.Z - p1.Z;

// if we are only dealing with a point then exit
if (Math.Abs(p21.X) < double.Epsilon && Math.Abs(p21.Y) < double.Epsilon && Math.Abs(p21.Z) < double.Epsilon)
return (false);

// calc the center of line(p1, p3)
p13.X = p1.X - p3.X;
p13.Y = p1.Y - p3.Y;
p13.Z = p1.Z - p3.Z;

// get the dotproduct for the points
d1343 = p13.X * p43.X + p13.Y * p43.Y + p13.Z * p43.Z;
d4321 = p43.X * p21.X + p43.Y * p21.Y + p43.Z * p21.Z;
d1321 = p13.X * p21.X + p13.Y * p21.Y + p13.Z * p21.Z;
d4343 = p43.X * p43.X + p43.Y * p43.Y + p43.Z * p43.Z;
d2121 = p21.X * p21.X + p21.Y * p21.Y + p21.Z * p21.Z;

denom = (d2121 * d4343) - (d4321 * d4321);
if (Math.Abs(denom) < double.Epsilon)
return (false);

numer = (d1343 * d4321) - (d1321 * d4343);

mua = numer / denom;
mub = ((mua * d4321) + d1343) / d4343;

if (mua < 0)
{
pa.X = p1.X;
pa.Y = p1.Y;
pa.Z = p1.Z;
}
else if (mua > 1)
{
pa.X = p2.X;
pa.Y = p2.Y;
pa.Z = p2.Z;
}
else
{
pa.X = (float)(Math.Round(p1.X + mua * p21.X, 3));
pa.Y = (float)(Math.Round(p1.Y + mua * p21.Y, 3));
pa.Z = (float)(Math.Round(p1.Z + mua * p21.Z, 3));
}

if (mub < 0)
{
pb.X = p3.X;
pb.Y = p3.Y;
pb.Z = p3.Z;
}
else if (mub > 1)
{
pb.X = p4.X;
pb.Y = p4.Y;
pb.Z = p4.Z;
}
else
{
pb.X = (float)(Math.Round(p3.X + mub * p43.X, 3));
pb.Y = (float)(Math.Round(p3.Y + mub * p43.Y, 3));
pb.Z = (float)(Math.Round(p3.Z + mub * p43.Z, 3));
}

return (true);
}

Share this post


Link to post
Share on other sites
you cannot simply use the results of the line-line function, because it will very very rarely produce a valid result when considering line-segments and you would find almost always that the values mua,mub indicate it is invalid.

Consider coplanar segments, the line-line function would simply find the intersection of the two lines in which the segments lie, this is only the correct result if the line segments infact intersect which in the general case, is practicaly never. Considering non coplanar segments, it's even less likely that the result of line-line would be valid.

To the OP, the results of your test are correct, draw it on paper if you like; you still seem to think that9 this function is working with line segments, and not infinite lines... >.> (Note that the first coordinate in your 'return' is the intersection of the two lines)

Share this post


Link to post
Share on other sites
I understand your expectations perfectly clearly. And I made perfectly clear already, that the algorithm cannot produce those results, and I even explained why. I even proposed a solution. And I even stated more times, that you have to handle all cases separately.
I even explained your results, even made a drawing that explains it. I had been fucking this thread for one hour, I'm done with it.

Share this post


Link to post
Share on other sites

This topic is 2543 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