How To Determine if a Point Is in a 2D Triangle

1. Overview

In this tutorial, we’ll discuss how to detect if a point lies inside a 2D triangle.

First, we’ll define the problem and demonstrate it with an example. Then, we’ll present three approaches to solving this problem. In the first approach, we’ll use the formula of the triangle area. For the second one, we’ll use line segment intersection. Finally, in the last approach, we’ll use cross-product.

2. Defining the Problem

Here we have a triangle, $T$ , defined by three points $A$ , $B$ , and $C$ . We also have a point $P$ . Now we want to check if the point $P$ lies inside the triangle $ABC$ or not.

For better understanding, let’s take a look at the following example:

In figure A, the given point $P$ lies outside the triangle $T$ ; therefore, the answer is $false$ .

In contrast, in figure B, the given point $P$ lies inside triangle $T$ . Thus, the answer is $true$ .

3. Triangles Area Approach

3.1. Mathematical Idea

The main idea of this approach is to check if the area of triangle $\boldsymbol{T}$ is equal to the sum of areas of sub triangles $\boldsymbol{ABP}$ , $\boldsymbol{BCP}$ , and $\boldsymbol{ACP}$ . Then the point $\boldsymbol{P}$ lies inside the triangle $\boldsymbol{T}$ . Otherwise, it’s outside.

Initially, we’ll create three triangles $ACP$ , $ABP$ , and $BCP$ . Let’s take a look at the following illustration:

As we can see, the sum of areas of the three sub triangles $ACP$ , $ABP$ , and $BCP$ is equal to the area of triangle $ABC$ . Therefore, the point $P$ is inside the given triangle $T$ . We can get the area of a triangle from the coordinates of its vertices using the cross product.

Recall that the triangle described by points $\boldsymbol{(A, B, C)}$ has an area equal to:

$\mathbf{ \frac{|CrossProduct(B - A, C - A)|}{2} }$

Finally, if the sum of the three triangles $ACP$ , $ABP$ , and $BCP$ is equal to the sum of the given triangle $ABC$ , that means the point $P$ is inside the given triangle. Otherwise, it’s outside.

3.2. Triangle Area

Now, let’s take a look at the algorithm to get the triangle’s area using cross-product:

Initially, we define the $TriangleArea$ function that will return the area of a triangle described by three points. Furthermore, the function will have three parameters, $A$ , $B$ , and $C$ , which will represent the coordinate of the vertices of the triangle.

First, we get two vectors, $AB$ and $AC$ , by subtracting the coordinate of the start point from the endpoint of the vector. After that, we multiply these two vectors using any of the two cross-product formulas.

Finally, the area of the triangle $(A, B, C)$ will be equal to the absolute value of the cross-product divided by two.

3.3. Algorithm

Let’s check the implementation of the algorithm:

Initially, we define the $InsideTriangle$ function that will return whether the given point $P$ is inside the triangle $ABC$ or not. Furthermore, the function will have four parameters: $P$ the point we want to check if it’s inside the triangle or not, $A$ , $B$ , and $C$ the vertices of the given triangle $T$ .

First, we declare $triangle \_ area$ , representing the area of the given triangle $T$ . Second, we declare $area \_ sum$ , which will represent the sum of areas of the sub triangles $ABP$ , $ACP$ , and $BCP$ . Then, we add the area of each of the previous sub triangles to the $arae \_ sum$ variables.

Finally, if the $triangle \_ area$ is equal to $area \_ sum$ , that means the point $P$ is inside the triangle $ABC$ . Therefore, we return true. Otherwise, it’s outside, so we return false.

4. Line Segment Intersection Approach

4.1. Mathematical Idea

In this approach, we draw a line segment $\boldsymbol{S}$ defined by the given point $\boldsymbol{P}$ and a random point far away from $\boldsymbol{P}$ . Next, we count the number of intersection points between the given triangle segments and the segment $\boldsymbol{S}$ . If the number of intersections is odd, that means the point $\boldsymbol{P}$ is inside the triangle $\boldsymbol{T}$ . Otherwise, it’s outside.

Let’s take a look at the following illustration for a better understanding:

