An error occurred while implementing the "control point inside a triangle" algorithm

Question

I follow Algorithm 1 in this article to check if a point is inside a triangle. This is my code:

//========================================================================================================================// // Methods //========================================================================================================================// private float getPerpDotProduct(final PointF p1, final PointF p2) { return p1.x * p2.y - p1.y * p2.x; } private boolean isInside(final PointF pPoint) { final float c1 = this.getPerpDotProduct(this.mA, pPoint); final float c2 = this.getPerpDotProduct(this.mB, pPoint); final float c3 = this.getPerpDotProduct(this.mC, pPoint); return ((c1 >= 0 && c2 >= 0 & c3 >= 0) || (c1 <= 0 && c2 <= 0 && c3 <= 0)); } 

And this is my test:

Blue zone: the real triangle that I give.

Pink Zone: Inside the Triangle

Blue Zone: Outside Triangle

EDIT:

This is my new vector calculation code:

 private PointF getVector(final PointF pPoint1, final PointF pPoint2) { return new PointF(pPoint2.x - pPoint1.x, pPoint2.y - pPoint1.y); } private float getPerpDotProduct(final PointF p1, final PointF p2) { return p1.x * p2.y - p1.y * p2.x; } private boolean isInside(final PointF pPoint) { final float c1 = this.getPerpDotProduct(getVector(this.mA, this.mB), getVector(this.mA, pPoint)); final float c2 = this.getPerpDotProduct(getVector(this.mB, this.mC), getVector(this.mB, pPoint)); final float c3 = this.getPerpDotProduct(getVector(this.mC, this.mA), getVector(this.mC, pPoint)); return ((c1 > 0 && c2 > 0 & c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)); } 

Please clarify my code. Thanks.

Answer 1

There is an “error” in the description of the article:

Compute perpDotProduct / cross-play of all three points V1, V2, V3 with breakpoint P

should be "Calculate perpDotProduct / crossproduct of all three vectors with vectors to breakpoint P".

As explained in the article, the algorithm returns true if all three points are visible in the same "angular direction" from the origin (in the upper left corner of your image). Your photo shows this accurately: the vectors (0, p) for all the pink dots must be rotated clockwise to reach the triangle if they are above the blue zone; if they are below the blue zone, the vectors will have to move counterclockwise.

To fix the algorithm, you need to calculate the cross products of the vectors {(V1-V2), (V1-P)} , {(V2-V3), (V2-P)} and {(V3-V1), (V3-P)} . Take a look at this article for pseudocode.

Answer 2

I usually do math like this using barycentric coordinates: (given 4 points where p1, p2, p3 is a triangle and p4 is the point you want to check: consider (p1, p3) as a vector p1 → p3

 dot00 = (p1,p3).(p1,p3) dot01 = (p1,p3).(p1,p2) dot02 = (p1,p3).(p1,p4) dot11 = (p1,p2).(p1,p2) dot12 = (p1,p2).(p1,p4) inverseDenominator = (1 / (dot00*dot11 - dot01*dot01) u = (dot11 * dot02 - dot01*dot12) * inverseDenominator v = (dot00 * dot12 - dot01*dot02) * inverseDenominator 

Now, when we calculate the barycentric coordinates, the check is simple, if P4 lies inside the triangle (P1, P2, P3) $, then u and v must be positive and sum together, they must be less than one:

 u >= 0 && v >= 0 && u + v < 1 

This is an article in which I learned how to do this when I was doing my dissertation: http://www.blackpawn.com/texts/pointinpoly/default.html (you will find similarities with variable names: p)