23
$\begingroup$

Is there an algorithm available to determine if a point P lies inside a triangle ABC defined as three points A, B, and C? (The three line segments of the triangle can be determined as well as the centroid if they are needed.)

Grid space is defined as Screen Space, that is, 2D Cartesian with the Y-Axis flipped so "up" is negative y and the origin is the upper left corner.

$\endgroup$

7 Answers 7

18
$\begingroup$

This is a fairly well known algorithm. It all comes down to using the cross product. Define the vectors $AB$, $BC$ and $CA$ and the vectors $AP$, $BP$ and $CP$. Then $P$ is inside the triangle formed by $A, B$ and $C$ if and only if all of the cross products $AB\times AP$, $BC\times BP$ and $CA\times CP$ point in the same direction relative to the plane. That is, either all of them point out of the plane, or all of them point into the plane.

Update: this test can be performed using dot products.

Update 2: As emphasised in the comments, you only have to compare signs of the third components.

$\endgroup$
5
  • 2
    $\begingroup$ Remind me again: A vector is defined as the two points at each end, and...what's the definition of the cross product and dot product? (For once, wikipedia isn't the way to go for a "simple" answer. :P ) $\endgroup$
    – Casey
    Jul 14, 2011 at 1:25
  • $\begingroup$ @Casey: actually the formula for cross product is in Wikipedia. Your vectors have only two components, so $(x_1,y_1,0)\times (x_2,y_2,0)=(0,0,x_1y_2-x_2y_1)$ and you just look at the signs of the third components. $\endgroup$ Jul 14, 2011 at 13:04
  • $\begingroup$ Worked great, thanks. $\endgroup$
    – Casey
    Jul 14, 2011 at 19:45
  • $\begingroup$ A crossproduct yields the vector which stands perpendicular to the other two. $\endgroup$
    – Antares
    May 1, 2020 at 0:10
  • $\begingroup$ The dot product gives a scalar value t which is the effective/projected length from a on b (it is the "shadow" which would be falling on b if parallel light is coming from above, orthognal on b). Interesting special cases are, that the dot product is 0 when the input vectors are orthogonal and 1 if they are parallel. $\endgroup$
    – Antares
    May 1, 2020 at 0:20
16
$\begingroup$

Method

To test any point $P=(x,y)$, first move the origin at one vertex, like $A$ such that $$ B \rightarrow B - A $$ $$ C \rightarrow C - A $$ $$ P \rightarrow P - A $$

Then I calculate the scalar $ d = x_B y_C - x_C y_B $ and the three Barycentric weights

$$ \begin{matrix} w_A = \frac{ x ( y_B-y_C) + y ( x_C-x_B) + x_B\; y_C - x_C\; y_B}{d} \\ w_B = \frac{ x\; y_C - y\; x_C }{d} \\ w_C = \frac{ y\; x_B - x\; y_B }{d} \end{matrix} $$

The point is inside when all weights are between $0\ldots1$.

Examples

Test Case 1

Example: $A=(1,1)$ $B=(4,2)$ $C=(2,7)$. Consider a point $P=(2,3)$ then the scalar is: $d=17$ and three weights are: $w_A = \frac{8}{17}$, $w_B = \frac{4}{17}$ and: $ w_C=\frac{5}{17}$ which are all $w_i \geq 0$ and $w_i \leq 1$.

Test Case 2

On the other hand if $P=(1.5,5)$ then: $w_A = \frac{13}{34} $, $w_B = -\frac{1}{17}$ and: $ w_C=\frac{23}{34}$ and since $w_B$ does not fall between $0\ldots1$ then the point is outside.

Proof

Use homogeneous coordinates with: $A=(x_A,y_A,1)$, $B=(x_B,y_B,1)$, $C=(x_C,y_C,1)$, $P=(x,y,1)$ and use the following relation $$ P = w_A\;A + w_B\;B+w_C\;C $$ to solve for $w_A$, $w_B$ and $w_C$.

