How to determine if a point is in a 2D triangle

Question

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

User · Answer

What I do is precalculate the three face normals,

in 3D by cross product of side vector and the face normal vector.
in 2D by simply swapping components and negating one,

then inside/outside for any one side is when a dot product of the side normal and the vertex to point vector, change sign. Repeat for other two (or more) sides.

Benefits:

a lot is precalculated so great for multiple point testing on same triangle.
early rejection of common case of more outside than inside points. (also if point distribution weighted to one side, can test that side first.)

User · Answer

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  gt  -0 0  amp  amp   v  lt  1 0000001  amp  amp   w  gt  -0 0  amp  amp   w  lt   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

User · Answer

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 gt 0  amp  amp  l2 gt 0   amp  amp  l3 gt 0      l1 lt 0  amp  amp  l2 lt 0  amp  amp  l3 lt 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

User · Answer

One of the easiest ways to check if the area formed by the vertices of triangle   x1 y1   x2 y2   x3 y3  is positive or not   Area can by calculated by the formula      1 2  x1 y2   y3    x2 y3   y1    x3 y1   y2     or python code can be written as   def triangleornot p1 p2 p3       return  1  2   p1 0  p2 1    p3 1     p2 0   p3 1    p1 1     p3 0   p1 0    p2 0

User · Answer

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    x000D   x000D  var ctx      canvas   0  getContext  2d    x000D  var W   500  x000D  var H   500  x000D   x000D  var point     x000D      x  W   2  x000D      y  H   2 x000D     x000D  var triangle   randomTriangle    x000D   x000D     canvas   click function  evt    x000D      point x   evt pageX -   this  offset   left  x000D      point y   evt pageY -   this  offset   top  x000D      test    x000D      x000D   x000D     canvas   dblclick function  evt    x000D      triangle   randomTriangle    x000D      test    x000D      x000D   x000D  test    x000D   x000D  function test     x000D      var result   ptInTriangle point  triangle a  triangle b  triangle c   x000D   x000D      var info    point        point x         point y      n   x000D      info     triangle a        triangle a x         triangle a y      n   x000D      info     triangle b        triangle b x         triangle b y      n   x000D      info     triangle c        triangle c x         triangle c y      n   x000D      info     result        result    true     false    x000D   x000D          result   text info   x000D      render    x000D    x000D   x000D  function ptInTriangle p  p0  p1  p2    x000D      var s    p0 y   p2 x - p0 x   p2 y    p2 y - p0 y    p x    p0 x - p2 x    p y   x000D      var t    p0 x   p1 y - p0 y   p1 x    p0 y - p1 y    p x    p1 x - p0 x    p y   x000D   x000D      if  s  lt   0    t  lt   0  return false  x000D   x000D      var A    -p1 y   p2 x   p0 y    -p1 x   p2 x    p0 x    p1 y - p2 y    p1 x   p2 y   x000D   x000D      return  s   t   lt  A  x000D    x000D   x000D  function checkClockwise p0  p1  p2    x000D      var A    -p1 y   p2 x   p0 y    -p1 x   p2 x    p0 x    p1 y - p2 y    p1 x   p2 y   x000D      return A  gt  0  x000D    x000D   x000D  function render     x000D      ctx fillStyle     CCC   x000D      ctx fillRect 0  0  500  500   x000D      drawTriangle triangle a  triangle b  triangle c   x000D      drawPoint point   x000D    x000D   x000D  function drawTriangle p0  p1  p2    x000D      ctx fillStyle     999   x000D      ctx beginPath    x000D      ctx moveTo p0 x  p0 y   x000D      ctx lineTo p1 x  p1 y   x000D      ctx lineTo p2 x  p2 y   x000D      ctx closePath    x000D      ctx fill    x000D      ctx fillStyle     000   x000D      ctx font    12px monospace   x000D      ctx fillText  1   p0 x  p0 y   x000D      ctx fillText  2   p1 x  p1 y   x000D      ctx fillText  3   p2 x  p2 y   x000D    x000D   x000D  function drawPoint p    x000D      ctx fillStyle     F00   x000D      ctx beginPath    x000D      ctx arc p x  p y  5  0  2   Math PI   x000D      ctx fill    x000D    x000D   x000D  function rand min  max    x000D      return Math floor Math random      max - min   1     min  x000D    x000D   x000D  function randomTriangle     x000D      while  true    x000D          var result     x000D              a    x000D                  x  rand 0  W   x000D                  y  rand 0  H  x000D                 x000D              b    x000D                  x  rand 0  W   x000D                  y  rand 0  H  x000D                 x000D              c    x000D                  x  rand 0  W   x000D                  y  rand 0  H  x000D                x000D             x000D          if  checkClockwise result a  result b  result c   return result  x000D        x000D    x000D   lt script src  https   cdnjs cloudflare com ajax libs jquery 1 9 1 jquery min js  gt  lt  script gt  x000D   lt pre gt Click  place the point  x000D  Double click  random triangle  lt  pre gt  x000D   x000D   lt pre id  result  gt  lt  pre gt  x000D   x000D   lt canvas width  500  height  500  gt  lt  canvas gt  x000D   x000D   x000D    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  lt   0    t  lt   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   lt  A

User · Answer

