Detect if point is inside triangle

There are a number of ways to detect if a point is inside a given triangle. The method shown here is the barycentric coordinate method. The barycentric method is a "complete" solution that will work regardless of the order of the triangle's vertices, and allows you to choose whether to include points on the edges of the triangle.

Note that this code is not optimized for physics engines. It uses division, a costly operation, and generally uses more operations than other algorithms. A different approach may be more suitable for your use case.

Time Complexity: O(1)

Space Complexity: O(1)

Code

Given:

Point p: List[int]
Vertices a, b, c: List[int]

px, py = p
ax, ay = a
bx, by = b
cx, cy = c

# Area is negative if the points are ordered in a clockwise direction (doesn't impact the result)
area = 0.5 * (-by * cx + ay * (-bx + cx) + ax * (by - cy) + bx * cy)

s = 1 / (2 * area) * (ay * cx - ax * cy + (cy - ay) * px + (ax - cx) * py)
t = 1 / (2 * area) * (ax * by - ay * bx + (ay - by) * px + (bx - ax) * py)

return s > 0 and t > 0 and 1 - s - t > 0

The point lies on the edge of the triangle if at least one of the coordinates is 0 and the other two are between 0 and 1 inclusive.

Explanation

Why this works is not entirely intuitive, especially if you are unfamiliar with barycentric coordinates. I recommend reading the Wikipedia page, since I will not be going through all of the math. Barycentric coordinates specify the location of a point in relation to a triangle. The coordinates act as masses placed on the vertices which specify how close the point is to each vertex.

Barycentric coordinates are typically represented with lambda (λ). For every point P inside of a triangle △ABC, there is a unique sequence of barycentric coordinates such that:

\lambda_1 + \lambda_2 + \lambda_3 = 1

\lambda_1 , \lambda_2 , \lambda_3 \ge 0

P = \lambda_1 * A + \lambda_2 * B + \lambda_3 * C

In our code, s , t , and 1 - s - t correspond to the λs. Notice that since the barycentric coordinates sum to 1, λ₃ can be derived from 1 - λ₁ - λ₂. Let's substitute this value for λ₃ into the equation above, and split our coordinates into x and y components:

x = \lambda_1 * x_a + \lambda_2 * x_b + (1 - \lambda_1 - \lambda_2) * x_c \\ y = \lambda_1 * y_a + \lambda_2 * y_b + (1 - \lambda_1 - \lambda_2) * y_c

Now you have 2 equations, and 2 variables, and are able to solve for λ₁ and λ₂. This is the part I'll leave as an exercise to the reader. The code I presented is not the most efficient way to calculate these values, but I didn't feel like trying to optimize it.

Finally, if a point is on the edge of the triangle or located at one of the vertices, the following will hold:

0 \le \lambda_i \le 1 \space \forall \space i \space \mathrm{in} \space 1, 2, 3 \space \mathrm{and} \\ \space \lambda_i = 0 \space \mathrm{for} \space \mathrm{some} \space i \space \mathrm{in} \space 1, 2, 3

If you are interested in different and more optimized solutions, this Stackoverflow thread may be helpful.

paramnesia

Detect if point is inside triangle

Code

Explanation