How to find if a point is inside a Triangle
This project is part of my fr3fou/random-stuff repo where I attempt to solve small, random problems.
It demonstrates how to determine whether an arbitrary point lays inside a triangle, given only the 3 points of the triangle.
It works by checking if the area of the "main" triangle is equal to the sum of all the possible triangles formed, using the point, as shown below.
Given
P_1 = (1, 1) # First point of triangle
P_2 = (5, 1) # Second point of triangle
P_3 = (1, 5) # Third point of triangle
S = (3, 2) # Example of point inside triangle
Q = (3, -1) # Example of point outside triangle
We can compute the area of our main triangle △ P_1 P_2 P_3. This can be achieved using some basic linear algebra. As demonstrated in [1] and proven in [2], we can compute the area of it, using the Determinant of the following matrix:
...where X_1, Y_1 and so on, are the coordinates of each point in the triangle.
We can then apply the same algorithm to each subsequent triangle:
# Combinations of triangles, given S
△ P_1 P_2 S
△ P_1 S P_3
△ S P_2 P_3
# Combinations of triangles, given Q
△ P_1 P_2 Q
△ P_1 Q P_3
△ Q P_2 P_3
We can now finally check if the point resides inside or outside the triangle. By getting the absolute values of the triangle areas we are interested in (for example, only those, formed given S) and ensuring that their sum is equal to the area of our main triangle △ P_1 P_2 P_3 we will know whether the point is inside or outside.
You can check the source code at fr3fou/random-stuff