[algorithm] How to determine if a point is in a 2D triangle?


Answers

Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.

s,t and 1 - s - t are called the barycentric coordinates of the point p.

Question

Is there an easy way to determine if a point is inside a triangle? It's 2D, not 3D.




Here is an efficient Python implementation:

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

and an example output:




I needed point in triangle check in "controlable environment" when you're absolutely sure that triangles will be clockwise. So, I took Perro Azul's jsfiddle and modified it as suggested by coproc for such cases; also removed redundant 0.5 and 2 multiplications because they're just cancel each other.

http://jsfiddle.net/dog_funtom/H7D7g/

Here is equivalent C# code for Unity:

public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2)
{
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0)
        return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}



bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

It can not be more efficient than this! Each side of a triangle can have independent position and orientation, hence three calculations: l1, l2 and l3 are definitely needed involving 2 multiplications each. Once l1, l2 and l3 are known, result is just a few basic comparisons and boolean operations away.




There are pesky edge conditions where a point is exactly on the common edge of two adjacent triangles. The point cannot be in both, or neither of the triangles. You need an arbitrary but consistent way of assigning the point. For example, draw a horizontal line through the point. If the line intersects with the other side of the triangle on the right, the point is treated as though it is inside the triangle. If the intersection is on the left, the point is outside.

If the line on which the point lies is horizontal, use above/below.

If the point is on the common vertex of multiple triangles, use the triangle with whose center the point forms the smallest angle.

More fun: three points can be in a straight line (zero degrees), for example (0,0) - (0,10) - (0,5). In a triangulating algorithm, the "ear" (0,10) must be lopped off, the "triangle" generated being the degenerate case of a straight line.




bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

almost perfect Cartesian coordinates converted from barycentric are exported within *v (x) and *w (y) doubles. Both export doubles should have a * char before in every case, likely: *v and *w Code can be used for the other triangle of a quadrangle too. Hereby signed wrote only triangle abc from the clockwise abcd quad.

A---B
|..\\.o|  
|....\\.| 
D---C 

the o point is inside ABC triangle for testing with with second triangle call this function CDA direction, and results should be correct after *v=1-*v; and *w=1-*w; for the quadrangle




A simple way 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.

Two good sites that explain alternatives are:

blackpawn and wolfram




I wrote this code before a final attempt with Google and finding this page, so I thought I'd share it. It is basically an optimized version of Kisielewicz answer. I looked into the Barycentric method also but judging from the Wikipedia article I have a hard time seeing how it is more efficient (I'm guessing there is some deeper equivalence). Anyway, this algorithm has the advantage of not using division; a potential problem is the behavior of the edge detection depending on orientation.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

In words, the idea is this: Is the point s to the left of or to the right of both the lines AB and AC? If true, it can't be inside. If false, it is at least inside the "cones" that satisfy the condition. Now since we know that a point inside a trigon (triangle) must be to the same side of AB as BC (and also CA), we check if they differ. If they do, s can't possibly be inside, otherwise s must be inside.

Some keywords in the calculations are line half-planes and the determinant (2x2 cross product). Perhaps a more pedagogical way is probably to think of it as a point being inside iff it's to the same side (left or right) to each of the lines AB, BC and CA. The above way seemed a better fit for some optimization however.







By using the analytic solution to the barycentric coordinates (pointed out by Andreas Brinck) and:

  • not distributing the multiplication over the parenthesized terms
  • avoiding computing several times the same terms by storing them
  • reducing comparisons (as pointed out by coproc and Thomas Eding)

one can minimize the number of "costy" operations:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

(code can be pasted in Perro Azul jsfiddle)

Leading to:

  • variable "recalls": 30
  • variable storage: 7
  • additions: 4
  • substractions: 8
  • multiplications: 6
  • divisions: none
  • comparisons: 4

This compares quite well with Kornel Kisielewicz solution (25 recalls, 1 storage, 15 substractions, 6 multiplications, 5 comparisons), and might be even better if clockwise/counter-clockwise detection is needed (which takes 6 recalls, 1 addition, 2 substractions, 2 multiplications and 1 comparison in itself, using the analytic solution determinant, as pointed out by rhgb).




If you know the co-ordinates of the three vertices and the co-ordinates of the specific point, then you can get the area of the complete triangle. Afterwards, calculate the area of the three triangle segments (one point being the point given and the other two being any two vertices of the triangle). Thus, you will get the area of the three triangle segments. If the sum of these areas are equal to the total area (that you got previously), then, the point should be inside the triangle. Otherwise, the point is not inside the triangle. This should work. If there are any issues, let me know. Thank you.




Related