= Solution
Use the straightforward <incremental three-dimensional convex hull algorithm>. Assume distinct input <points>, at least four noncoplanar <points>, and general position with no four coplanar. Use exact orientation decisions, or robust predicates that certify the same signs. These assumptions avoid the separate bookkeeping for flat faces, points on the boundary and lower-dimensional initial data.
\Ol[
* Select four <points> forming a nondegenerate <tetrahedron>. Store its four triangular faces with outward <normal vectors> and consistent adjacency.
* For the next <point> $p$, evaluate every current oriented face $f=(a,b,c)$ using
$$
\sigma_f(p)=((b-a)\times(c-a))\cdot(p-a).
$$
The current hull lies in $\sigma_f\le0$. Thus a face is visible from $p$ exactly when $\sigma_f(p)>0$.
* If no face is visible, discard $p$: it lies in the current <convex hull>. Otherwise identify the <horizon of a convex polyhedron> seen from $p$, namely the edges incident with exactly one visible and one retained face.
* Delete the visible faces and cone the ordered <horizon of a convex polyhedron> to $p$, adding one <triangle> per horizon edge. Orient each new face consistently outward and continue with the next <point>.
]
The <determinant> $\sigma_f$ is six times the oriented volume of the <tetrahedron> $abcp$; only its sign matters. A zero value needs a declared degeneracy policy if the general-position assumption is relaxed.
The <data structure> update is a separate local operation. Mark visible faces and walk their adjacency to collect the horizon cycle before deleting anything. Remove edges with two visible incident faces; retain horizon edges and their retained-face links. Insert a <vertex of a polyhedron> record for $p$ and a new edge from $p$ to each horizon <vertex of a polyhedron>. Add one face per horizon edge, connect its other two edges to its neighbours in the cone, and replace the deleted face reference on each horizon edge. Restore the cyclic boundary references and each retained <vertex of a polyhedron>'s incident-edge reference; remove any old <vertices of a polyhedron> left without incident faces.
For an outward visible face with boundary edge $a\to b$ on the horizon, the new outward face can be ordered $(a,b,p)$. Its retained neighbour already traverses that edge as $b\to a$. As an independent orientation check, an interior <point> of the old hull must evaluate negatively against the new face.
The correctness step is geometric: the nonvisible part of a <convex polyhedron> remains supporting, while sight lines from $p$ to the horizon create precisely the new supporting faces. Replacing the visible cap by its cone therefore gives
$$
\boxed{H_{i+1}=\operatorname{conv}(H_i\cup\{p\}).}
$$
Induction from the initial <tetrahedron> yields the <convex hull> of all input <points>.
Back to article page
