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


EPS = 0.001
EPS_SQUARE = EPS * EPS
 
function side(x1, y1, x2, y2, x, y)
    return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1)
end
 
function naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
    local checkSide1 = side(x1, y1, x2, y2, x, y) >= 0
    local checkSide2 = side(x2, y2, x3, y3, x, y) >= 0
    local checkSide3 = side(x3, y3, x1, y1, x, y) >= 0
    return checkSide1 and checkSide2 and checkSide3
end
 
function pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)
    local xMin = math.min(x1, x2, x3) - EPS
    local xMax = math.max(x1, x2, x3) + EPS
    local yMin = math.min(y1, y2, y3) - EPS
    local yMax = math.max(y1, y2, y3) + EPS
    return not (x < xMin or xMax < x or y < yMin or yMax < y)
end
 
function distanceSquarePointToSegment(x1, y1, x2, y2, x, y)
    local p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)
    local dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength
    if dotProduct < 0 then
        return (x - x1) * (x - x1) + (y - y1) * (y - y1)
    end
    if dotProduct <= 1 then
        local p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)
        return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength
    end
    return (x - x2) * (x - x2) + (y - y2) * (y - y2)
end
 
function accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
    if not pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) then
        return false
    end
    if naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) then
        return true
    end
    if distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE then
        return true
    end
    if distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE then
        return true
    end
    if distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE then
        return true
    end
    return false
end
 
function printPoint(x, y)
    io.write('('..x..", "..y..')')
end
 
function printTriangle(x1, y1, x2, y2, x3, y3)
    io.write("Triangle is [")
    printPoint(x1, y1)
    io.write(", ")
    printPoint(x2, y2)
    io.write(", ")
    printPoint(x3, y3)
    print("]")
end
 
function test(x1, y1, x2, y2, x3, y3, x, y)
    printTriangle(x1, y1, x2, y2, x3, y3)
    io.write("Point ")
    printPoint(x, y)
    print(" is within triangle? " .. tostring(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)))
end
 
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0)
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1)
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1)
print()
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348)
print()
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348)
print()