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=xa⋅yb−ya⋅xa
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
S△ABC=|→AB||→AC|sinθ/2=|(xb−xa)(yc−ya)−(yb−ya)(xc−xa)|/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=u→AB+v→AC
We caluclate the dot products of the equation above with →AB and →AC and get
→AP⋅→AB=u→AB⋅→AB+v→AC⋅→AB→AP⋅→AC=u→AB⋅→AC+v→AC⋅→AC
And from this we can induct:
u=→(AB⋅→AB)→(AP⋅→AC)−→(AC⋅→AB)→(AP⋅→AB)→(AC⋅→AC)→(AB⋅→AB)−→(AB⋅→AC)→(AB⋅→AC)v=→(AC⋅→AC)→(AP⋅→AB)−→(AC⋅→AB)→(AP⋅→AC)→(AC⋅→AC)→(AB⋅→AB)−→(AB⋅→AC)→(AB⋅→AC)
Then if u∈[0,1] and v∈[0,1] and u+v≤1, 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.