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]]


 
type p2d
    x as double   'define a two-dimensional point
    y as double
end type
 
function in_tri( A as p2d, B as p2d, C as p2d, P as p2d ) as boolean
    'uses barycentric coordinates to determine if point P is inside
    'the triangle defined by points A, B, C
    dim as double AreaD = (-B.y*C.x + A.y*(-B.x + C.x) + A.x*(B.y - C.y) + B.x*C.y)
    dim as double s = (A.y*C.x - A.x*C.y + (C.y - A.y)*P.x + (A.x - C.x)*P.y)/AreaD
    dim as double t = (A.x*B.y - A.y*B.x + (A.y - B.y)*P.x + (B.x - A.x)*P.y)/AreaD
    if s<=0 then return false
    if t<=0 then return false
    if s+t>=1 then return false
    return true
end function
 
dim as p2d A,B,C,P    'generate some arbitrary triangle
A.x = 4.14 : A.y = -1.12
B.x = 8.1 : B.y =-4.9 
C.x = 1.5: C.y = -9.3
 
for y as double = -0.25 to -9.75 step -0.5    'display a 10x10 square
    for x as double = 0.125 to 9.875 step 0.25
        P.x = x : P.y = y
        if in_tri(A,B,C,P) then print "@"; else print ".";   'with all the points inside the triangle indicated
    next x
    print
next y
 