Point in Triangle
Given a triangle by its vertices' coordinations , and . You are asked that if any point 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 and , the cross product of them is:
Where is the angle between those two vectors and is a vector in a third dimention that is perpendicular to both and . If we use Cartesian coordinate to prepresent the two vectors as and , we can get
Based on this, we can give some solutions to this problem.
Use areas of triangles
This is a straightforward solution. If is in , then we must have the sum of areas of , and is the same of the area of . Otherwise the sum will be greater than that of .
To calculate the area of a triangle , we can use cross product as
Use vector space
We know if form a triangle, at most two points of the three are on a line. So we can uses and to form a vector space where can be represented as:
We caluclate the dot products of the equation above with and and get
And from this we can induct:
Then if and and , is in , otherwise it is out of it.
Use vector relationships
The third and the best solution is making use of the relative position of and the all of three side of the triangle. We know, if is at the clockwise side of , the cross product of will be negative, or if it is at counterclockwise, the cross product is positive.
So we can uses cross product to decide if is at the same side of , and . In other words, if we let:
We can decide if is in by checking if is both positive or negative. If so, it is in the triangle. Especially, if one of is zero, then is on one side of .