How to check if a 3 dimensional point lies in a Polygon with 4 vertices

Question

Can anyone provide an equation to this problem?

Given that I have a 3 dimensional polygon that consist of 4 vertices, how do I check if pointX lies inside that polygon?

Answer 1

Let's start with an example. If you want to define a segment $AB$ you can start from $A$ and add the vector $B-A$ (this is the vector going from $A$ to B) multiplied for a coefficient $t$ between $0$ and $1$ to get every point of the segment. So your segment can be described as

$A + t(B-A) = A(1-t) + tB$.

As you can see, the sum of the coefficients for $A$ and $B$ is $1$. Now given a new point $C$, you want to check if it is inside the segment or not. Notice that $A,B,C$ are know (for example are expressed with their coordinates in 3-dimensional space), so in order to check if $C$ is inside $AB$ or not, you just have to pose

$A(1-t) + tB = C$

and find $0 \leq t \leq 1$. If you can find $t$, the point is inside, if you can't it is not.

Let's do the same with our problem: Let $ABCD$ be the vertices of your polyedron. If you think at $D$ as the starting point, you can create your polyedron by adding to D any combination of vectors $DA$, $DB$, $DC$, multiplied respectively for coefficients $a,b,c$ between $0$ and $1$. So our polyedron is

$D + a(A-D) + b(B-D) +c(C-D) = aA + bB + cC + (1-a-b-c)D$.

with $a+b+c = 1$. Given a new point $Q = (x,y,z)$, is it inside? If you express $A,B,C$ and $D$ with their coordinates and solve

aA + bB + cC + (1-a-b-c)D = (x,y,z)

if you can find $a,b,c$ which are all between $0$ and $1$ and $a+b+c = 1$ the point is inside, otherwise it is not.

EXAMPLE:

Let $D = (0,0,0)$, A = (1,0,0), B = (0,1,0), C = (0,0,1) the vertex of our polyedron. We can write our polyedron in this way

P = aA + bB + cC + (1-a-b-c)D = (a,b,c).

with $a+b+c = 1$, and $0 \leq a,b,c \leq 1$.

Is a new point $Q = (1/2,1/3,1/2)$ inside? We must solve

(a,b,c) = (1/2,1/3,1/2)

which is $a = 1/2$, $b= 1/3$, $c=1/2$ they are all in the range, but $a+b+c = 4/3 \not = 1$ so $Q$ is not inside.

Is a new point $Z=(1/3,1/3,1/3)$ insiede? We must solve

(a,b,c) = (1/3,1/3,1/3)

which is $a = 1/3$, $b= 1/3$, $c=1/3$ they are between $0$ and $1$, and their sum is $1$, so $Z$ is inside the polyedron.