Java version of barycentric method   class Triangle       Triangle double x1  double y1  double x2  double y2  double x3              double y3            this x3   x3          this y3   y3          y23   y2 - y3          x32   x3 - x2          y31   y3 - y1          x13   x1 - x3          det   y23   x13 - x32   y31          minD   Math min det  0           maxD   Math max det  0              boolean contains double x  double y            double dx   x - x3          double dy   y - y3          double a   y23   dx   x32   dy          if  a  lt  minD    a  gt  maxD              return false          double b   y31   dx   x13   dy          if  b  lt  minD    b  gt  maxD              return false          double c   det - a - b          if  c  lt  minD    c  gt  maxD              return false          return true             private final double x3  y3      private final double y23  x32  y31  x13      private final double det  minD  maxD      The above code will work accurately with integers  assuming no overflows   It will also work with clockwise and anticlockwise triangles   It will not work with collinear triangles  but you can check for that by testing det  0    The barycentric version is fastest if you are going to test different points with the same triangle   The barycentric version is not symmetric in the 3 triangle points  so it is likely to be less consistent than Kornel Kisielewicz s edge half-plane version  because of floating point rounding errors   Credit  I made the above code from Wikipedia s article on barycentric coordinates

User · Answer

I agree with Andreas Brinck  barycentric coordinates are very convenient for this task  Note that there is no need to solve an equation system every time  just evaluate the analytical solution  Using Andreas  notation  the solution is   s   1  2 Area   p0y p2x - p0x p2y    p2y - p0y  px    p0x - p2x  py   t   1  2 Area   p0x p1y - p0y p1x    p0y - p1y  px    p1x - p0x  py     where Area is the  signed  area of the triangle   Area   0 5   -p1y p2x   p0y  -p1x   p2x    p0x  p1y - p2y    p1x p2y     Just evaluate s  t and 1-s-t  The point p is inside the triangle if and only if they are all positive   EDIT  Note that the above expression for the area assumes that the triangle node numbering is counter-clockwise  If the numbering is clockwise  this expression will return a negative area  but with correct magnitude   The test itself  s gt 0  amp  amp  t gt 0  amp  amp  1-s-t gt 0  doesn t depend on the direction of the numbering  however  since the expressions above that are multiplied by 1  2 Area  also change sign if the triangle node orientation changes   EDIT 2  For an even better computational efficiency  see coproc s comment below  which  makes the point that if the orientation of the triangle nodes  clockwise or counter-clockwise  is known beforehand  the division by 2 Area in the expressions for s and t can be avoided   See also Perro Azul s jsfiddle-code in the comments under Andreas Brinck s answer

User · Answer

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

User · Answer

The easiest way and it works with all types of triangles is simply determine the angles of the P point A  B   C points angles  If any of the angles are bigger than 180 0 degree then it is outside  if 180 0 then it is on the circumference and if acos cheating on you and less than 180 0 then it is inside Take a look for understanding http   math-physics-psychology blogspot hu 2015 01 earlish-determination-that-point-is html

User · Answer

C  version of the barycentric method posted by andreasdr and Perro Azul  I added a check to abandon the area calculation when s and t have opposite signs  since potentially avoiding one-third of the multiplication cost seems justified  Also  even though the math here is firmly-established by now  I ran a thorough unit-test harness on this specific code for good measure anyway  public static bool PointInTriangle Point p  Point p0  Point p1  Point 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  lt  0      t  lt  0           return false       var A   -p1 Y   p2 X   p0 Y    p2 X - p1 X    p0 X    p1 Y - p2 Y    p1 X   p2 Y       return A  lt  0                s  lt   0  amp  amp  s   t  gt   A                 s  gt   0  amp  amp  s   t  lt   A

