## 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, , defined by three points , , and . We also have a point . Now we want to check if the point lies inside the triangle or not.

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

In figure A, the given point lies outside the triangle ; therefore, the answer is .

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

## 3. Triangles Area Approach

### 3.1. Mathematical Idea

**The main idea of this approach is to check if the area of triangle is equal to the sum of areas of sub triangles , , and . Then the point lies inside the triangle . Otherwise, it’s outside.**

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

As we can see, the sum of areas of the three sub triangles , , and is equal to the area of triangle . Therefore, the point is inside the given triangle . 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 has an area equal to:**

Finally, if the sum of the three triangles , , and is equal to the sum of the given triangle , that means the point 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 function that will return the area of a triangle described by three points. Furthermore, the function will have three parameters, , , and , which will represent the coordinate of the vertices of the triangle.

First, we get two vectors, and , 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 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 function that will return whether the given point is inside the triangle or not. Furthermore, the function will have four parameters: the point we want to check if it’s inside the triangle or not, , , and the vertices of the given triangle .

First, we declare , representing the area of the given triangle . Second, we declare , which will represent the sum of areas of the sub triangles , , and . Then, we add the area of each of the previous sub triangles to the variables.

Finally, if the is equal to , that means the point is inside the triangle . 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 defined by the given point and a random point far away from . Next, we count the number of intersection points between the given triangle segments and the segment . If the number of intersections is odd, that means the point is inside the triangle . 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 is outside the triangle . We draw a line-segment that start from and go somewhere far away from , and this segment intersect with the segments of the triangle at two points, so the point is outside the triangle since the number of intersection points is even. In contrast, point is inside the triangle since the number of intersection points is odd in figure B.

In conclusion, we can imagine that for each intersection point, the point is changing its state. For the first intersection, the point 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 in such a way that makes it pass through one of the triangle vertices. So, if the point 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 to be a random point far from , 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 function the same as the previous approach.

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

Finally, the variable will be storing the number of intersection points. If the number of intersection points is odd, the point is inside the triangle , 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 lies on the same side (inner side), which means the point is inside the triangle . Otherwise, it’s outside.**

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

**Recall is less than if the vector is to the left of the vector , and it’s greater than if it’s to the right**.

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

### 5.2. Orientation

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

Initially, we define the 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, , , and , which will represent the coordinate of the given points.

First, we get two vectors, and , 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 is greater than , that means we did a left turn (the point lies on the left side of segment ), so we return . Otherwise, we made a right turn, and we return .

### 5.3. Algorithm

Let’s check the implementation of the algorithm:

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

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

Finally, if the absolute value of is equal to , that means the point lies on the same side for all segments, and it’s inside the triangle , 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 . **This is because we’re doing a constant number of arithmetic operations for each approach