0
$\begingroup$

Formula, Explanation And code for this is At this Link Basically This was solved in the StackOverflow question i asked...

Let's say AB1, AB2, CD1, CD2. AB1&AB2 and CD1&CD2 3D Points makes a Line Segment. And the Said Line segments are Not in the same Plane.

AP is a point Line segment AB1&AB2, BP is a point Line segment CD1&CD2.

Point1 and Point2 Closest To each other (Shortest distance between the two line segment)

Now, how can I Find the said two points Point1 and Point2? What method should I use?

So Far I have Tried All these Below which works only when both Line segments have the same Magnitude...

Link 1 Link 2

I tried Calculating the centroid of both line segments and calculating the nearest Point on Segment From the midpoint. (I know how to calculate the Closest Point line segment from another Point)

But This only works when Both Line segments are of equal length AND each of Both the Linesegment's MidPoint is perpendicular to Each other and the centroid... Visual Geometry Geogbra3D

AB1 =                                               (6.550000, -7.540000, 0.000000 )
AB2 =                                               (4.540000, -3.870000, 6.000000 )
CD1 =                                               (0.000000, 8.000000, 3.530000 )
CD2 =                                               (0.030000, -7.240000, -1.340000 )
PointCD1AB =                                        (3.117523, -1.272742, 10.246199 )
PointCD2AB =                                        (6.318374, -7.117081, 0.691420 )
PointAB1CD =                                        (0.029794, -7.135321, -1.306549 )
PointAB2CD =                                        (0.019807, -2.062110, 0.314614 )
Magntidue of PointCD1AB - P1LineSegmentCD =          11.866340
Magntidue of PointCD2AB - P2LineSegmentCD =          6.609495
Magntidue of PointAB1CD - P1LineSegmentAB =          6.662127
Magntidue of PointAB2CD - P2LineSegmentAB =          9.186399
Magntidue of PointCD1AB - PointAB1CD =               13.318028
Magntidue of PointCD2AB - PointAB2CD =               8.084965
Magntidue of PointCD1AB - PointAB2CD =               10.433375
Magntidue of PointCD2AB - PointAB1CD =               6.598368


Actual Shortest Point are
Point1 =                                            (0.01, 1.59, 1.48 )  
Point2 =                                            (-1.23, 1.11, 3.13 )
Magnitude of Point1 And Point2 =                     2.1190799890518526
$\endgroup$
12
  • $\begingroup$ Are the segments on same plane? Is this a 2D problem? You need to be VERY specific. $\endgroup$ – Moti Apr 3 at 0:50
  • $\begingroup$ @Moti Thanks for replying I have updated the question stating this is For 3D and The line segments are not in same Plane $\endgroup$ – Punal Manalan Apr 3 at 2:05
  • $\begingroup$ Do you know how to find the distance of a point from a line? $\endgroup$ – Moti Apr 3 at 3:24
  • $\begingroup$ @Moti yes i do know how to find the Shortest Distance from a point to A line Segment, What i want is the Closest Two 3D Point between two Line Segment of varied Magnitude in Different Plane $\endgroup$ – Punal Manalan Apr 3 at 4:03
  • $\begingroup$ By measuring distances for each segment edges/midpoint, you could determine first if the distance is at the edge or somewhere of the segment itself. If you write the distance as function for each point on one line to the other line could be differentiated to get the point of minimal distance from the segment that is contained in a line. $\endgroup$ – Moti Apr 3 at 4:36
0
$\begingroup$

You have equations for one line - for each (x,y,z) that meets one line equation write the function that describes the distance to the other line. I assume that you will get a function with three variables. Differentiate for each (x,y,z) and equal to 0. Three equations will result values for (x,y,z) - this point should be on the line in or outside the segment. If inside - good if outside I think the closest edge of segment will be the solution