User · Answer

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  costly  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 lt 0  return s lt  0  amp  amp  t lt  0  amp  amp  s t gt  D      return s gt  0  amp  amp  t gt  0  amp  amp  s t lt  D      Code can be pasted in Perro Azul jsfiddle or try it by clicking  Run code snippet  below   x000D   x000D  var ctx      canvas   0  getContext  2d    x000D  var W   500  x000D  var H   500  x000D   x000D  var point     x  W   2  y  H   2    x000D  var triangle   randomTriangle    x000D   x000D     canvas   click function evt    x000D      point x   evt pageX -   this  offset   left  x000D      point y   evt pageY -   this  offset   top  x000D      test    x000D      x000D   x000D     canvas   dblclick function evt    x000D      triangle   randomTriangle    x000D      test    x000D      x000D   x000D  test    x000D   x000D  function test     x000D      var result   ptInTriangle point  triangle a  triangle b  triangle c   x000D       x000D      var info    point        point x         point y      n   x000D      info     triangle a        triangle a x         triangle a y      n   x000D      info     triangle b        triangle b x         triangle b y      n   x000D      info     triangle c        triangle c x         triangle c y      n   x000D      info     result        result    true     false    x000D   x000D          result   text info   x000D      render    x000D    x000D   x000D  function ptInTriangle p  p0  p1  p2    x000D      var A   1 2    -p1 y   p2 x   p0 y    -p1 x   p2 x    p0 x    p1 y - p2 y    p1 x   p2 y   x000D      var sign   A  lt  0   -1   1  x000D      var s    p0 y   p2 x - p0 x   p2 y    p2 y - p0 y    p x    p0 x - p2 x    p y    sign  x000D      var t    p0 x   p1 y - p0 y   p1 x    p0 y - p1 y    p x    p1 x - p0 x    p y    sign  x000D       x000D      return s  gt  0  amp  amp  t  gt  0  amp  amp   s   t   lt  2   A   sign  x000D    x000D   x000D  function render     x000D      ctx fillStyle     CCC   x000D      ctx fillRect 0  0  500  500   x000D      drawTriangle triangle a  triangle b  triangle c   x000D      drawPoint point   x000D    x000D   x000D  function drawTriangle p0  p1  p2    x000D      ctx fillStyle     999   x000D      ctx beginPath    x000D      ctx moveTo p0 x  p0 y   x000D      ctx lineTo p1 x  p1 y   x000D      ctx lineTo p2 x  p2 y   x000D      ctx closePath    x000D      ctx fill    x000D      ctx fillStyle     000   x000D      ctx font    12px monospace   x000D      ctx fillText  1   p0 x  p0 y   x000D      ctx fillText  2   p1 x  p1 y   x000D      ctx fillText  3   p2 x  p2 y   x000D    x000D   x000D  function drawPoint p    x000D      ctx fillStyle     F00   x000D      ctx beginPath    x000D      ctx arc p x  p y  5  0  2   Math PI   x000D      ctx fill    x000D    x000D   x000D  function rand min  max    x000D   return Math floor Math random      max - min   1     min  x000D    x000D   x000D  function randomTriangle     x000D      return   x000D          a    x  rand 0  W   y  rand 0  H     x000D          b    x  rand 0  W   y  rand 0  H     x000D          c    x  rand 0  W   y  rand 0  H    x000D         x000D    x000D   lt script src  https   cdnjs cloudflare com ajax libs jquery 1 9 1 jquery min js  gt  lt  script gt  x000D   lt pre gt Click  place the point  x000D  Double click  random triangle  lt  pre gt  x000D   lt pre id  result  gt  lt  pre gt  x000D   lt canvas width  500  height  500  gt  lt  canvas gt  x000D   x000D   x000D    Leading to    variable  recalls   30 variable storage  7 additions  4 subtractions  8 multiplications  6 divisions  none comparisons  4   This compares quite well with Kornel Kisielewicz solution  25 recalls  1 storage  15 subtractions  6 multiplications  5 comparisons   and might be even better if clockwise counter-clockwise detection is needed  which takes 6 recalls  1 addition  2 subtractions  2 multiplications and 1 comparison in itself  using the analytic solution determinant  as pointed out by rhgb

User · Answer

If you are looking for speed  here is a procedure that might help you   Sort the triangle vertices on their ordinates  This takes at worst three comparisons  Let Y0  Y1  Y2 be the three sorted values  By drawing three horizontals through them you partition the plane into two half planes and two slabs  Let Y be the ordinate of the query point   if Y  lt  Y1     if Y  lt   Y0 - gt  the point lies in the upper half plane  outside the triangle  you are done     else Y  gt  Y0 - gt  the point lies in the upper slab else     if Y  gt   Y2 - gt  the point lies in the lower half plane  outside the triangle  you are done     else Y  lt  Y2 - gt  the point lies in the lower slab   Costs two more comparisons  As you see  quick rejection is achieved for points outside of the  bounding slab    Optionally  you can supply a test on the abscissas for quick rejection on the left and on the right  X  lt   X0  or X  gt   X2    This will implement a quick bounding box test at the same time  but you ll need to sort on the abscissas too   Eventually you will need to compute the sign of the given point with respect to the two sides of the triangle that delimit the relevant slab  upper or lower   The test has the form     X - Xi     Y - Yj   gt   X - Xi     Y - Yj        X - Xi     Y - Yk   gt   X - Xi     Y - Yk     The complete discussion of i  j  k combinations  there are six of them  based on the outcome of the sort  is out of the scope of this answer and  left as an exercise to the reader   for efficiency  they should be hard-coded   If you think that this solution is complex  observe that it mainly involves simple comparisons  some of which can be precomputed   plus 6 subtractions and 4 multiplies in case the bounding box test fails  The latter cost is hard to beat as in the worst case you cannot avoid comparing the test point against two sides  no method in other answers has a lower cost  some make it worse  like 15 subtractions and 6 multiplies  sometimes divisions    UPDATE  Faster with a shear transform  As explained just above  you can quickly locate the point inside one of the four horizontal bands delimited by the three vertex ordinates  using two comparisons   You can optionally perform one or two extra X tests to check insideness to the bounding box  dotted lines    Then consider the  shear  transform given by X   X - m Y  Y    Y  where m is the slope DX DY for the highest edge  This transform will make this side of the triangle vertical  And since you know on what side of the middle horizontal you are  it suffices to test the sign with respect to a single side of the triangle     Assuming you precomputed the slope m  as well as the X  for the sheared triangle vertices and the coefficients of the equations of the sides as X   m Y   p  you will need in the worst case   two ordinate comparisons for vertical classification  optionally one or two abscissa comparisons for bounding box rejection  computation of X    X - m Y  one or two comparisons with the abscissas of the sheared triangle  one sign test X  gt  lt  m  Y   p  against the relevant side of the sheared triangle

User · Answer

