Point in Triangle

Given a triangle by its vertices' coordinations A=(xa,ya), B=(xb,yb) and C=(xc,yc). You are asked that if any point P=(xp,yp) is in the triangle.

There are serveral solutions to this problem. Most of them will make use of cross product operator of two vector.

Assume we have two vectors a and b, the cross product of them is:

a×b=|a||b|sinθn

Where sinθ is the angle between those two vectors and n is a vector in a third dimention that is perpendicular to both a and b. If we use Cartesian coordinate to prepresent the two vectors as a=(xa,ya) and b=(xb,yb), we can get

a×b=xaybyaxa

Based on this, we can give some solutions to this problem.

Use areas of triangles

This is a straightforward solution. If P is in ABC, then we must have the sum of areas of ABP, BCP and ACP is the same of the area of ABC. Otherwise the sum will be greater than that of ABC.

To calculate the area of a triangle ABC, we can use cross product as

SABC=|AB||AC|sinθ/2=|(xbxa)(ycya)(ybya)(xcxa)|/2

Use vector space

We know if ABC form a triangle, at most two points of the three are on a line. So we can uses AB and AC to form a vector space where P can be represented as:

AP=uAB+vAC

We caluclate the dot products of the equation above with AB and AC and get

APAB=uABAB+vACABAPAC=uABAC+vACAC

And from this we can induct:

u=(ABAB)(APAC)(ACAB)(APAB)(ACAC)(ABAB)(ABAC)(ABAC)v=(ACAC)(APAB)(ACAB)(APAC)(ACAC)(ABAB)(ABAC)(ABAC)

Then if u[0,1] and v[0,1] and u+v1, P is in ABC, otherwise it is out of it.

Use vector relationships

The third and the best solution is making use of the relative position of P and the all of three side of the triangle. We know, if AP is at the clockwise side of AB, the cross product of AB×AP will be negative, or if it is at counterclockwise, the cross product is positive.

So we can uses cross product to decide if P is at the same side of AB, BC and CA. In other words, if we let:

t1=AB×APt2=BC×BPt3=CA×CP

We can decide if P is in ABC by checking if t1,t2,t3 is both positive or negative. If so, it is in the triangle. Especially, if one of ti is zero, then P is on one side of ABC.