# Testing whether a tetrahedron lies inside a Polyhedron

I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$.

I would like to add one detail to the problem in case it may contribute to the solution: $t$ is a Delaunay tetrahedron and faces of $p$ are triangular and are strongly Delaunay both with respect to vertices of $p$. A tetrahedron is Delaunay if circumsphere of its vertices contains no other vertex inside it. A face is strongly Delaunay if there exists a circumsphere containing vertices of that face on its surface but no other vertex on or inside it.

Following figures show the same problem in $2D$ space:

The original polygon $p$:

Delaunay triangulation of vertices of $p$:

Result of inside/outside test over triangles $t$(Shaded triangles are inside $p$ and rest are outside):

Desired result(pruning outside triangles):

My original problem is in 3D space so triangles $t$ in above figures translate to tetrahedrons and polygon $p$ translates to an arbitrary polyhedron $p$. I have figured out some formulations of this problem:

Formulation 1
The only parts of $t$ which can be outside $p$ are its edges and triangular faces but in general there may exist a $p$ which has edges of all outside $t$'s on its surface, so alternatively, this problem may also be formulated as to test whether for a tetrahedron $t$ there exists a face which lies outside $p$?

Formulation 2
I have another possible perspective towards this problem but lacking any formal idea:
Geometrically, if $t$ is outside then it will always be sticking on the outer surface of $p$. So if we can compute the contours(informally, the outer boundary) $C_{V}$ and $C_{V_{p}}$ such that $V=V_{t}\cup V_{p}$ and $V_t,V_p$ are sets of vertices in $t,p$ respectively, then $C_{V}=C_{V_p}$ iff $t$ lies inside $p$.

I would like to know:

• How can I solve either of Formulation 1 or Formulation 2?
• Or, is there any completely different approach to solve this?

Update:
I now realize that this problem can be reduced to Point in polyhedron problem. Since an outside tetrahedron $t$ will have at least one face which lies outside $p$, so any arbitrary point on that face(except its vertices,in general) will always lie outside $p$. Therefore, for each face of $t$, I need to take an arbitrary point and test if that point lies outside $p$.

From point in polygon article I came to know about Ray casting algorithm and Winding number algorithm. Ray casting is not numerically stable for cases where point lies on the surface of $p$. But numerical robustness of Winding number algorithm has not been addressed there.

Based on above, my core problem now seems to be(please suggest if it should be asked as a separate question):
Is there any numerically robust algorithm for point in polygon problem?

• Just to clarify: 1) Can the polyhedron $p$ be non-convex, and 2) if $t$ and $p$ share a face or an edge (or part of one), does that disqualify $t$ from being "inside" of $p$? (Obviously, based on your requirements, $t$ and $p$ must be allowed to share vertices.) – Ilmari Karonen May 31 '14 at 17:01
• @IlmariKaronen 1) Yes 2). No, as far as I can imagine, the only difference between inside and outside tetrahedron will be that its non-shared face/edge will lie outside if $t$ is outside $p$ and inside if $t$ is inside $p$(as I have also mentioned under Formulation 1). BTW, what do you mean by "...or part of one..."? – Pranav Jun 1 '14 at 1:34
• Two coplanar faces or collinear edges might overlap only partially. This could happen even if $p$ itself has no coincident faces or edges, as long as it has more than two collinear or more than three coplanar vertices. – Ilmari Karonen Jun 1 '14 at 1:39
• non-convexity has the oddity that all vertices can be inside the polyhedron and yet the tetrahedron can be outside (since an edge need not lie inside as a whole). Possible algorithm, see if edges (between polyhedron and tetrahedron) can have intersections => prob that tetrahedron lies outside is great – Nikos M. Jun 4 '14 at 20:36
• Have you seen the Gilbert–Johnson–Keerthi distance algorithm? You would need to decompose the polygon/polyhedron into convex shapes first (as you noted, a simplicial complex would do the job). GJK is known to be very stable and very fast. – Pseudonym Jan 6 '17 at 1:55

Problem can be solved if I compute the generalized winding number of the centroid of $t$ against the surface of $p$.
• Point containment will not solve the problem: Picture $p$ a triangular prism with one side of ("Platonic") $t$ (slightly smaller, inside,) parallel and near to one of the triangular faces of $p$. Now subtract from $p$ a "needle tetrahedron" from the middle of that face to near one of the vertices "in the opposite face": None of $t$'s vertices is outside $p$, none of $p$'s vertices is inside $t$, yet $t$ is not inside $p$. – greybeard Feb 4 '17 at 11:18