Other function in python  faster than Developer s method  for me at least  and inspired by C  dric Dufour solution     def ptInTriang p test  p0  p1  p2               dX   p test 0  - p0 0       dY   p test 1  - p0 1       dX20   p2 0  - p0 0       dY20   p2 1  - p0 1       dX10   p1 0  - p0 0       dY10   p1 1  - p0 1        s p    dY20 dX  -  dX20 dY       t p    dX10 dY  -  dY10 dX       D    dX10 dY20  -  dY10 dX20        if D  gt  0           return     s p  gt   0  and  t p  gt   0  and  s p   t p   lt   D         else           return     s p  lt   0  and  t p  lt   0  and  s p   t p   gt   D      You can test it with   X size   64 Y size   64 ax x   np arange X size  astype np float32  ax y   np arange Y size  astype np float32  coords np meshgrid ax x ax y  points unif    coords 0  reshape X size Y size   coords 1  reshape X size Y size    p test   np array  0   0   p0   np array  22   8    p1   np array  12   55    p2   np array  7   19    fig   plt figure dpi 300  for i in range 0 X size Y size       p test 0    points unif 0  i      p test 1    points unif 1  i      if ptInTriang p test  p0  p1  p2           plt plot p test 0   p test 1     g       else          plt plot p test 0   p test 1     r     It takes a lot to plot  but that grid is tested in 0 0195319652557 seconds against 0 0844349861145 seconds of Developer s code   Finally the code comment     Using barycentric coordintes  any point inside can be described as    X   p0 x   r   p1 x   s   p2 x   t   Y   p0 y   r   p1 y   s   p2 y   t   with    r   s   t   1  and 0  lt  r s t  lt  1   then  r   1 - s - t   and then    X   p0 x    1 - s - t    p1 x   s   p2 x   t   Y   p0 y    1 - s - t    p1 y   s   p2 y   t     X   p0 x    p1 x-p0 x    s    p2 x-p0 x    t   Y   p0 y    p1 y-p0 y    s    p2 y-p0 y    t     X - p0 x    p1 x-p0 x    s    p2 x-p0 x    t   Y - p0 y    p1 y-p0 y    s    p2 y-p0 y    t     we have to solve        X - p0 x       p1 x-p0 x     p2 x-p0 x       s       Y - p0 Y       p1 y-p0 y     p2 y-p0 y       t       --- gt  b   A x   --- gt  x   A -1   b        s       A -1      X - p0 x       t                 Y - p0 Y       A -1   1 D   adj A      The adjugate of A      adj A          p2 y-p0 y    - p2 x-p0 x                   - p1 y-p0 y     p1 x-p0 x       The determinant of A      D    p1 x-p0 x   p2 y-p0 y  -  p1 y-p0 y   p2 x-p0 x      Then      s p      p2 y-p0 y   X - p0 x  -  p2 x-p0 x   Y - p0 Y      t p      p1 x-p0 x   Y - p0 Y  -  p1 y-p0 y   X - p0 x        s   s p   D   t   t p   D     Recovering r      r   1 -  s p   t p  D     Since we only want to know if it is insidem not the barycentric coordinate      0  lt  1 -  s p   t p  D  lt  1   0  lt   s p   t p  D  lt  1   0  lt   s p   t p   lt  D     The condition is    if D  gt  0        s p  gt  0 and t p  gt  0 and  s p   t p   lt  D   else        s p  lt  0 and t p  lt  0 and  s p   t p   gt  D     s p     dY20 dX - dX20 dY     t p     dX10 dY - dY10 dX     D   dX10 dY20 - dY10 dX20

User · Answer

This is the simplest concept to determine if a point is inside or outside the triangle or on an arm of a triangle   Determination of a point is inside a triangle by determinants     The simplest working code    - - coding  utf-8 - -  import numpy as np  tri points     1 1   2 3   3 1    def pisinTri point tri points       Dx   Dy   point      A B C   tri points     Ax  Ay   A     Bx  By   B     Cx  Cy   C      M1   np array    Dx - Bx  Dy - By  0                        Ax - Bx  Ay - By  0                        1        1        1                            M2   np array    Dx - Ax  Dy - Ay  0                        Cx - Ax  Cy - Ay  0                        1        1        1                            M3   np array    Dx - Cx  Dy - Cy  0                        Bx - Cx  By - Cy  0                        1        1        1                            M1   np linalg det M1      M2   np linalg det M2      M3   np linalg det M3      print M1 M2 M3       if M1    0 or M2    0 or M3   0               print  Point    point   lies on the arms of Triangle       elif  M1  gt  0 and M2  gt  0 and M3  gt  0 or M1  lt  0 and M2  lt  0 and M3  lt  0                 if products is non 0 check if all of their sign is same             print  Point    point   lies inside the Triangle       else              print  Point    point   lies outside the Triangle    print  Vertices of Triangle    tri points  points     0 0   1 1   2 3   3 1   2 2   4 4   1 0   0 4   for c in points      pisinTri c tri points

User · Answer

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

User · Answer

