Find if a point is within a triangle.



Task

   Assume points are on a plane defined by (x, y) real number coordinates.
   Given a point P(x, y) and a triangle formed by points A, B, and C, determine if P is within triangle ABC. 
   You may use any algorithm. 
   Bonus: explain why the algorithm you chose works.


Related tasks

   Determine_if_two_triangles_overlap


Also see

 Discussion of several methods. [[1]]
 Determine if a point is in a polygon [[2]]
 Triangle based coordinate systems [[3]]
 Wolfram entry [[4]]


V EPS = 0.001
V EPS_SQUARE = EPS * EPS
 
F side(p1, p2, p)
   R (p2.y - p1.y) * (p.x - p1.x) + (-p2.x + p1.x) * (p.y - p1.y)
 
F distanceSquarePointToSegment(p1, p2, p)
   V p1P2SquareLength = sqlen(p2 - p1)
   V dotProduct = dot(p - p1, p2 - p1) / p1P2SquareLength
   I dotProduct < 0
      R sqlen(p - p1)
   I dotProduct <= 1
      V pP1SquareLength = sqlen(p1 - p)
      R pP1SquareLength - dotProduct * dotProduct * p1P2SquareLength
   R sqlen(p - p2)
 
T Triangle
   (Float, Float) p1, p2, p3
 
   F (p1, p2, p3)
      .p1 = p1
      .p2 = p2
      .p3 = p3
 
   F String()
      R ‘Triangle[’(.p1)‘, ’(.p2)‘, ’(.p3)‘]’
 
   F.const pointInTriangleBoundingBox(p)
      V xMin = min(.p1.x, min(.p2.x, .p3.x)) - :EPS
      V xMax = max(.p1.x, max(.p2.x, .p3.x)) + :EPS
      V yMin = min(.p1.y, min(.p2.y, .p3.y)) - :EPS
      V yMax = max(.p1.y, max(.p2.y, .p3.y)) + :EPS
      R !(p.x < xMin | xMax < p.x | p.y < yMin | yMax < p.y)
 
   F.const nativePointInTriangle(p)
      V checkSide1 = side(.p1, .p2, p) >= 0
      V checkSide2 = side(.p2, .p3, p) >= 0
      V checkSide3 = side(.p3, .p1, p) >= 0
      R checkSide1 & checkSide2 & checkSide3
 
   F.const accuratePointInTriangle(p)
      I !.pointInTriangleBoundingBox(p)
         R 0B
      I .nativePointInTriangle(p)
         R 1B
      I distanceSquarePointToSegment(.p1, .p2, p) <= :EPS_SQUARE
         R 1B
      I distanceSquarePointToSegment(.p2, .p3, p) <= :EPS_SQUARE
         R 1B
      R distanceSquarePointToSegment(.p3, .p1, p) <= :EPS_SQUARE
 
F test(t, p)
   print(t)
   print(‘Point ’p‘ is within triangle ? ’(I t.accuratePointInTriangle(p) {‘true’} E ‘false’))
 
V p1 = (1.5, 2.4)
V p2 = (5.1, -3.1)
V p3 = (-3.8, 1.2)
V tri = Triangle(p1, p2, p3)
test(tri, (0.0, 0.0))
test(tri, (0.0, 1.0))
test(tri, (3.0, 1.0))
print()
p1 = (1.0 / 10, 1.0 / 9)
p2 = (100.0 / 8, 100.0 / 3)
p3 = (100.0 / 4, 100.0 / 9)
tri = Triangle(p1, p2, p3)
V pt = (p1.x + 3.0 / 7 * (p2.x - p1.x), p1.y + 3.0 / 7 * (p2.y - p1.y))
test(tri, pt)
print()
p3 = (-100.0 / 8, 100.0 / 6)
tri = Triangle(p1, p2, p3)
test(tri, pt)