$\endgroup$
14
  • $\begingroup$ You have equations for one line - for each (x,y,z) that meets one line equation write the function that describes the distance to the other line For like segment A1&A2 I should take Closest Distance between Point B1 and B2 And Vice-Versa for B1&B2 with Point A1 and A2? you will get a function with three variables Input being(LineStart, LineEnd, Point)Am I correct? Differentiate for each (x,y,z) and equal to 0' I don't Understand This part... Three equations will result values for (x,y,z)` I Am Confused Shouldn't it be 4? Since we are checking A1,A2 And B1,B2 with B1&B2, A1&A2 $\endgroup$ – Punal Manalan Apr 4 at 2:51
  • $\begingroup$ You write the line equations first. Based on the solution you know if the shortest distance between the lines is in the segments or not - if not you move to the edges. $\endgroup$ – Moti Apr 4 at 3:02
  • $\begingroup$ I use this Formula to Find the Closest Point On Line segment From another External Point Let CH Be unit Direction LSS is start Of LineSegment, LSS Is End of LineSegment Get Heading Direction of Capsule from Origin To End CH = LSE - LSS MagLSeg = Magnitude Of CH CH = CH Divide each by MagLSeg Project From Point to Origin Proj = Point - LSS Dot = DotProduct Of Proj by CH Dot = Clamp Dot Between 0 and MagLSeg Result = LSS + CH * Dot This Works Properly Only when Both Line segments Are on X or Y or Z-Axis... $\endgroup$ – Punal Manalan Apr 4 at 6:23
  • $\begingroup$ Start with two lines (not line segments). Once you solve it, you see where the points of the shortest distance lie on each line and based on this you decide if you need to get to the edges - based on the closer edge to the point on each line. $\endgroup$ – Moti Apr 4 at 7:12
  • $\begingroup$ Sorry for the late reply! thanks for explaining further, Now i know the shortest Two points IF Both the Line Segments Are Far from Each Other... ELSE if they are on Top of Each other then How should i find Out the Points Since they are not on Any Edge...? $\endgroup$ – Punal Manalan Apr 4 at 14:44
0
$\begingroup$

We write the equations of the segments vectorially as

$$\vec p+u\vec q,\\\vec r+v\vec s$$ where $0\le u,v\le1$ and minimize the squared distance:

$$(\vec{d}-u\vec q+v\vec s)^2$$ where $\vec d:=\vec r-\vec q$. This is a convex function.

We cancel the gradient and obtain

$$\begin{cases}\vec d\vec s-u\,\vec q\vec s+v\,\vec s^2=0,\\\vec d\vec q-u\,\vec q^2+v\,\vec s\vec q=0.\end{cases}$$ which is an easy system of two equations in the two unkonwns $u,v$.

If the values you obtain are in $[0,1]$, you are done. Otherwise, you need to look for a minimum on the edges. E.g., with $u=0$, the system of equations simplifies to

$$\vec d\vec q+v\,\vec s\vec q=0,$$ giving you $v$. (You obtain the point of the second segment closest to the first endpoint of the first segment.) The squared distance is

$$\left(\vec d-\frac{\vec d\vec q}{\vec s\vec q}\,\vec s\right)^2.$$

Repeat for $u=1$ and for $v=0$ and $v=1$ if necessary.

If you still get no solution in the range, compare to the squared distances between then endpoints. In the end, you keep the shortest of all the computed distances.

$\endgroup$
14
  • $\begingroup$ Both equations should equal Zero Right? But Here it does not equate to zero... AB1 = (6.55, -7.54, 0 ) AB2 = (4.54, -3.87, 6.0 ) CD1 = (0, 8.0, 3.53 ) CD2 = (0.03, -7.24, -1.34 ) Basically this is how my equation is written Q = (AB2 - AB1), S = (CD2 - CD1), D = (CD1 - Q), Alpha = 0.000000, Beta = 0.000000, One = DotProduct(D, S) - (Alpha * DotProduct(Q, S)) + (Beta * DotProduct(S, S)), Two = DotProduct(D, Q) - (Alpha * DotProduct(Q, Q)) + (Beta * DotProduct(S, Q)), One = -53.899994 Two = -2.969001 $\endgroup$ – Punal Manalan Apr 7 at 5:08
  • $\begingroup$ @PunalManalan: your comment is not much readable, but in any case, I don't see you computing $u,v$, so "does not equate zero" makes no sense. $\endgroup$ – user65203 Apr 7 at 7:31
  • $\begingroup$ What I meant is that shouldn't \begin{cases}\vec d\vec s-u\,\vec q\vec s+v\,\vec s^2=0,\\\vec d\vec q-u\,\vec q^2+v\,\vec s\vec q=0.\end{cases} Should equal to Zero? $\endgroup$ – Punal Manalan Apr 7 at 7:35
  • $\begingroup$ @PunalManalan: right, but you didn't show that. $\endgroup$ – user65203 Apr 7 at 7:41
  • $\begingroup$ AB1 = (6.55, -7.54, 0 ), AB2 = (4.54, -3.87, 6.0 ), CD1 = (0, 8.0, 3.53 ), CD2 = (0.03, -7.24, -1.34 ), These 4 Points Represent Two Line Segment... $\endgroup$ – Punal Manalan Apr 7 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.