Дано дискретное множество точек в пространстве и надо построить выпуклую оболочку этих точек. Результатом построения выпуклой оболочки будет многогранник. В данном алгоритме все грани многогранника будут треугольными:

Polyhedron & convexHull ( CArrRef<Vector3d> point, Polyhedron & poly );

В начале программы строится простейшая трёхмерная фигура - тетраэдр. В качестве первой вершины этого тетраэдра выбирается точка, самая удалённая от центра координат. Вторая вершина - это точка самая удалённая от первой. Третья вершина - это точка самая удалённая от прямой, проходящей через первые две точки. Четвёртая вершина - это точка самая удалённая от плоскости, проходящей через первые три точки. Если входные точки лежат на одной плоскости, то программа останавливается и возвращает пустую модель. Иначе все вершины тетраэдра принадлежат выпуклой оболочке.

Вычисляем центр сферы вписанной в тетраэдр. Далее все точки попавшие внутрь тетраэдра игнорируются, а остальные распределяются по граням тетраэдра, в зависимости от того куда попадёт луч выпущенный из центра вписанной сферы и проходящий через данную точку.
Для каждой грани тетраэдра вычисляется самая удалённая точка из приналежащих ей, и если такая точка есть, то грань ставится в очередь с приоритетом, где приоритетом является расстояние до самой удалённой точки делённое на абсолютное расстояние от плоскости грани до центра вписанной сферы.

Далее в цикле из очереди выбирается грань с максимальным приоритетом. Она делится на три грани при помощи максимально-удалённой точки. Эта точка принадлежит выпуклой оболочке. Осташиеся внешние точки выбранной грани распределяются среди новых граней. В результате этого разбиения в многограннике могут появиться невыпуклости. Они устраняются, рассматривая соседние треугольники и в случае необходимоти перестраивая их. Все изменённые грани выбираются из очереди и, если у них есть внешние точки, то для них вычисляется новый приоритет, и грань ставится в очередь. Выпуклая оболочка будет готова, когда очередь опустеет.

Время работы алгоритма для точек равномерно-распределённых на сфере равно O ( n * log² ( n ) ).

Следующий алгоритм строит выпуклую оболочку многогранника:

Polyhedron & convexHull ( const Polyhedron & inner, Polyhedron & outer );

Следующая функция определеяет - является ли многогранник выпуклым:

bool isConvex ( const Polyhedron & poly );

Описание шаблона классов CArrRef находится здесь.
Описание класса Polyhedron находится здесь, а описание класса Vector3d - здесь.

Исходники находятся в файле func3d.cpp.