Point in Traingle Colission - Goriar/Ai-Project GitHub Wiki
Same Side Technique
A common way to check if a point is in a triangle is to find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi then the point is inside the triangle, otherwise it is not. It works, but it is very slow. This text explains a faster and much easier method.
Okay, A B C forms a triangle and all the points inside it are yellow. Lines AB, BC, and CA each split space in half and one of those halves is entirely outside the triangle. This is what we'll take advantage of.
For a point to be inside the traingle A B C it must be below AB and left of BC and right of AC. If any one of these tests fails we can return early.
But, how do we tell if a point is on the correct side of a line? I'm glad you asked.
If you take the cross product of [B-A] and [p-A], you'll get a vector pointing out of the screen. On the other hand, if you take the cross product of [B-A] and [p'-A] you'll get a vector pointing into the screen. Ah ha! In fact if you cross [B-A] with the vector from A to any point above the line AB, the resulting vector points out of the screen while using any point below AB yields a vector pointing into the screen. So all we need to do to distinguish which side of a line a point lies on is take a cross product.
The only question remaining is: how do we know what direction the cross product should point in? Because the triangle can be oriented in any way in 3d-space, there isn't some set value we can compare with. Instead what we need is a reference point - a point that we know is on a certain side of the line. For our triangle, this is just the third point C.
So, any point p where [B-A] cross [p-A] does not point in the same direction as [B-A] cross [C-A] isn't inside the triangle. If the cross products do point in the same direction, then we need to test p with the other lines as well. If the point was on the same side of AB as C and is also on the same side of BC as A and on the same side of CA as B, then it is in the triangle.
Implementing this is a breeze. We'll make a function that tells us if two points are on the same side of a line and have the actual point-in-triangle function call this for each edge.
function SameSide(p1,p2, a,b) cp1 = CrossProduct(b-a, p1-a) cp2 = CrossProduct(b-a, p2-a) if DotProduct(cp1, cp2) >= 0 then return true else return false
function PointInTriangle(p, a,b,c) if SameSide(p,a, b,c) and SameSide(p,b, a,c) and SameSide(p,c, a,b) then return true else return false It's simple, effective and has no square roots, arc cosines, or strange projection axis determination nastiness.