Honestly it is as simple as Simon P Steven s answer however with that approach you don t have a solid control on whether you want the points on the edges of the triangle to be included or not   My approach is a little different but very basic  Consider the following triangle     In order to have the point in the triangle we have to satisfy 3 conditions   ACE angle  green  should be smaller than ACB angle  red  ECB angle  blue  should be smaller than ACB angle  red  Point E and Point C shoud have the same sign when their x and y values are applied to the equation of the  AB  line    In this method you have full control to include or exclude the point on the edges individually  So you may check if a point is in the triangle including only the  AC  edge for instance   So my solution in JavaScript would be as follows    x000D   x000D  function isInTriangle t p   x000D   x000D    function isInBorder a b c p   x000D      var m    a y - b y     a x - b x                          calculate the slope x000D      return Math sign p y - m p x   m a x - a y      Math sign c y - m c x   m a x - a y   x000D      x000D     x000D    function findAngle a b c                                    calculate the C angle from 3 points  x000D      var ca   Math hypot c x-a x  c y-a y                      ca edge length x000D          cb   Math hypot c x-b x  c y-b y                      cb edge length x000D          ab   Math hypot a x-b x  a y-b y                      ab edge length x000D      return Math acos  ca ca   cb cb - ab ab     2 ca cb       return the C angle x000D      x000D   x000D    var pas   t slice 1  x000D                map tp   gt  findAngle p tp t 0                    find the angle between  p t 0   with  t 1  t 0    amp   t 2  t 0   x000D         ta   findAngle t 1  t 2  t 0    x000D    return pas 0   lt  ta  amp  amp  pas 1   lt  ta  amp  amp  isInBorder t 1  t 2  t 0  p   x000D    x000D   x000D  var triangle     x 3  y 4   x 10  y 8   x 6  y 10    x000D        point1    x 3  y 9   x000D        point2    x 7  y 9   x000D   x000D  console log isInTriangle triangle point1    x000D  console log isInTriangle triangle point2    x000D   x000D   x000D

User · Answer

Here is a solution in python that is efficient  documented and contains three unittests  It s professional-grade quality and ready to be dropped into your project in the form of a module as is     import unittest                                                                                  def point in triangle point  triangle          Returns True if the point is inside the triangle     and returns False if it falls outside      - The argument  point  is a tuple with two elements     containing the X Y coordinates respectively      - The argument  triangle  is a tuple with three elements each     element consisting of a tuple of X Y coordinates       It works like this      Walk clockwise or counterclockwise around the triangle     and project the point onto the segment we are crossing     by using the dot product      Finally  check that the vector created is on the same side     for each of the triangle s segments                Unpack arguments     x  y   point     ax  ay   triangle 0      bx  by   triangle 1      cx  cy   triangle 2        Segment A to B     side 1    x - bx     ay - by  -  ax - bx     y - by        Segment B to C     side 2    x - cx     by - cy  -  bx - cx     y - cy        Segment C to A     side 3    x - ax     cy - ay  -  cx - ax     y - ay        All the signs must be positive or all negative     return  side 1  lt  0 0      side 2  lt  0 0      side 3  lt  0 0                                                                                   class TestPointInTriangle unittest TestCase        triangle     22   8                    12   55                    7   19        def test inside self           point    15  20          self assertTrue point in triangle point  self triangle        def test outside self           point    1  7          self assertFalse point in triangle point  self triangle        def test border case self              If the point is exactly on one of the triangle s edges          we consider it is inside             point    7  19          self assertTrue point in triangle point  self triangle                                                                                    if   name         main         suite   unittest defaultTestLoader loadTestsFromTestCase TestPointInTriangle      unittest TextTestRunner   run suite    There is an additional optional graphical test for the algorithm above to confirm its validity   import random from matplotlib import pyplot from triangle test import point in triangle                                                                                    The area   size x   64 size y   64    The triangle   triangle     22   8                12   55                7   19      Number of random points   count points   10000    Prepare the figure   figure   pyplot figure   axes   figure add subplot 111  aspect  equal   axes set title  Test the  point in triangle  function   axes set xlim 0  size x  axes set ylim 0  size y     Plot the triangle   from matplotlib patches import Polygon axes add patch Polygon triangle  linewidth 1  edgecolor  k   facecolor  none       Plot the points   for i in range count points       x   random uniform 0  size x      y   random uniform 0  size y      if point in triangle  x y   triangle   pyplot plot x  y    g       else                                   pyplot plot x  y    b      Save it   figure savefig  point in triangle pdf     Producing the following graphic

User · Answer

I just want to use some simple vector math to explain the barycentric coordinates solution which Andreas had given  it will be way easier to understand    Area A is defined as any vector given by s   v02   t   v01  with condition s    0 and t    0  If any point inside the triangle v0  v1  v2  it must be inside Area A       If further restrict s  and t belongs to  0  1   We get Area B which contains all vectors of s   v02   t   v01  with condition s  t belongs to  0  1   It is worth to note that the low part of the Area B is the mirror of Triangle v0  v1  v2  The problem comes to if we can give certain condition of s  and t  to further excluding the low part of Area B       Assume we give a value s  and t is changing in  0  1   In the following pic  point p is on the edge of v1v2  All the vectors of s   v02   t   v01 which are along the dash line by simple vector sum  At v1v2 and dash line cross point p  we have      1-s  v0v2     v0v2    tp v0v1     v0v1    we get 1 - s   tp  then 1   s   tp  If any t   tp  which 1  lt  s   t where is on the double dash line  the vector is outside the triangle  any t  lt   tp  which 1    s   t where is on single dash line  the vector is inside the triangle    Then if we given any s in  0  1   the corresponding t must meet 1    s   t  for the vector inside triangle      So finally we get v   s   v02   t   v01  v is inside triangle with condition s  t  s t belongs to  0  1   Then translate to point  we have  p - p0   s    p1 - p0    t    p2 - p0   with s  t  s   t in  0  1   which is the same as Andreas  solution to solve equation system p   p0   s    p1 - p0    t    p2 - p0   with s  t  s   t belong to  0  1

