Intereting Posts

Second Stiefel-Whitney Class of a 3 Manifold
Closure of union of two sets
Convergence of $\int f dP_n$ to $\int f dP$ for all Lipschitz functions $f$ implies uniform integrability
What are zero divisors used for?
Relation between Hermite polynomials and Brownian motion (on martingale property)
The king comes from a family of 2 children. What is the probability that the other child is his sister?
No consistent theory can define a product of distributions: why?
Geometric mean of prime gaps?
Explicit example of a non-trivial zero of Riemann zeta function
Formula for prime counting function
Expectation of Double Dice Throw
Classifying complex $2\times 2$ matrices up to similarity
Solve problem of trigonometry.
Can this be proved using definite integrals
How to expand a representation

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.

- Composing permutations in factorial notation
- Help understanding the complexity of my algorithm (summation)
- An algorithm for making conditionally convergent series take arbitrary values?
- Maximization with xor operator
- Asymptotically optimal algorithms
- Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

- A natural number multiplied by some integer results in a number with only ones and zeros
- Mathematically representing combinations with integers uniquely?
- merge sort vs insertion sort time complexity
- Explanation needed on this rather basic recurrence solution
- Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$
- Finding equation of an ellipsoid
- Rabin and Shallit Algorithm
- Efficiently partition a set into all possible unique pair combinations
- Help understanding the complexity of my algorithm (summation)
- How to approach number guessing game(with a twist) algorithm?

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.

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$.

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|<1$.

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.

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$.

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.

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.

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 !

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.

- Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$
- Bounds on the gaps in a variant of polylog-smooth numbers.
- Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm
- fast algorithm for solving system of linear equations
- Prove that the series $\sum_{n=1}^\infty \left$ converges
- Can a circle's circumference be divided into arbitrary number of equal parts using straight edge and compass only?
- Set and its Complement are Measure Dense
- Evaluating $\lim_{x\to0}\frac{1-\cos(x)}{x}$
- a problem on solving a determinant equation
- Group question: only one element $x$ with order $n>1$, then $x\in Z(G)$
- How to prove $\left(\frac{a}{(a,b)}, \frac{b}{(a,b)}\right) = 1$?
- Einstein Summation with multiple terms
- Evaluating the series $\sum_{n=1}^{\infty} \frac{1}{n^{3} \binom{2n}{n}} $
- Separable Hahn-Banach and the axiom of choice
- Why should I consider the components $j^2$ and $k^2$ to be $=-1$ in the search for quaternions?