IQotW 2020-02-10

isInTriangle.py

# Given an array of points that represent the 3 vertices of a triangle, and a point K, return true if K is inside the triangle.

# Example:
# let triangle = [ [0,0], [0,3], [4,0] ]
# isInTriangle(triangle, [2,1])
# > true
# isInTriangle(triangle, [3,2])
# > false

import math

def lineLength(A, B):
    a = (A[0] - B[0]) ** 2
    b = (A[1] - B[1]) ** 2
    c = a + b
    return math.sqrt(c)

# https://sciencing.com/area-scalene-triangle-10015426.html
# Heron's formula : Area = square root [s (s - a) (s - b) (s - c)]
# where s = (a + b + c) / 2
def triangleArea(triangle):
    segmentA = lineLength(triangle[0], triangle[1])
    segmentB = lineLength(triangle[1], triangle[2])
    segmentC = lineLength(triangle[2], triangle[0])
    s = (segmentA + segmentB + segmentC) / 2
    a = math.sqrt(s * (s - segmentA) * (s - segmentB) * (s - segmentC))
    return a

def isInTriangle(triangle, point):
    area = triangleArea(triangle)
    areaPart1 = triangleArea([ point, triangle[1], triangle[2]])
    areaPart2 = triangleArea([ triangle[0], point, triangle[2]])
    areaPart3 = triangleArea([ triangle[0], triangle[1], point])

    if abs(area - ( areaPart1 + areaPart2 + areaPart3)) < 0.001:
        return True
    else:
        return False

triangle = [ [0,0], [0,3], [4,0] ]

print(isInTriangle(triangle, [ 2,1 ]))
print(isInTriangle(triangle, [ 3,2 ]))