Calculating closest point on a line?

jn0k · April 6, 2020, 10:39pm

I’m trying to calculate the closest point on a line segment to another point. I found a function online for returning the distance between a line and a point, and I’m wondering what tweaks need to be made to the math in order for it to return the closest vector3 point on the line instead of the distance.

function distanceToSegment( v, a, b ) --v is the point, a and b are the start and end points of the line
    local ab = b - a
    local av = v - a

    if (av:Dot(ab) <= 0) then -- Point is lagging behind start of the segment, so
        return av.Magnitude -- Use distance to start of segment instead.
    end

    local bv = v - b

    if (bv:Dot(ab) >= 0 ) then -- Point is advanced past the end of the segment, so
        return bv.Magnitude -- Use distance to end of the segment instead
    end

    return (ab:Cross(av)).Magnitude / ab.Magnitude -- Perpendicular distance of point to segment
end

Would I just not return the .Magnitude? Any advice is much appreciated

Senbanistan · April 6, 2020, 10:41pm

There’s actually a built-in Roblox function for doing just that, except with Rays.
Check out Ray:ClosestPoint at Ray | Documentation - Roblox Creator Hub

jn0k · April 6, 2020, 10:43pm

I noticed that too, I’m wondering which method would be more performant as well. Couldn’t I just solve for the point using vector math instead?

Senbanistan · April 6, 2020, 10:45pm

Unless you’re doing these calculations multiple times every frame, performance shouldn’t be an issue.
Even in that scenario, I think Luau has been optimized enough that the performance increase from using your own function and using that one would be minuscule.

jn0k · April 6, 2020, 10:50pm

local function findClosestPointOnSegment(point,start,end)

	local segment = Ray.new(start,(end-start).unit) --just .unit or .unit*Length ?
	
	return segment:ClosestPoint(point) 

end

Would I need to multiply the direction of the ray by the length of the segment?

Senbanistan · April 6, 2020, 10:50pm

You do need to multiply the unit vector by the length, Rays are not infinite.

JimmyChance · April 6, 2020, 11:16pm

Actually, on the wiki it states the ray must be of unit length for the method to work as expected:

Senbanistan · April 6, 2020, 11:39pm

Ah, my mistake. I should have done a bit more reading. Good catch!

Jaycbee05 · April 7, 2020, 1:48am

Just in case you were wondering the way you could have found a point on a line given the distance returned from the function you provided, would be (one way) to use the Pythagorean theorem to find the length of the adjacent side of the triangle given the distance from the line and the distance from the start of the line so that: math.sqrt((FromStart^2)- (Distance^2)) is the length of the adjacent side , where FromStart is the distance from a and v and Distance is the distance returned from your function (the distance perpendicular to your line). Then you would take the unit vector of ab and multiply it by the adjacent length and add that by a making the final equation to find the point on the line a + (ab.unit) * Adjacent :

local Distance = (ab:Cross(av)).Magnitude / ab.Magnitude  --- distance returned from function 
local FromStart = (a-v).Magnitude
local  AdjacentLength =  math.sqrt((FromStart^2)- (Distance^2)) 
local point = a + (ab.unit) * AdjacentLength --- vector pos on line

However adding this to end of your code isn’t mathematically efficient (alot to do with sqrt) so you’d better off using a different method , like using some simple projection (which in this case is faster and more preformant than what i suggested above):

local function ClosetPointOnSegment(v,a,b)
local ab = b - a;
local av = v - a
local  i = av:Dot(ab) /(ab.x^2+ab.y^2)
 i = math.clamp(i, 0,1)
 return a + i*ab 
end

it’s basically what is being described on this stack overflow post