User · Answer

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  gt  0       if  c x-a x  as y- c y-a y  as x  gt  0    s ab  return false       if  c x-b x   s y-b y - c y-b y   s x-b x   gt  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

User · Answer

In general  the simplest  and quite optimal  algorithm is checking on which side of the half-plane created by the edges the point is   Here s some high quality info in this topic on GameDev  including performance issues   And here s some code to get you started   float sign  fPoint p1  fPoint p2  fPoint p3        return  p1 x - p3 x     p2 y - p3 y  -  p2 x - p3 x     p1 y - p3 y      bool PointInTriangle  fPoint pt  fPoint v1  fPoint v2  fPoint v3        float d1  d2  d3      bool has neg  has pos       d1   sign pt  v1  v2       d2   sign pt  v2  v3       d3   sign pt  v3  v1        has neg    d1  lt  0      d2  lt  0      d3  lt  0       has pos    d1  gt  0      d2  gt  0      d3  gt  0        return   has neg  amp  amp  has pos

User · Answer

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 lt 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 gt 0  and  1-s-t gt 0     and an example output

User · Answer

Supposedly high-performance code which I adapted in JavaScript  article below    function pointInTriangle  p  p0  p1  p2      return    p1 y - p0 y     p x - p0 x  -  p1 x - p0 x     p y - p0 y       p2 y - p1 y     p x - p1 x  -  p2 x - p1 x     p y - p1 y       p0 y - p2 y     p x - p2 x  -  p0 x - p2 x     p y - p2 y     gt   0       pointInTriangle p  p0  p1  p2  - for counter-clockwise triangles pointInTriangle p  p0  p1  p2  - for clockwise triangles   Look in jsFiddle  performance test included   there s also winding checking in a separate function  Or press  Run code snippet  below   x000D   x000D  var ctx      canvas   0  getContext  2d    x000D  var W   500  x000D  var H   500  x000D   x000D  var point     x  W   2  y  H   2    x000D  var triangle   randomTriangle    x000D   x000D     canvas   click function evt    x000D      point x   evt pageX -   this  offset   left  x000D      point y   evt pageY -   this  offset   top  x000D      test    x000D      x000D   x000D     canvas   dblclick function evt    x000D      triangle   randomTriangle    x000D      test    x000D      x000D   x000D  document querySelector   performance   addEventListener  click    testPerformance   x000D   x000D  test    x000D   x000D  function test     x000D      var result   checkClockwise triangle a  triangle b  triangle c    pointInTriangle point  triangle a  triangle c  triangle b    pointInTriangle point  triangle a  triangle b  triangle c   x000D       x000D      var info    point        point x         point y      n   x000D      info     triangle a        triangle a x         triangle a y      n   x000D      info     triangle b        triangle b x         triangle b y      n   x000D      info     triangle c        triangle c x         triangle c y      n   x000D      info     result        result    true     false    x000D   x000D          result   text info   x000D      render    x000D    x000D   x000D  function  testPerformance      x000D   var px       py       p0x       p0y       p1x       p1y       p2x       p2y       p       p0       p1       p2       x000D       x000D   for var i   0  i  lt  1000000  i      x000D      p i     x  Math random     100  y  Math random     100   x000D      p0 i     x  Math random     100  y  Math random     100   x000D      p1 i     x  Math random     100  y  Math random     100   x000D      p2 i     x  Math random     100  y  Math random     100   x000D      x000D    console time  optimal  pointInTriangle    x000D    for var i   0  i  lt  1000000  i      x000D      pointInTriangle p i   p0 i   p1 i   p2 i    x000D      x000D    console timeEnd  optimal  pointInTriangle    x000D   x000D    console time  original  ptInTriangle    x000D    for var i   0  i  lt  1000000  i      x000D     ptInTriangle p i   p0 i   p1 i   p2 i    x000D      x000D    console timeEnd  original  ptInTriangle    x000D    x000D   x000D  function pointInTriangle  p  p0  p1  p2    x000D   return    p1 y - p0 y     p x - p0 x  -  p1 x - p0 x     p y - p0 y       p2 y - p1 y     p x - p1 x  -  p2 x - p1 x     p y - p1 y       p0 y - p2 y     p x - p2 x  -  p0 x - p2 x     p y - p2 y     gt   0  x000D    x000D   x000D  function ptInTriangle p  p0  p1  p2    x000D      var s    p0 y   p2 x - p0 x   p2 y    p2 y - p0 y    p x    p0 x - p2 x    p y   x000D      var t    p0 x   p1 y - p0 y   p1 x    p0 y - p1 y    p x    p1 x - p0 x    p y   x000D   x000D      if  s  lt   0    t  lt   0  return false  x000D   x000D      var A    -p1 y   p2 x   p0 y    -p1 x   p2 x    p0 x    p1 y - p2 y    p1 x   p2 y   x000D      return  s   t   lt  A  x000D    x000D   x000D  function render     x000D      ctx fillStyle     CCC   x000D      ctx fillRect 0  0  500  500   x000D      drawTriangle triangle a  triangle b  triangle c   x000D      drawPoint point   x000D    x000D   x000D  function checkClockwise p0  p1  p2    x000D      var A    -p1 y   p2 x   p0 y    -p1 x   p2 x    p0 x    p1 y - p2 y    p1 x   p2 y   x000D      return A  gt  0  x000D    x000D   x000D  function drawTriangle p0  p1  p2    x000D      ctx fillStyle     999   x000D      ctx beginPath    x000D      ctx moveTo p0 x  p0 y   x000D      ctx lineTo p1 x  p1 y   x000D      ctx lineTo p2 x  p2 y   x000D      ctx closePath    x000D      ctx fill    x000D      ctx fillStyle     000   x000D      ctx font    12px monospace   x000D      ctx fillText  1   p0 x  p0 y   x000D      ctx fillText  2   p1 x  p1 y   x000D      ctx fillText  3   p2 x  p2 y   x000D    x000D   x000D  function drawPoint p    x000D      ctx fillStyle     F00   x000D      ctx beginPath    x000D      ctx arc p x  p y  5  0  2   Math PI   x000D      ctx fill    x000D    x000D   x000D  function rand min  max    x000D   return Math floor Math random      max - min   1     min  x000D    x000D   x000D  function randomTriangle     x000D      return   x000D          a    x  rand 0  W   y  rand 0  H     x000D          b    x  rand 0  W   y  rand 0  H     x000D          c    x  rand 0  W   y  rand 0  H    x000D         x000D    x000D   lt script src  https   cdnjs cloudflare com ajax libs jquery 1 9 1 jquery min js  gt  lt  script gt  x000D   lt button id  performance  gt Run performance test  open console  lt  button gt  x000D   lt pre gt Click  place the point  x000D  Double click  random triangle  lt  pre gt  x000D   lt pre id  result  gt  lt  pre gt  x000D   lt canvas width  500  height  500  gt  lt  canvas gt  x000D   x000D   x000D    Inspired by this  http   www phatcode net articles php id 459