As we can see in figure A, point $P$ is outside the triangle $T$ . We draw a line-segment $S$ that start from $P$ and go somewhere far away from $P$ , and this segment $S$ intersect with the segments of the triangle $T$ at two points, so the point $P$ is outside the triangle $T$ since the number of intersection points is even. In contrast, point $P$ is inside the triangle $T$ since the number of intersection points is odd in figure B.

In conclusion, we can imagine that for each intersection point, the point $P$ is changing its state. For the first intersection, the point $P$ moves from outside the triangle to the inside. Then, at the second intersection, it moves from the inside to the outside, and so on.

The only weak case we can face in this approach is if we draw the segment $S$ in such a way that makes it pass through one of the triangle vertices. So, if the point $P$ is inside the triangle, we’ll have two intersection points which means it’s outside while it’s not.

In order to avoid this problem, we choose the point $Q$ to be a random point far from $P$ , such that we decrease the probabilities of passing through any triangle’s vertex.

4.2. Algorithm

Now, let’s take a look at the implementation of the algorithm:

Initially, we define the $InsideTriangle$ function the same as the previous approach.

First, we declare segment $S$ , which is defined by point $P$ and a random point at infinity that is far away from $P$ . Second, we declare $intersections$ , which represents the number of intersection points between the segment $S$ and the triangle segments. Then, for each segment of the triangle $T$ , we call the function isIntersect between the current segment and the segment $S$ . That function will return $1$ if the given segments intersect. Otherwise, it will return $0$ .

Finally, the $intersections$ variable will be storing the number of intersection points. If the number of intersection points is odd, the point $P$ is inside the triangle $ABC$ , so we return true. Otherwise, it’s outside, so we return false.

5. Orientation Approach

5.1. Mathematical Idea

In this approach, we’ll check for all triangle segments if the point $\boldsymbol{P}$ lies on the same side (inner side), which means the point $\boldsymbol{P}$ is inside the triangle $\boldsymbol{T}$ . Otherwise, it’s outside.

Initially, we’ll check for each triangle’s segment the position of the point $P$ if it lies to the right or the left of the tested segment. We can get this orientation using cross-product.

Recall $\boldsymbol{cross\_product(V_1, V_2)}$ is less than $\boldsymbol{0}$ if the vector $\boldsymbolV_1}$ is to the left of the vector $\boldsymbol{V_2}$ , and it’s greater than $\boldsymbol{0}$ if it’s to the right.

In the end, if point $P$ lies on the left for all triangle segments or to the right for all triangle segments, that means the point $P$ is inside the triangle $T$ . Otherwise, it’s not.

5.2. Orientation

Take a look at the algorithm to get the orientation of three points:

Initially, we define the $Orient$ function that will return the orientation of the given points, whether they make a left turn or a right turn. Furthermore, the function will have three parameters, $A$ , $B$ , and $C$ , which will represent the coordinate of the given points.

First, we get two vectors, $AB$ and $AC$ , by subtracting the coordinate of the start point from the endpoint of the vector. Then, we multiply these two vectors using any of the two cross-product formulas.

Finally, if the $cross \_ product$ is greater than $0$ , that means we did a left turn (the point $C$ lies on the left side of segment $AB$ ), so we return $1$ . Otherwise, we made a right turn, and we return $-1$ .

5.3. Algorithm

Let’s check the implementation of the algorithm:

Initially, we define the $InsideTriangle$ function the same as the previous approach.

First, we declare variable $turns$ , which will store the sum of the orientation of point $P$ respective to all triangle segments.

Finally, if the absolute value of $turns$ is equal to $3$ , that means the point $P$ lies on the same side for all segments, and it’s inside the triangle $ABC$ , so we return true. Otherwise, it’s outside, so we return false.

6. Conclusion

In this article, we learned how to detect if a point lies inside a 2D triangle or not.

First, we provided an example to explain the problem. Then, we explored three different approaches to solving it.

Finally, we walked through the implementations and explained the time complexity for each algorithm.

The time complexity of all algorithms is $\boldsymbol{O(1)}$ . This is because we’re doing a constant number of arithmetic operations for each approach

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex