Point in triangle

[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

[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

[darkfrei]

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

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.

[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.

[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]

[darkfrei]

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