# Need help finding closest line segment between two line segments

Hello,
I need a function that returns the closest points UV between two line segments AB and CD
the issue is I’m not very good at math and haven’t found much reference online.

here’s an illustration:

and here’s a function i had wrote that partially achieves the desired result but not exactly what i’m looking for (i don’t recommend using it as a reference):

``````function closest_point_between_line_segments(a_1, a_2, b_1, b_2)
local alpha = 0
local plane_normal = (b_2 - b_1)
local parallel = plane_normal.Unit:Dot((a_2 - a_1).Unit) == 1 or plane_normal.Unit:Dot((a_2 - a_1).Unit) == -1
if parallel then
local center = vector_library.lerp(b_1,b_2,vec3.new(1,1,1) * 1)
local p = closest_point_on_line_segment(a_1,a_2,center)
alpha = (a_1 - p).Magnitude / (a_1 - a_2).Magnitude
else
local project_a_1 = project_to_plane(a_1,b_1,plane_normal)
local project_a_2 = project_to_plane(a_2,b_1,plane_normal)
local closest_point = closest_point_on_line_segment(project_a_1,project_a_2,b_1)
alpha = (project_a_1 - closest_point).Magnitude / (project_a_1 - project_a_2).Magnitude
end
local point = vector_library.lerp(a_1,a_2,(vec3.new(1,1,1) * alpha))

return point
end;
``````
2 Likes

I would start by solving this for two lines (instead of segements), since that only involves one “case”. For line segments there are three cases:

• The shortest line is within both segments
• The shortest line is from one endpoint to inside the other segment
• The shortest line is between one endpoint to another

For lines, consider that the shortest line will always have a direction equal to the normal of the plane formed by the two lines.
Now construct two planes with that same normal, one containing line A and the other containing line B. Since these planes are parallel, the distance between them is a constant and can be found by projecting any vector between the two onto the normal vector.
Now you know the direction and length of the shortest line solution, you just need to find where that vector exactly fits on one line such that it gives a point on the other line. There may be one or infinite solutions (if the lines are parallel). I’m not sure how to do this last step but it will probably involve solving a system of equations such that:
`O1 + D1*a + S = O2 + D2*b`

You also know that S must be perpendicular to both lines, that is: Dot(D1, S) and Dot(D2, S) must both be zero.

Where O and D are the origins and directions of the lines, S is your solution vector (known direction and length), and a, b are unknown constants.

3 Likes

Check out https://geomalgorithms.com/code.html, especially `dist3D_Segment_to_Segment` in `C07_Line_Line_Distance.cpp`.

2 Likes

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.