Jump to content
  • Advertisement
Sign in to follow this  
WrongWayJerry

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

This topic is 2845 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
Advertisement
Quote:
Original post by WrongWayJerry
I have already tried this:

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

It doesn't work in all cases.

In what case does it not work?

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
Actually, the link you provided (first) clearly states it is working on two infinite lines and finding the shorted line segment between them. not the shortest line segment between two other line segments :P

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!