best way to check if a point lies inside a triangle or not

general
, , ,
1

Given the coordinates of 3 vertices of a triangle and a point. What is the most accurate and efficient way to determine if the given point is inside the triangle?

2 Likes
2

Suppose A,B & C are the given coordinates of triangle and P is the point that you want to check weather it is inside of \Delta{ABC} or not.

Now if
area(\Delta{ABC}) = area(\Delta{ABP}) + area(\Delta{BCP}) + area(\Delta{ACP})
then the point P is inside the triangle otherwise not. It also works if the point is on one of sides of triangle. You can find area of triangle using {Hero's} formula.

4 Likes
3

What if P is outside the triangle but the sum of area PAB,BCP,ACP still equal to area of ABC?

1 Like
4

You can use dot product to find that, assume that p1, p2, p3 are ordered in counterclockwise, then we can check if p lies at left of the 3 oriented edges [p1, p2], [p2, p3] and [p3, p1], if all the dot products are of the same sign then p is on the same side of all, and thus inside.

For that, consider 3 vectors v1, v2 and v3 that are respectively left-orthogonal to [p1, p2], [p2, p3] and [p3, p1] :

**v1 = (y2 - y1, -x2 + x1)

v2 = (y3 - y2, -x3 + x2)

v3 = (y1 - y3, -x1 + x3)
**

then take the following vectors:

**v1’ = (x - x1, y - y1)

v2’ = (x - x2, y - y2)

v3’ = (x - x3, y - y3)
**

Now compute dot products as:

dot1 = v1 . v1’ = (y2 - y1)(x - x1) + (-x2 + x1)(y - y1)

dot2 = v1 . v2’ = (y3 - y2)(x - x2) + (-x3 + x2)(y - y2)

dot3 = v3 . v3’ = (y1 - y3)(x - x3) + (-x1 + x3)(y - y3)

Now, p lies in triangle if and only if dot1>=0 && dot2>=0 && dot3>=0.

P.S.: Here is a neat implementation of the approach described above in C++, link.

You can refer to this link for more information link

1 Like
5

If the point is outside the triangle then it is impossible…(Take out pen and paper and try drawing figures you’ll come to know and its too easy)

6

The simplest approach I can think of is, take a point at infinity ( largest value in constraints ) and connect given point to this point and now find the intersection of this line with all the edges of the triangle ( or any convex polygon ) .
if the total number of intersections is equal to “1” then it lies inside else not.

5 Likes
7

A(x1,y1)
/
/
/
/ P \
/
B(x2,y2)--------C(x3,y3)
Let the coordinates of A, B, and C are (x1, y1), (x2, y2) and (x3, y3) respectively. And coordinates of the given point P be (x, y)

Algorithm :
1. Calculate area of the triangle ABC. let the area is A.
   Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2

2. We can use the same formula to calculate the triangle PAB. Let the area is A1.
3. Calculate area of the triangle PBC. Let this area be A2.
4. Calculate area of the triangle PAC. Let this area be A3.
4.if(A = A1+A2+A3) print : P lies inside the triangle. Otherwise Not.
1 Like