User · Answer

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

User · Answer

Since there s no JS answer  Clockwise  amp  Counter-Clockwise solution   function triangleContains ax  ay  bx  by  cx  cy  x  y         let det    bx - ax     cy - ay  -  by - ay     cx - ax       return  det     bx - ax     y - ay  -  by - ay     x - ax    gt  0  amp  amp              det     cx - bx     y - by  -  cy - by     x - bx    gt  0  amp  amp              det     ax - cx     y - cy  -  ay - cy     x - cx    gt  0       EDIT  there was a typo for det computation  cy - ay instead of cx - ax   this is fixed   https   jsfiddle net jniac rctb3gfL    x000D   x000D  function triangleContains ax  ay  bx  by  cx  cy  x  y    x000D   x000D      let det    bx - ax     cy - ay  -  by - ay     cx - ax  x000D    x000D      return  det     bx - ax     y - ay  -  by - ay     x - ax    gt  0  amp  amp  x000D              det     cx - bx     y - by  -  cy - by     x - bx    gt  0  amp  amp  x000D              det     ax - cx     y - cy  -  ay - cy     x - cx    gt  0  x000D   x000D    x000D   x000D   x000D   x000D   x000D   x000D   x000D  let width   500  height   500 x000D   x000D     clockwise x000D  let triangle1     x000D   x000D   A     x  10  y  -10    x000D   C     x  20  y  100    x000D   B     x  -90  y  10    x000D    x000D   color    f00   x000D   x000D    x000D   x000D     counter clockwise x000D  let triangle2     x000D   x000D   A     x  20  y  -60    x000D   B     x  90  y  20    x000D   C     x  20  y  60    x000D   x000D   color    00f   x000D    x000D    x000D   x000D   x000D  let scale   2 x000D  let mouse     x  0  y  0   x000D   x000D   x000D   x000D   x000D   x000D   x000D     DRAW  gt  x000D   x000D  let wrapper   document querySelector  div wrapper   x000D   x000D  wrapper onmousemove      layerX x  layerY y      gt    x000D    x000D   x -  width   2 x000D   y -  height   2 x000D   x    scale x000D   y    scale x000D    x000D   mouse x   x x000D   mouse y   y x000D    x000D   drawInteractive   x000D   x000D    x000D   x000D  function drawArrow ctx  A  B    x000D   x000D   let v   normalize sub B  A   3  x000D   let I   center A  B  x000D    x000D   let p x000D    x000D   p   add I  rotate v  90   v  x000D   ctx moveTo p x  p y  x000D   ctx lineTo I x  I  y  x000D   p   add I  rotate v  -90   v  x000D   ctx lineTo p x  p y  x000D   x000D    x000D   x000D  function drawTriangle ctx    A  B  C  color      x000D   x000D   ctx beginPath   x000D   ctx moveTo A x  A y  x000D   ctx lineTo B x  B y  x000D   ctx lineTo C x  C y  x000D   ctx closePath   x000D    x000D   ctx fillStyle   color    6  x000D   ctx strokeStyle   color x000D   ctx fill   x000D    x000D   drawArrow ctx  A  B  x000D   drawArrow ctx  B  C  x000D   drawArrow ctx  C  A  x000D    x000D   ctx stroke   x000D   x000D    x000D   x000D  function contains   A  B  C    P    x000D   x000D   return triangleContains A x  A y  B x  B y  C x  C y  P x  P y  x000D   x000D    x000D   x000D  function resetCanvas canvas    x000D   x000D   canvas width   width x000D   canvas height   height x000D    x000D   let ctx   canvas getContext  2d   x000D   x000D   ctx resetTransform   x000D   ctx clearRect 0  0  width  height  x000D   ctx setTransform scale  0  0  scale  width 2  height 2  x000D    x000D    x000D   x000D  function drawDots     x000D   x000D   let canvas   document querySelector  canvas dots   x000D   let ctx   canvas getContext  2d   x000D   x000D   resetCanvas canvas  x000D    x000D   let count   1000 x000D   x000D   for  let i   0  i  lt  count  i      x000D   x000D    let x   width    Math random   -  5  x000D    let y   width    Math random   -  5  x000D     x000D    ctx beginPath   x000D    ctx ellipse x  y  1  1  0  0  2   Math PI  x000D     x000D    if  contains triangle1    x  y       x000D     x000D     ctx fillStyle     f00  x000D     x000D      else if  contains triangle2    x  y       x000D     x000D     ctx fillStyle     00f  x000D     x000D      else   x000D     x000D     ctx fillStyle     0003  x000D     x000D      x000D   x000D     x000D    ctx fill   x000D     x000D     x000D    x000D    x000D   x000D  function drawInteractive     x000D   x000D   let canvas   document querySelector  canvas interactive   x000D   let ctx   canvas getContext  2d   x000D   x000D   resetCanvas canvas  x000D    x000D   ctx beginPath   x000D   ctx moveTo 0  -height 2  x000D   ctx lineTo 0  height 2  x000D   ctx moveTo -width 2  0  x000D   ctx lineTo width 2  0  x000D   ctx strokeStyle     0003  x000D   ctx stroke   x000D    x000D   drawTriangle ctx  triangle1  x000D   drawTriangle ctx  triangle2  x000D    x000D   ctx beginPath   x000D   ctx ellipse mouse x  mouse y  4  4  0  0  2   Math PI  x000D    x000D   if  contains triangle1  mouse     x000D    x000D    ctx fillStyle   triangle1 color    a  x000D    ctx fill   x000D     x000D     else if  contains triangle2  mouse     x000D    x000D    ctx fillStyle   triangle2 color    a  x000D    ctx fill   x000D     x000D     else   x000D    x000D    ctx strokeStyle    black  x000D    ctx stroke   x000D     x000D     x000D    x000D    x000D   x000D  drawDots   x000D  drawInteractive   x000D   x000D   x000D   x000D   x000D   x000D   x000D   x000D   x000D   x000D   x000D     trigo x000D   x000D  function add    points    x000D    x000D   let x   0  y   0 x000D    x000D   for  let point of points    x000D    x000D    x    point x x000D    y    point y x000D    x000D     x000D    x000D   return   x  y   x000D   x000D    x000D   x000D  function center    points    x000D    x000D   let x   0  y   0 x000D    x000D   for  let point of points    x000D    x000D    x    point x x000D    y    point y x000D    x000D     x000D    x000D   x    points length x000D   y    points length x000D    x000D   return   x  y   x000D   x000D    x000D   x000D  function sub A  B    x000D   x000D   let x   A x - B x x000D   let y   A y - B y x000D    x000D   return   x  y   x000D   x000D    x000D   x000D  function normalize   x  y    length   10    x000D   x000D   let r   length   Math sqrt x   x   y   y  x000D    x000D   x    r x000D   y    r x000D    x000D   return   x  y   x000D   x000D    x000D   x000D  function rotate   x  y    angle   90    x000D   x000D   let length   Math sqrt x   x   y   y  x000D    x000D   angle    Math PI   180 x000D   angle    Math atan2 y  x  x000D    x000D   x   length   Math cos angle  x000D   y   length   Math sin angle  x000D    x000D   return   x  y   x000D   x000D    x000D      x000D   margin  0  x000D    x000D   x000D  html   x000D   font-family  monospace  x000D    x000D   x000D  body   x000D   padding  32px  x000D    x000D   x000D  span red   x000D   color   f00  x000D    x000D   x000D  span blue   x000D   color   00f  x000D    x000D   x000D  canvas   x000D   position  absolute  x000D   border  solid 1px  ddd  x000D    x000D   lt p gt  lt span class  red  gt red triangle lt  span gt  is clockwise lt  p gt  x000D   lt p gt  lt span class  blue  gt blue triangle lt  span gt  is couter clockwise lt  p gt  x000D   lt br gt  x000D   lt div class  wrapper  gt  x000D    lt canvas id  dots  gt  lt  canvas gt  x000D    lt canvas id  interactive  gt  lt  canvas gt  x000D   lt  div gt  x000D   x000D   x000D      I m using here the same method as described above  a point is inside ABC if it is respectively on the  same  side of each line AB  BC  CA

User · Answer

Solve the following equation system   p   p0    p1 - p0    s    p2 - p0    t   The point p is inside the triangle if 0  lt   s  lt   1 and 0  lt   t  lt   1 and s   t  lt   1   s t and 1 - s - t are called the barycentric coordinates of the point p

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

Examples related to algorithm

Examples related to math

Examples related to geometry