17
$\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$
16
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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 '11 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$ – Ross Millikan Jul 14 '11 at 13:04
  • $\begingroup$ Worked great, thanks. $\endgroup$ – Casey Jul 14 '11 at 19:45
  • $\begingroup$ A crossproduct yields the vector which stands perpendicular to the other two. $\endgroup$ – Antares May 1 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 at 0:20
12
$\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 planar vector cross products to get the weights, without having to shift the origin to $A$. Given the original 2D 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$ 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;
| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is superior to the accepted answer (which is a binary decision) when you need Barycentric coordinates for something, e.g., interpolation. $\endgroup$ – Sibbs Gambling Mar 26 '17 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 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$ – John Alexiou Jan 2 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 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$ – John Alexiou Jan 2 at 17:56
6
$\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.

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
2
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I believe this will be problematic if dealing with floating point numbers. $\endgroup$ – M.B. Jul 13 '11 at 23:59
  • $\begingroup$ @M.B.: As an issue of precision? $\endgroup$ – Isaac Jul 14 '11 at 0:01
  • $\begingroup$ Isaac: Yes. Comparing floating point numbers by equality is never advised. $\endgroup$ – M.B. Jul 14 '11 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 '11 at 0:16
0
$\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 !

| cite | improve this answer | |
$\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.