Point in triangle

Show off your games, demos and other (playable) creations.
Post Reply
User avatar
darkfrei
Party member
Posts: 325
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 2361 times
point-in-triangle.love
(727 Bytes) Downloaded 87 times
User avatar
ivan
Party member
Posts: 1732
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: 325
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 2307 times
point-in-triangle-02.love
(946 Bytes) Downloaded 81 times
User avatar
ivan
Party member
Posts: 1732
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.
Post Reply

Who is online

Users browsing this forum: No registered users and 6 guests