The notice that the equation $w_A=0$ described the line $BC$ and the equation $w_A=1$ a line parallel to $BC$ through $A$. Similarly for the other weights. The region where all the weights are $w_i\geq0$ and $ w_i\leq1$ is the triangle described by $ABC$.

Appendix

The more general procedure uses vector cross products to get the weights, without having to shift the origin to $A$. Given the original 2D or 3D vectors $A$, $B$, $C$ and $P$ the barycentric weights are

$$ \begin{aligned} w_A & = \tfrac{ B \times C + P \times (B-C) }{ A\times B + B \times C + C \times A } \\ w_B & = \tfrac{ C \times A + P \times (C-A) }{ A\times B + B \times C + C \times A } \\ w_C & = \tfrac{ A \times B + P \times (A-B) }{ A\times B + B \times C + C \times A } \\ \end{aligned} $$

where $A \times B = x_A \, y_B - y_A \, x_B$ for 2D vectors, and similarly for the rest of the cross products.

C# Code

The code below is tested and it works

public bool GetWeights(Vector2 point, out double w_A, out double w_B, out double w_C)
{
    double xd = Cross(A, B) + Cross(B, C) + Cross(C, A);

    if (Abs(xd) > 1e-13)
    {
        double xa = Cross(B, C) + Cross(point, B - C);
        double xb = Cross(C, A) + Cross(point, C - A);
        double xc = Cross(A, B) + Cross(point, A - B);

        w_A = xa / xd;
        w_B = xb / xd;
        w_C = xc / xd;
    }
    w_A = 0;
    w_B = 0;
    w_C = 0;
    return false;
}

public static double Cross(Vector2 a, Vector2 b) => a.X*b.Y - a.Y*b.X;
$\endgroup$
7
  • 3
    $\begingroup$ This is superior to the accepted answer (which is a binary decision) when you need Barycentric coordinates for something, e.g., interpolation. $\endgroup$ Mar 26, 2017 at 20:49
  • $\begingroup$ If (x, y) = (0, 0) it seems like this always produces the same result (weights of 1, 0, and 0), if I am not mistaken. Is this a special case? $\endgroup$
    – Jack Moody
    Jan 2, 2020 at 16:41
  • $\begingroup$ @JackMoody - What is your triangle? I tested with a random triangle and P=[0,0] and I get the correct weights. I have unit testing for this code. $\endgroup$ Jan 2, 2020 at 17:37
  • $\begingroup$ When x = 0 and y = 0 shouldn't w_b and w_c always be 0? And also w_a = (x_b * y_c - x_c * y_b) / (x_b * y_c - x_c * y_b) = 1? $\endgroup$
    – Jack Moody
    Jan 2, 2020 at 17:45
  • 1
    $\begingroup$ Remember to shift $P$ such that $A$ is the new origin in order to use the component method above. That makes $x$ and $y$ not zero unless they lie on $A$ at which point the result is $(1,0,0)$. Otherwise use the more general method, I just added to the answer. Numerically they both produce the same result (verified with CAS system). $\endgroup$ Jan 2, 2020 at 17:56
5
$\begingroup$

Given three non-collinear points in $\mathbb{R}^2$ (the vertices of a triangle) $A,B,C$ and a point $P$, there is a unique way to represent $P$ as $$ P=\lambda_A A + \lambda_B B + \lambda_C C $$ with $\lambda_A,\lambda_B,\lambda_C$ being real coefficients fulfilling $\lambda_A+\lambda_B+\lambda_C=1$. This kind of representation is also known as exact barycentric coordinates. The coefficients $\lambda_A,\lambda_B,\lambda_C$ are straightforward to find through linear algebra and the point $P$ strictly lies on the interior of $ABC$ iff $$\lambda_A>0,\quad\lambda_B>0,\quad\lambda_C>0,$$ that is equivalent to $$ \begin{pmatrix}1 & 1 & 1 \\ x_A & x_B & x_C \\ y_A & y_B & y_C\end{pmatrix}^{-1} \begin{pmatrix}1 \\ x_P \\ y_P\end{pmatrix}>0. $$

