Looking for a better way of doing point in triangle detection

[Tornation]

From experimenting I wrote a couple methods to help detect whether a point was in a set of three vertices. It works a little but not really. It doesn't seem to give false-positives but it does often won't recognize while the point is in the triangle (kinda random). I think what I did would work in theory but due to the behavior of floating point values it's horribly inconsistent.

 

My question is whether anyone knows or can point me to an easier more consistent way of accomplishing this.

 

Spoiler

#pragma once

#include <glm/glm.hpp>
#include <cmath>

float TriangleArea(glm::vec2 & v1, glm::vec2 & v2, glm::vec2 & v3) {
	return abs((((v1.x - v3.x) * (v2.y - v3.y)) - ((v2.x - v3.x) * (v1.y - v3.y))) / 2.0f);
}

bool PointInTriangle(glm::vec2 & pt, glm::vec2 & v1, glm::vec2 & v2, glm::vec2 & v3) {
	return 
		TriangleArea(pt, v1, v2) + 
		TriangleArea(pt, v1, v3) + 
		TriangleArea(pt, v2, v3) ==
		TriangleArea(v1, v2, v3);
}

 

 

[trag1c]

AABB might be adaptable to your situation.

[fizzlesticks]

For a counter clockwise triangle a, b, c and point p

bool pointInTriangle(vec p, vec a, vec b, vec c)
{
	//transform so p is at origin
	a -= p;
	b -= p;
	c -= p;

	//X = cross product
	vec u = b X c;
	vec v = c X a;

	//* = dot product
	if(u * v < 0)
    {
   		return false;
    }
    vec w = a X b;
   	if(u * w < 0)
    {
		return false;
	}
	return true;
}

untested but something like that.

edit: just realized you're doing 2d, it would still work if you gave everything a z of 0 but there would probably be a more efficient solution.

[Nineshadow]

Barycentric Tehnique

It's based on a simple observation :

Consider a triangle ABC and a point P. If you take the cross product of AB and AP, you will get a vector pointing outside of the triangle if P is outside the triangle and inside the triangle vice-versa. This way we can easily figure out which side of a line a points resides in. But how should we do it for a triangle? The triangle can be oriented in any way, there isn't some value to compare with, so we take C as a reference point. Thus, for a point P, if the vector AB cross AP doesn't point in the same direction as AB cross AC, then the point P can't be inside the triangle. Otherwise, we'll also need to test the other edges. So, if P is on the same side of AB as C, on the same side of BC as A and the same side of AC as B, then P is inside a triangle.

 

We'll say the triangle can define a plane in space and we'll pick a point as an origin of that plane. The others will be relative to it. So let's pick A. Let's pick two edges of the triangle which touch A. We can get to any point of the plane by starting at A at going along AB, then in the direction of AC, etc., etc.

We'll use a barycentric coordinate system to describe a point on our plane. A barycentric coordinate system for a triangle looks something like this :
Considering a triangle with the verticies A,B,C, for every point P inside the triangle there is an unique sequence of numbers x,y>=0 and <=1 such that :

P=A + x*B + y*C

A point P is not inside the triangle if x or y <0 or x or y > 1.

P,A,B and C are constants so we only need to know x and y. We can easily get a system of 2 equations by multiplying (as in dot product) both sides once by B and then by C. Solving this system of 2 equations is trivial. You could also rewrite the whole thing under a matrix form.

 

This is basically what @fizzlesticks used in his example.