For example, the convex hull of three points in
space is the planar triangle that has the three points as its vertices.
The convex hull of a the unit circle in he plane is the unit disk, and
the convex hull of a cube in space is the solid cube.
The algorithm used here to construct
the convex hull here is based on Josef O'Rourkes algorithm.The code is
also based on that which is available on the web.The avilable code was
based on integer arithmetic which was modified to floating point arithmetic.The
datastructures used also had to be added & modified so that relevant
information like normal vectors of the faces were also calculated and presented
in the format accepted by the program
The code starts by finding an initial
building bloclk a minimum simplex of appropriate degree(tetrahedron in
this case).The other vertices are considered sequentially.If a vertex is
found to be inside the initial simplex (found by tetrahedron signed
volume test) the vertex is elliminated otherwise it is marked for addition
into the convexhull.The edges which have both of their adgacent faces visible
from the newly added vertex are marked for deletion.The datastructure is
cleanedup after every addition or deletion.The code also generates the
top view of the convexhull in the postscript format.