Point in triangle

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

Point in triangle

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 (8.29 KiB) Viewed 2361 times
point-in-triangle.love
ivan
Party member
Posts: 1732
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Point in triangle

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
Party member
Posts: 325
Joined: Sat Feb 08, 2020 11:09 pm

Re: Point in triangle

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 (12.72 KiB) Viewed 2307 times
point-in-triangle-02.love