[Non-obvious algorithms of obvious things] Algorithm 2. The point belongs to a triangle in space

A series of posts [Unobvious algorithms of obvious things] will contain action algorithms that seem obvious and simple, but if you ask yourself the question “how is this done?”, The answer is far from obvious. Of course, all these algorithms can be found in the literature. Under the cat is the algorithm for determining whether a point P belongs to a triangle ABC in space .

The belonging of the point P to the triangle ABC in space

Idea

Sometimes it is necessary to determine whether a point belongs to a geometric shape. The simplest is the triangle ABC.

Given:

Point P (P_x, P_y, P_z), a triangle with vertices: A (A_x, A_y, A_z), B (B_x, B_y, B_z), C (C_x, C_y, C_z).

technique

Three triangles are formed: ABP, ACP, BCP. After that, their areas are calculated S _ABP , S _ACP , S _BCP . After that, the sum of these areas is verified with the area of ​​the triangle S _ABC . If the point lies on the triangle ABC, then the triangles ABP, ACP, BCP will be simply parts of the triangle ABC, and the sum of their areas will be equal to its area S _ABC . If the point does not belong to a triangle, the sum of the areas S _ABP , S _ACP , S _BCP will exceed the area of ​​the triangle ABC.
Easy lyrical digression for those who do not remember what the area of ​​the triangle is equal to: it is easiest to use the formula of Gerona , which allows you to find the area of ​​the triangle, knowing only its sides, very good. conveniently

Function code:

#define EPS 1e-10 float triangle_square(float a,float b, float c){ float p=(a+b+c)/2; return sqrt(p*(pa)*(pb)*(pc)); } float inside_triangle(float P_x,float P_y, float P_z, float A_x, float A_y, float A_z, float B_x, float B_y, float B_z, float C_x, float C_y, float C_z){ int inside=0; float AB=sqrt( (A_x-B_x)*(A_x-B_x) + (A_y-B_y)*(A_y-B_y) + (A_z-B_z)*(A_z-B_z) ); float BC=sqrt( (B_x-C_x)*(B_x-C_x) + (B_y-C_y)*(B_y-C_y) + (B_z-C_z)*(B_z-C_z) ); float CA=sqrt( (A_x-C_x)*(A_x-C_x) + (A_y-C_y)*(A_y-C_y) + (A_z-C_z)*(A_z-C_z) ); float AP=sqrt( (P_x-A_x)*(P_x-A_x) + (P_y-A_y)*(P_y-A_y) + (P_z-A_z)*(P_z-A_z) ); float BP=sqrt( (P_x-B_x)*(P_x-B_x) + (P_y-B_y)*(P_y-B_y) + (P_z-B_z)*(P_z-B_z) ); float CP=sqrt( (P_x-C_x)*(P_x-C_x) + (P_y-C_y)*(P_y-C_y) + (P_z-C_z)*(P_z-C_z) ); float diff=(triangle_square(AP,BP,AB)+triangle_square(AP,CP,CA)+triangle_square(BP,CP,BC))-triangle_square(AB,BC,CA); if (fabs(diff)<EPS) inside=1; return inside; } 

If suddenly someone is too lazy to attach math.h, then you can use the root function from this post .