An equivalent alternative, assuming that $A,B,C$ are counter-clockwise ordered, is to compute the (oriented) areas of $ABP,BCP,CAP$ through the shoelace formula and check that all these (oriented) areas are positive.

Update. The (seemingly) most efficient approach just requires $\color{red}{6}$ multiplications (as already studied on SO). Without loss of generality, by using a translation we may assume that $A$ is the origin. Up to relabeling $B$ and $C$, we may also assume that $O,B,C$ are counter-clockwise oriented. Let $\varphi$ be the linear map bringing $B$ to $(1,0)$ and $C$ to $(0,1)$: $P$ lies inside $OBC$ iff $\varphi^{-1}(P)$ lies inside the right isosceles triangle with vertices at $(0,0),(1,0),(0,1)$, so in order to check if $P$ lies inside $OBC$ we just have to set $$ v = \begin{pmatrix}y_C & -x_C \\ -y_B & x_B \end{pmatrix}\begin{pmatrix}x_P \\ y_P\end{pmatrix},\qquad D=x_B y_C-x_C y_B $$ then check that all the conditions $$ v_x > 0,\qquad v_y > 0,\qquad v_x+v_y < D $$ hold. Just $\color{red}{6}$ multiplications and a few comparisons/sums/subtractions are involved.

$\endgroup$
3
$\begingroup$

I think you could check by computing the area of $\triangle ABC$, $\triangle ABP$, $\triangle BCP$, and $\triangle ACP$ (which can be done relatively easily from the coordinates of the points), and if $k_{\triangle ABC}=k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$ (where $k_\_$ is the area), then $P$ is inside the triangle (or possibly on its boundary), but if $k_{\triangle ABC}< k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$, $P$ is outside the triangle.

$\endgroup$
4
  • $\begingroup$ I believe this will be problematic if dealing with floating point numbers. $\endgroup$
    – M.B.
    Jul 13, 2011 at 23:59
  • $\begingroup$ @M.B.: As an issue of precision? $\endgroup$
    – Isaac
    Jul 14, 2011 at 0:01
  • $\begingroup$ Isaac: Yes. Comparing floating point numbers by equality is never advised. $\endgroup$
    – M.B.
    Jul 14, 2011 at 0:03
  • $\begingroup$ @M.B.: Testing for equality isn't necessary—testing $k_{\triangle ABC}< k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$ is sufficient to determine that $P$ is outside the triangle. $\endgroup$
    – Isaac
    Jul 14, 2011 at 0:16
3
$\begingroup$

Yes, this problem certainly has come up a lot before. Eric Haines wrote about the more general "point in polygon" problem (whose algorithms can be vastly simplified for the triangular case) in Graphics Gems IV. He also presented a method using barycentric coordinates in this Dr. Dobb's Journal article.

$\endgroup$
1
$\begingroup$

I wrote a complete article about point in triangle test. It shows the barycentric, parametric and dot product based methods.

Then it deals with the accuracy problem occuring when a point lies exactly on one edge (with examples). Finally it exposes a complete new method based on point to edge distance.

http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html

Enjoy !

$\endgroup$
0
$\begingroup$

Let us suppose point $P$ is inside $\triangle ABC$. Consider the line passing through $A$ and $B$. It divides the plane into two zones. $P$ and $C$ are in the same zone (why?). This simple property allows us to write an algorithm that answers OP's question.

Pick any vertex, see if that vertex and $P$ are on the same side of the line passing through the other two vertices. If the answer is yes for any selected vertex, then $P$ is inside $\triangle ABC$.

This method can be generalized for convex polygons, if the order of the vertices is given.

Note: to check if two points are on the same side of the line, plug the coordinates of each point in the equation of the line. The two points are on the same side of the line if and only if the two calculated numbers have the same sign.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.