CODEWITHSUNDEEP
javaalgorithmcollision-detection
Luke Vo
Luke Vo

Reputation: 20638

Bug when implement "check point inside triangle" algorithm

I'm following the 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: enter image description here

Cyan zone: The real triangle I give.

Pink zone: "Inside" the triangle

Blue Zone: "Outside" the triangle

EDIT:

This is my new code to calculate by vectors:

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. Thank you.

Upvotes: 6

Views: 450

Answers (2)

fmsf
fmsf

Reputation: 37137

I normally do the math like this, using barycentric coordinates: (considering 4 points where p1,p2,p3 are the triangle and p4 is the point you want to check: consider (p1,p3) as the 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 that we have the barycentric coordinates calculated, the verification is simple, should P4 lie inside the triangle (P1,P2,P3)$ then u and v must both be positive and summed up together they must be smaller than one:

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

This is the article where I learned how to do it when I was doing my thesis: http://www.blackpawn.com/texts/pointinpoly/default.html (you'll find similarities with the variable names :p)

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726469

There is a "bug" in the article's description of what needs to be done:

Calculate the perpDotProduct/crossproduct of all three points V1, V2, V3 with the testpoint P

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

As explained in the article, the algorithm returns true if all three points are visible at the same "angular direction" from the origin (the upper-left corner of your picture). Your picture shows it precisely, too: vectors (0, p) for all pink points need to turn clockwise to reach the triangle if they are above the blue zone; if they are below the blue zone, the vectors would need to move counterclockwise.

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

Upvotes: 1

Related Questions