= Solution
Insert the <points> in their given order, starting from $ABCD$. Use outward face orientation and regard $f\le0$ as the interior side. The initial <tetrahedron> is nondegenerate because
$$
((B-A)\times(C-A))\cdot(D-A)=(-2,0,2)\cdot(0,1,1)=2\ne0.
$$
Thus its volume is $|2|/6=1/3$. The following table gives consistently oriented faces, conveniently scaled <plane> equations, and the omitted old <vertex of a polyhedron> test:
|| Face order
|| Interior inequality
|| Value at the opposite vertex
| $ACB$
| $x-z\le0$
| $f(D)=-1$
| $ABD$
| $x\le0$
| $f(C)=-1$
| $ADC$
| $-2x-y+z-1\le0$
| $f(B)=-2$
| $BCD$
| $-2x+y+z-1\le0$
| $f(A)=-2$
Every opposite <vertex of a polyhedron> is strictly on the interior side, so these orientations are correct. The intersection of these four <half-spaces> is exactly the initial <tetrahedron>.
Now test $E=(1,0,0)$. In the same row order the face expressions give
$$
\boxed{(f_{ACB}(E),f_{ABD}(E),f_{ADC}(E),f_{BCD}(E))=(1,1,-3,-3).}
$$
Therefore $ACB$ and $ABD$ are visible and must be removed; $ADC$ and $BCD$ are retained. The common edge $AB$ lies inside the deleted patch and is removed. The directed horizon is
$$
A\longrightarrow C\longrightarrow B\longrightarrow D\longrightarrow A.
$$
Cone this cycle to $E$, giving outward face orders $ACE,CBE,BDE,DAE$. Their equations and tests of the two old <vertices of a polyhedron> not belonging to each face are:
|| New face
|| Interior inequality
|| Tests of the other vertices
| $ACE$
| $x-y-2z-1\le0$
| $f(B)=-2,\ f(D)=-3$
| $CBE$
| $x+y-2z-1\le0$
| $f(A)=-2,\ f(D)=-3$
| $BDE$
| $x+y+z-1\le0$
| $f(A)=-2,\ f(C)=-3$
| $DAE$
| $x-y+z-1\le0$
| $f(B)=-2,\ f(C)=-3$
Each new <plane> contains its three named <vertices of a polyhedron> and has all remaining input <points> strictly on the interior side. Together with the two retained <half-spaces>, these six supporting inequalities describe the final <convex hull>:
$$
\boxed{\begin{gathered}
-2x-y+z-1\le0,\quad -2x+y+z-1\le0,\\
x-y-2z-1\le0,\quad x+y-2z-1\le0,\\
x+y+z-1\le0,\quad x-y+z-1\le0.
\end{gathered}}
$$
Equivalently assemble the closed oriented boundary from $ADC,BCD,ACE,CBE,BDE,DAE$, with adjacent face loops traversing shared edges in opposite directions. It is a triangular <bipyramid> with base <triangle> $CDE$ and apices $A,B$; $CDE$ is internal, so it is not a boundary face. There are five <vertices of a polyhedron>, nine edges and six faces, giving the check $5-9+6=2$. The initial <tetrahedron> similarly has $4-6+4=2$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/geometric-modelling-2015-hull.png]
{title=Initial tetrahedron, the two faces visible from E and their horizon, and the final six-face convex hull}
Back to article page
