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
Looking for an implementation of finding the closest two points of 2 3D line segments
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?
Author
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.
They should yield the same results unless I don't understand how it is supposed to work.
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?)
-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?)
Author
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.
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.
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
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.
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.
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.
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.
Author
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.
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.
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
