homechevron_rightStudychevron_rightMathchevron_rightGeometry

Is a point in a triangle?

The calculator determines if an arbitrary point lies inside 2D triangle. The triangle is defined by 3 cartesian coordinate pairs.

The calculator below determines if a given point is inside a 2D triangle. The calculator uses a simple algorithm based on vector cross product features. The algorithm detailed description is right behind the calculator.

PLANETCALC, Point in triangle

Point in triangle

Digits after the decimal point: 2
Is point in triangle
 

Cross products (z-coordinate)

AB x AP
 
BC x BP
 
CA x CP
 

A point inside a triangle. The algorithm description

3-dimensional vectors a and b cross product result for the right orthonormal basis is defined as:
 \mathbf {a} \times \mathbf {b} =(a_{y}b_{z}-a_{z}b_{y},\;a_{z}b_{x}-a_{x}b_{z},\;a_{x}b_{y}-a_{y}b_{x}) [1].
Cross product is anticommutative:
 \mathbf {a} \times \mathbf {b} =-\mathbf {b} \times \mathbf {a}
It is important feature to solve the point and triangle problem.

Pairwise vector cross product of the side of the triangle and the ray to the point
Pairwise vector cross product of the side of the triangle and the ray to the point



To determine if a point P is inside a triangle ABC we compute 3 cross products: ABxAP, BCxBP and CAxCP. Since we are in 2D space, third vector coordinate (z) equals to 0. According to formula [1] we don't need to calculate first two coordinates, since the result x,y coordinate is always 0, because z coordinate is 0 (the result vector is perpendicular to ABC plane). The sign of remained (z) coordinate depends on the relative position of the vectors. If the first vector appears on the right of the second one, the z coordinate is positive, if the first vector appears on the left of the second one, the z coordinate is negative, otherwise (both vectors point to the same direction) the result is 0.
The remaining step to solve our problem is to analyse signs of the z coordinates. If we have both positive and negative results then the point is outside the triangle, if we have only positive or only negative signs - the point is inside the triangle.
The following table illustrates all possible solutions

Drawing Description

atriangle_c_negative.png

atriangle_c_positive.png

All results are negative or positive.
The point is inside the triangle.

atriangle_c_zero1.png

One result is zero, the remaining ones is all positive or all negative.
The point lies on a side of the triangle.
If two results are zero, then the point coincides with a triangle vertex.

atriangle_c_outside.png

We have both positive and negative results.
The point is outside the triangle.
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Is a point in a triangle?

Comments