[SOLVED] Math: Shortest distance from point to line (EDITED)

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: [Help] Math: Shortest distance from point to line (EDITE

Post by micha »

Ref wrote:Saw the typo and after correction seems to work for me.
Question:
Easy to find closest-point-on-line but pretty mess to get closest-point-on-line-segment.
Do you have a 'neat' way of doing this?
This is the 'neatest' I can come up with:

Code: Select all

function ClosestPointOnLineSegment(px,py,x1,y1,x2,y2)
  local dx,dy = x2-x1,y2-y1
  local length = math.sqrt(dx*dx+dy*dy)
  dx,dy = dx/length,dy/length
  local posOnLine = math.min(length, math.max(0,dx*(px-x1) + dy*(py-y1)))
  return x1+posOnLine*dx,x2+posOnLine*dy
end
The only difference to a closest-point-on-line-calculation is the clamping of the posOnLine. This is a coordinate along the line segment. If the point has to be on the line segment, then this coordinates has to be between zero and length.
User avatar
XHH
Citizen
Posts: 85
Joined: Thu Jun 20, 2013 6:43 pm
Location: US
Contact:

Re: [Help] Math: Shortest distance from point to line (EDITE

Post by XHH »

Sorry that didn't work. But I did figure out how to do it! Should I post the solution?
I like to draw and program :)
davisdude
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: [Help] Math: Shortest distance from point to line (EDITE

Post by davisdude »

If you want to. The whole point of the forums is to help people out. It would help somebody with the same problem as you.
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim
User avatar
Ref
Party member
Posts: 702
Joined: Wed May 02, 2012 11:05 pm

Re: [Help] Math: Shortest distance from point to line (EDITE

Post by Ref »

Mr. Typo again! :)
try changing:

Code: Select all

return x1+posOnLine*dx,x2+posOnLine*dy
to

Code: Select all

return x1+posOnLine*dx,y1+posOnLine*dy
Haven't tried to test it too much yet.
User avatar
XHH
Citizen
Posts: 85
Joined: Thu Jun 20, 2013 6:43 pm
Location: US
Contact:

Re: [Help] Math: Shortest distance from point to line (EDITE

Post by XHH »

Here's my code. You just need to use distLine(LINE,POINT). I was hesitant to post this because I used it in Python. It can be easily changed back to Lua using keywords like function and local.

Code: Select all

#Compute the distance from LINE(x1,y1,x2,y2) to POINT(x,y)

def distLine(line,point):
        A,B = [line[0],line[1]],[line[2],line[3]]
        C = point
        if self.distance(A,B) != 0:
            dist = cross(A,B,C)/self.distance(A,B)
        else:
            dist = self.cross(A,B,C/1)
        dot1 = dot(A,B,C)
        if dot1 > 0:return distance(B,C)
        dot2 = dot(B,A,C)
        if dot2 > 0:return distance(A,C)
        return abs(dist)

def dot(A,B,C):
        AB,BC=[0,0],[0,0]

        AB[0] = B[0]-A[0]
        AB[1] = B[1]-A[1]
        BC[0] = C[0]-B[0]
        BC[1] = C[1]-B[1]
        dot = AB[0] * BC[0] + AB[1] * BC[1]
        return dot

    #Compute the cross product AB x AC
def cross(A,B,C):
        AB,AC = [0,0],[0,0]

        AB[0] = B[0]-A[0]
        AB[1] = B[1]-A[1]
        AC[0] = C[0]-A[0]
        AC[1] = C[1]-A[1]
        cross = AB[0] * AC[1] - AB[1] * AC[0]
        return cross

    #Compute the distance from A to B
def distance(A,B):
        d1 = A[0] - B[0]
        d2 = A[1] - B[1]
        return math.sqrt(d1*d1+d2*d2)
I like to draw and program :)
User avatar
Ref
Party member
Posts: 702
Joined: Wed May 02, 2012 11:05 pm

Re: [SOLVED] Math: Shortest distance from point to line (EDI

Post by Ref »

I think Micha's code is pretty neat.
Attachments
closest_point2.love
simple test of Micha' code
(1.08 KiB) Downloaded 145 times
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: [SOLVED] Math: Shortest distance from point to line (EDI

Post by micha »

Thanks Ref. I definitely go for neatness, whenever possible :)
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: [SOLVED] Math: Shortest distance from point to line (EDITED)

Post by darkfrei »

I've googled it a lot of times, my solution:

Code: Select all

local function distPointToLine(px,py,x1,y1,x2,y2) -- point, start and end of the segment
	local dx,dy = x2-x1,y2-y1
	local length = math.sqrt(dx*dx+dy*dy)
	dx,dy = dx/length,dy/length
	local p = dx*(px-x1)+dy*(py-y1)
	if p < 0 then
		dx,dy = px-x1,py-y1
		return math.sqrt(dx*dx+dy*dy), x1, y1 -- distance, nearest point
	elseif p > length then
		dx,dy = px-x2,py-y2
		return math.sqrt(dx*dx+dy*dy), x2, y2 -- distance, nearest point
	end
	return math.abs(dy*(px-x1)-dx*(py-y1)), x1+dx*p, y1+dy*p -- distance, nearest point
end
So you can get (and highlight) the nearest segment of a polyline:

Code: Select all

function nearestSegmentInLine (x, y, line)
	local x1, y1, x2, y2, min_dist
	local nx, ny, px, py
	local ax,ay = line[1], line[2]
	for j = 3, #line-1, 2 do
		local bx,by = line[j], line[j+1]
		local dist, px,py = distPointToLine(x,y,ax,ay,bx,by)
		if not min_dist or dist < min_dist then
			min_dist = dist
			x1, y1, x2, y2 = ax,ay,bx,by
			nx,ny = px,py
		end
		ax, ay = bx, by
	end
	return x1, y1, x2, y2, nx, ny -- segment, nearest point
end
Attachments
2021-09-18T10_46_18-Untitled.png
2021-09-18T10_46_18-Untitled.png (29.45 KiB) Viewed 4022 times
nearest-sector-01.love
(1.44 KiB) Downloaded 99 times
Last edited by darkfrei on Fri Oct 22, 2021 9:11 pm, edited 2 times in total.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: [SOLVED] Math: Shortest distance from point to line (EDITED)

Post by darkfrei »

So, if the drawn line has different colors along the it's length, we can set to every point in window the color of the nearest sector of this line:

The gradient function:

Code: Select all

function get_red_blue_gradient_color (t) -- t is between 0 as red to 1 as blue
	local r = 2-4*t
	local g = t < 1/2 and 4*t or 4-4*t
	local b = -2 + 4*t
	r = math.min(math.max(0, r), 1)
	g = math.min(math.max(0, g), 1)
	b = math.min(math.max(0, b), 1)
	return {r^0.5,g^0.5,b^0.5,1}
end
Attachments
nearest-sector-02-line.png
nearest-sector-02-line.png (25.98 KiB) Viewed 4017 times
nearest-sector-02-fields.png
nearest-sector-02-fields.png (90.78 KiB) Viewed 4017 times
nearest-sector-02.love
(1.77 KiB) Downloaded 104 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot], Google [Bot], Semrush [Bot] and 51 guests