Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

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:

Triangle1

 

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:

Triangle2

 

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Triangle3

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!