Anyone got any reference or code for doing a point withina traingle check in 2D? I figure you can do it by checking which side of each line the point is on… but can’t quite get my head round it.
Cheers,
Kev
You can make a Polygon out of your Triangle and use the contains method.:
public boolean isInsideTriangle(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
Polygon p=new Polygon(new int[]{x1,x2,x3},new int[]{y1,y2,y3},3);
if(p.contains(x4,y4)) return true;
return false;
}
Or you can check check if the area of ABM+ACM+BCM=ABC(M is the point you check).If the point is inside the triangle they will be equal else they won’t.The area of a triangle is (Heron’s Formula) sqrt(p*(p-a)(p-b)(p-c)) where a,b,c are the lengths of BC,AC,AB and p is the semiperimeter((a+b+c)/2).
But I doubt the second method will run too fast. I don’t know how fast the first one runs…
Hope this helps. 
Thanks for the suggestions, I’m trying to avoid AWT/Java2D (and associated geom classes) where possible though. The second one might just be quick enough in this case though
Kev
If you have a guaranteed winding you could use cross products. Given a point p and a triangle a,b,c that is wound clockwise ab x ap, bc x bp and ca x cp all have to be greater or equal to zero in order for the point to lie inside the triangle.
Ye, with winding and crossproduct it should be pretty fast. It’s that SAT (separate axis theorem) thing. In most cases there won’t be a collision and you can return out of it after only 1 or 2 checks.
In addition, you can change it so that you don’t really need to worry about the vertices being in any particular order. Just check that the cross products are all negative or all positive. If one has a different sign than the others, the point is outside the triangle.
But then you always need to do all 3 checks and another one at the end. I would rather check the winding in the ctor with something like (x2-x1)(y3-y1) > (x3-x1)(y2-y1).
Not necessarily, you can stop early if the first two cross products have different signs.
I guess the best way to go depends on the context: If the triangles are long-lived, then the one-time cost of determining the winding order will be amortised and you can enjoy the benefits of a quick rejection with one less cross-product. If, OTOH, the triangle vertices are transient the potential savings may not justify the cost of determining winding order.
It’ll also depend on the likelihood of the point being inside the triangle. Both methods take three cross products for a positive result, and so the savings of a quick rejection with one less cross product become less significant as the probability of the point being inside the triangle increases.
Maybe I’m analysing this too much. It’s probably a case of six of one and half a dozen of the other.
Thanks all!
In this case it’s just mouse over sections (polygons broken into triangles) for a map. So correct winding will be the order of the day I think.
Thanks again,
Kev
Another way of doing it, and I think this works, but no idea how efficient it is
create 3 new vectors that connect each of the triangles points to the point you are trying to check. Get the angles between each of the lines. If the 3 angles add up to 360, then the point is inside, if it’s less than 360, the point is outside
Draw pictures, it’s how I came up with it
Endolf
No winding-order required:
Vec3 a, b, c, p;
boolean sideA = ((b.z-a.z)*(p.x-a.x)-(b.x-a.x)*(p.z-a.z)) > 0.0f;
boolean sideB = ((c.z-b.z)*(p.x-b.x)-(c.x-b.x)*(p.z-b.z)) > 0.0f;
if (sideA != sideB) return false;
boolean sideC = ((a.z-c.z)*(p.x-c.x)-(a.x-c.x)*(p.z-c.z)) > 0.0f;
return (sideA == sideC);
The comp.graphics.algorithms faq has one for this, although it’s for general polygons. It’s subject 2.03
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}