如何确定一个点是否在2D三角形内

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 ABC or not.

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

Triangle1

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

In contrast, in figure B, the given point lies inside triangle . 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 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 $\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 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:

algorithm TriangleArea(A, B, C):
    // INPUT
    //    A = the first vertex of the triangle
    //    B = the second vertex of the triangle
    //    C = the third vertex of the triangle
    // OUTPUT
    //    The area of the triangle formed by points A, B, and C

    AB <- Vector(B.x - A.x, B.y - A.y)
    AC <- Vector(C.x - A.x, C.y - A.y)
    cross_product <- AB.x * AC.y - AB.y * AC.x 

    return |cross_product| / 2

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, , , 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 (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:

algorithm TrianglesAreaApproach(P, A, B, C):
    // INPUT
    //    P = the point to check if it is inside the triangle
    //    A = the first vertex of the triangle
    //    B = the second vertex of the triangle
    //    C = the third vertex of the triangle
    // OUTPUT
    //    Returns true if the point P is inside the triangle ABC, false otherwise

    triangle_area <- TriangleArea(A, B, C)
    area_sum <- 0

    area_sum <- area_sum + TriangleArea(A, B, P)
    area_sum <- area_sum + TriangleArea(A, C, P)
    area_sum <- area_sum + TriangleArea(B, C, P)

    if triangle_area = area_sum:
        return true
    else:
        return false

Initially, we define the InsideTriangle function that will return whether the given point is inside the triangle ABC 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 $triangle \_ area$ , representing the area of the given triangle . 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 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 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:

algorithm InsideTriangle(P, A, B, C):
    // INPUT
    //    P = the point we want to check if it's inside the triangle
    //    A = the first vertex of the triangle
    //    B = the second vertex of the triangle
    //    C = the third vertex of the triangle
    // OUTPUT
    //    Returns true if point P is inside the triangle ABC, otherwise false

    S <- Segment(P, Point(infinity, infinity))
    intersections <- 0
    
    intersections <- intersections + isIntersect(S, Segment(A, B))
    intersections <- intersections + isIntersect(S, Segment(A, C))
    intersections <- intersections + isIntersect(S, Segment(B, C))

    if intersections mod 2 = 1:
        return true
    else:
        return false

Initially, we define the InsideTriangle 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 intersections , 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 intersections variable will be storing the number of intersection points. If the number of intersection points is odd, the point 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 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 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:

algorithm Orient(A, B, C):
    // INPUT
    //    A = the first vertex of the triangle
    //    B = the second vertex of the triangle
    //    C = the third vertex of the triangle
    // OUTPUT
    //    1 if the orientation makes a left turn (C is on the left side of AB)
    //    -1 if the orientation makes a right turn (C is on the right side of AB)

    AB <- Vector(B.x - A.x, B.y - A.y)
    AC <- Vector(C.x - A.x, C.y - A.y)
    cross_product <- AB.x * AC.y - AB.y * AC.x

    if cross_product > 0:
        return 1
    else:
        return -1

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, , , 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 $cross \_ product$ 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:

algorithm InsideTriangle(P, A, B, C):
    // INPUT
    //    P = the point to check
    //    A = the first vertex of the triangle
    //    B = the second vertex of the triangle
    //    C = the third vertex of the triangle
    // OUTPUT
    //    Returns true if P is inside the triangle ABC, false otherwise

    turns <- Orient(A, B, P) + Orient(B, C, P) + Orient(C, A, P)

    if |turns| = 3:
        return true
    else:
        return false

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 respective to all triangle segments.

Finally, if the absolute value of turns is equal to , that means the point 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

Persistence

REST

Security