0

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
Punal Manalan
  • 9
  • Are the segments on same plane? Is this a 2D problem? You need to be VERY specific. – Moti Apr 03 '21 at 00:50
  • @Moti Thanks for replying I have updated the question stating this is For 3D and The line segments are not in same Plane – Punal Manalan Apr 03 '21 at 02:05
  • Do you know how to find the distance of a point from a line? – Moti Apr 03 '21 at 03:24
  • @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 – Punal Manalan Apr 03 '21 at 04:03
  • 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. – Moti Apr 03 '21 at 04:36
  • @Moti what to do after getting the Magnitude and Midpoint of each line segment? "determine first if the distance is at the edge or somewhere of the segment itself" how? I Don't Understand can you please explain further. – Punal Manalan Apr 03 '21 at 04:43
  • It could only help but it is not solving. By adding points along the line outside the segment you could at least find the edge closest in case minimal distance between the lines is outside the segment. – Moti Apr 03 '21 at 04:52
  • @Moti thanks for Suggesting this but I already use this as of right now... what I want now is an accurate method to find the Shortest line segment(One point on each line) between Two Line segment – Punal Manalan Apr 03 '21 at 05:06
  • Write the equation of the distance for one line to the other - differentiate to find minimum. This will be the solution. – Moti Apr 03 '21 at 05:13
  • @Moti Like this? A1(Point) to B1B2(Segment), A2 to B1B2, B1 to A1A2 , B1 to A1A2 And Get Centroid of all these? – Punal Manalan Apr 03 '21 at 05:19
  • 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. – Moti Apr 03 '21 at 05:24
  • @Moti Can you please write your comment as an answer instead of a comment, It says comment might get deleted so I am a bit worried – Punal Manalan Apr 03 '21 at 06:16

2 Answers2

0

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

Moti
  • 1,928
  • 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 – Punal Manalan Apr 04 '21 at 02:51
  • 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. – Moti Apr 04 '21 at 03:02
  • 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...

     – Punal Manalan Apr 04 '21 at 06:23
  • 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. – Moti Apr 04 '21 at 07:12
  • 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...? – Punal Manalan Apr 04 '21 at 14:44
  • This is just the shortest distance you found! – Moti Apr 05 '21 at 01:57
  • Sorry for the late reply yesterday I was trying my best to apply your advice to make out a formula... but it seems to only when Line Segments are Away from each other Not on Top of Each other... I updated my Question with Visual Geometry Link please see it – Punal Manalan Apr 06 '21 at 05:40
  • What you mean by "on top of each other"? Intersecting in same plane? – Moti Apr 07 '21 at 06:08
  • What i meant by is that both the line segment would be separated by a small distance, When compared to the shortest distance from Edges of One Linsegment to the other, it would actually be much longer This Link For Visual Representation – Punal Manalan Apr 07 '21 at 06:33
  • I was under the impression that you said that you know how to find the shortest distance between two lines. – Moti Apr 07 '21 at 06:36
  • I know how to Find the Shortest Distance from a POINT to LINE SEGMENT What i want to find is The shortest distance Defined by Two Points(lineSegment) between two lines – Punal Manalan Apr 07 '21 at 08:22
  • Could you write the equations of the lines that include the segments? – Moti Apr 07 '21 at 18:06
  • $\vec p+u\vec q,\\vec r+v\vec s$ Minimum and maximum of u and v is 0,1 This make it a line equation – Punal Manalan Apr 08 '21 at 03:56
  • Try to use plane equations. – Moti Apr 08 '21 at 06:52
0

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.

  • 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 – Punal Manalan Apr 07 '21 at 05:08
  • @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. –  Apr 07 '21 at 07:31
  • 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? – Punal Manalan Apr 07 '21 at 07:35
  • @PunalManalan: right, but you didn't show that. –  Apr 07 '21 at 07:41
  • 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... – Punal Manalan Apr 07 '21 at 08:23
  • Applying \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} I get One = -53.899994, Two = -2.969001 When u,v is both Zero – Punal Manalan Apr 07 '21 at 08:25
  • @PunalManalan: $u=v=0$ is not a solution, so why worry ? Are you unable to solve a $2\times2$ system ? –  Apr 07 '21 at 08:27
  • \vec d\vec q+v,\vec s\vec q=0, is equal to \vec d\vec s+v,\vec s^2=0, . But it is giving different answers... – Punal Manalan Apr 07 '21 at 08:49
  • @PunalManalan: are you able to solve the system ? –  Apr 07 '21 at 09:04
  • $-\vec d\vec q/,\vec s\vec q=v,$ $-\vec d\vec s/,\vec s^2=v,$ When u = 0, But when supplied with values it does not equal the same... – Punal Manalan Apr 07 '21 at 09:11
  • @PunalManalan: I don't think you answered my question. –  Apr 07 '21 at 09:23
  • I mean $-\vec d\vec q/,\vec s\vec q=v,$ is used to solve equation right? – Punal Manalan Apr 07 '21 at 09:56
  • @PunalManalan: I was speaking of the system. –  Apr 07 '21 at 10:10
  • Then I Do not know what you mean I am sorry, could you please tell me how to solve the system! – Punal Manalan Apr 07 '21 at 12:25