Algorithm that determines whether a point is inside a triangle or rectangle

Given
the coordinates (x_{1},y_{1},z_{1}),
(x_{2},y_{2},z_{2}), (x_{3},y_{3},z_{3})
of three points P_{1}, P_{2} and P_{3}, we
want to determine whether a given fourth point P_{0}(x_{0},y_{0},z_{0}),
which lies on the same plane with the other three, is inside the
triangle formed by them.

First, we calculate the vectors a = P_{0 }-
P_{1}, b = P_{0 }- P_{2}, c =P_{0 }-
P_{3 }and after that, the vectors _{
,}
_{
,} _{
.
}The sum of the above vectors is _{
}.
We define q_{1}=Q×Q_{1},
q_{2}= Q×Q2,
q_{3}= Q×Q_{3}
ÎÂ.
The point P_{0} is inside the triangle (P_{1}, P_{2},
P_{3}) iff q_{1}, q_{2} and q_{3} are
all positive (q_{1}>0, q_{2}>0 and q_{3}>0).
If one of them is zero, P_{0} is probably on the boundary.

If we have a rectangle instead of a triangle, the
method is quite simple: we could divide the rectangle area into two
triangles, and apply the point-is-triangle algorithm to both of them.
If P_{0} is on the boundary of both triangles, it must be
either inside the rectangle, or on one of the rectangle’s
vertices.

Given the coordinates (x_{1},y_{1},z_{1}),
(x_{2},y_{2},z_{2}) of two points P_{1}
and P_{2}, which define a linear segment, we want to
calculate the minimum distance between it and a given point
P_{0}(x_{0},y_{0},z_{0}). Both P_{1}
and P_{2} are on the line E defined by P_{1} and _{
.}
The projection of point P_{0} on E is _{
}= P_{1} + t _{
},
where _{
.}
The point _{
}is part of P_{1}P_{2} if and only if _{
,} _{
}. In this case, the minimum distance is _{
}. If _{
}is not part of P_{1}P_{2}, the minimum distance
is min _{
.}

Minimum distance between a point and a polygon in three-dimensional space

Given
the coordinates (x_{1},y_{1},z_{1}),
(x_{2},y_{2},z_{2}),… (x_{N},y_{N},z_{N})
of N points P_{1}, P_{2}, .., P_{N}, which
lie on the same plane forming a polygon, we want to calculate the
minimum distance between the above polygon and a given point
P_{0}(x_{0},y_{0},z_{0}).

Since in our case the polygon is an organ contour,
we assume that all contour points have the same z coordinate, z_{p}=z_{i},
i=1, 2,…, N. The projection of point P_{0} on the
plane z=z_{p} is the point PP_{0}(x_{0},y_{0},z_{p}).
Now, there are two possibilities: the point PP_{0} is either
inside or outside of the polygon (P_{1}, P_{2}, ..,
P_{N}). In the first case, the minimum distance between the
polygon and P_{0} is _{
}.

In the second case, more calculations have to be
done. The minimum distance between the polygon and P_{0} is
equal to the minimum distance between P_{0} and the closest
edge of the polygon, _{
},
i=1, 2,…, N.

Minimum distance between a point and a triangle in three-dimensional space

Given
the coordinates (x_{1},y_{1},z_{1}),
(x_{2},y_{2},z_{2}), (x_{3},y_{3},z_{3})
of three points P_{1}, P_{2} and P_{3}, we
want to calculate the minimum distance between the triangle formed by
them and a given fourth point P_{0}(x_{0},y_{0},z_{0}).

The
points P_{1}, P_{2} and P_{3} define a plane
Ax+By+Cz+D=0, where

A=_{,}
B=_{,
}C=_{,}

and D=-(Ax_{0}+By_{0}+Cz_{0}).
The vector _{
}={A,B,C} is perpendicular to that plane.

The
projection of P_{0} on that plane is _{
}=
P_{0} + t _{
},
where t=_{
}If _{
}is inside the triangle, the minimum distance between the point
P_{0} and the triangle { P_{1}, P_{2}, P_{3}}
is equal to the minimum distance between the point P_{0} and
the plane {A, B, C, D}, that is _{
},
or _{
}

If
_{
}is not inside the triangle, the minimum distance is equal to
the minimum distance from the closest of the three edges _{
}, _{
},
_{
}of the triangle.