Point in triangle

Show off your games, demos and other (playable) creations.
Post Reply
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Point in triangle

Post by darkfrei »

Hi All!

I've made a small program how to get the information if the point is in the triangle.

The main function:

Code: Select all

function is_point_in_triangle(p, t)
	local a = {
		 t[2].x*t[3].y,
		-t[2].y*t[3].x,
		 t[1].x*( t[2].y-t[3].y),
		 t[1].y*(-t[2].x+t[3].x)
	}
	local b = {
		 t[1].x*t[2].y,
		-t[1].y*t[2].x,
		p.x*(t[1].y-t[2].y),
		p.y*(t[2].x-t[1].x)
	}
	local c = {
		 t[1].y*t[3].x,
		-t[1].x*t[3].y,
		 p.x*(t[3].y-t[1].y),
		 p.y*(t[1].x-t[3].x)
	}
	local sa = a[1]+a[2]+a[3]+a[4]
	local sb = b[1]+b[2]+b[3]+b[4]
	local sc = c[1]+c[2]+c[3]+c[4]
	local sign = (sa>=0) and 1 or -1
	if (sign*sb>0) and (sign*sc>0) and (sb+sc)<(sign*sa) then
		return true
	else
		return false
	end
end
Attachments
2021-04-08T15_29_52-point-in-triangle-lua.png
2021-04-08T15_29_52-point-in-triangle-lua.png (8.29 KiB) Viewed 10614 times
point-in-triangle.love
(727 Bytes) Downloaded 186 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Point in triangle

Post by ivan »

Hello, I haven't tested your code, but I think there are a lot simpler and more efficient ways to test if a point is inside a triangle:
https://2dengine.com/?p=intersections#P ... e_triangle
The issues with your code are:
1. The intermediate a,b,c tables. That's very inefficient
2. No "early bailout". What I mean is that you can avoid a number of calculations by returning ASAP:

Code: Select all

if sign*sb<0 then return false end
3. All and all you are doing extra calculations compared to the link above
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Point in triangle

Post by darkfrei »

ivan wrote: Thu Apr 08, 2021 5:12 pm Hello, I haven't tested your code, but I think there are a lot simpler and more efficient ways to test if a point is inside a triangle:
https://2dengine.com/?p=intersections#P ... e_triangle
Christer Ericson wrote:

Code: Select all

function pointInTriangle(px, py, x1, y1, x2, y2, x3, y3)
  local ax, ay = x1 - px, y1 - py
  local bx, by = x2 - px, y2 - py
  local cx, cy = x3 - px, y3 - py
  local sab = ax*by - ay*bx < 0
  if sab ~= (bx*cy - by*cx < 0) then
    return false
  end
  return sab == (cx*ay - cy*ax < 0)
end
It's a kind of magic!

but I like it like

Code: Select all

function pointInTriangle(p, t)
  local px, py, x1, y1, x2, y2, x3, y3 = p.x, p.y, t[1].x, t[1].y, t[2].x, t[2].y, t[3].x, t[3].y
  local ax, ay = x1 - px, y1 - py
  local bx, by = x2 - px, y2 - py
  local cx, cy = x3 - px, y3 - py
  local sab = ax*by - ay*bx < 0
  if sab ~= (bx*cy - by*cx < 0) then
    return false
  end
  return sab == (cx*ay - cy*ax < 0)
end
UPD:
Tested: About 4 times faster: 0.023362800013274 vs 0.090537000040058 for 1000000 iterations.
Attachments
2021-04-08T23_07_39-Untitled.png
2021-04-08T23_07_39-Untitled.png (12.72 KiB) Viewed 10560 times
point-in-triangle-02.love
(946 Bytes) Downloaded 181 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Point in triangle

Post by ivan »

If I remember correctly from Ericson's book, it may be possible to do even further performance optimizations - but you have to know the triangle's winding/orientation in advance.
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Point in triangle

Post by togFox »

Did a google search on "lua code for determining if point is inside triangle" and this thread came up. :)

Just checking if the OP code is still considered the best? Has there been any improvements in the last two years? I'm happy to use as-is but just checking. :)

[I can't access 2dengine.com from my work internet]
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Point in triangle

Post by darkfrei »

togFox wrote: Mon Oct 09, 2023 11:39 pm Did a google search on "lua code for determining if point is inside triangle" and this thread came up. :)

Just checking if the OP code is still considered the best? Has there been any improvements in the last two years? I'm happy to use as-is but just checking. :)

[I can't access 2dengine.com from my work internet]
Not sure if it faster, but it's shorter!

Code: Select all

function love.load()
	v1 = {x = 200, y = 200}
	v2 = {x = 400, y = 250}
	v3 = {x = 250, y = 500}
	inside = false
end

local function isPointInTriangle(point, v1, v2, v3)
	local function calculateTriangleArea(v1, v2, v3)
		return 0.5 * math.abs((v1.x - v3.x) * (v2.y - v1.y) - (v1.x - v2.x) * (v3.y - v1.y))
	end
	local totalArea = calculateTriangleArea(v1, v2, v3)
	local area1 = calculateTriangleArea(point, v2, v3)
	local area2 = calculateTriangleArea(v1, point, v3)
	local area3 = calculateTriangleArea(v1, v2, point)
	return math.abs(totalArea - (area1 + area2 + area3)) < 1e-6
end

function love.draw()
	if inside then
		love.graphics.setColor(0,1,1)
	else
		love.graphics.setColor(1,0,0)
	end
	love.graphics.line(v1.x, v1.y, v2.x, v2.y)
	love.graphics.line(v2.x, v2.y, v3.x, v3.y)
	love.graphics.line(v3.x, v3.y, v1.x, v1.y)
	love.graphics.circle ('line', v3.x, v3.y, 5)
end

function love.mousemoved(x, y)
	inside = isPointInTriangle({x=x, y=y}, v1, v2, v3)
end

function love.mousepressed(x, y)
	v2, v3 = v3, v2
	inside = isPointInTriangle({x=x, y=y}, v1, v2, v3)
end
or just check the polygon (triangle is a polygon too):

Code: Select all

local function pointInPolygon (px, py, ...)
	local vertices = {...}
	local inside = false
	local j = #vertices-1
	local x2, y2 = vertices[j], vertices[j+1]

	for i = 1, #vertices-1, 2 do
		local x1, y1 = vertices[i], vertices[i+1]
		if (y1 < py and y2 >= py or y2 < py and y1 >= py)
		and (x1 <= px or x2 <= px)
		and (x1 + (py - y1) / (y2-y1)*(x2-x1) < px) then
			inside = not inside
		end
		x2, y2 = x1, y1
	end
	return inside
end

function love.mousemoved(x, y)
	inside = isPointInTriangle({x=x, y=y}, v1, v2, v3)

	local inside2 = pointInPolygon (x, y, v1.x, v1.y, v2.x, v2.y, v3.x, v3.y)
	love.window.setTitle (tostring (inside2))
end
Attachments
point-in-triangle-03.love
(537 Bytes) Downloaded 52 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
Post Reply

Who is online

Users browsing this forum: No registered users and 17 guests