Выпуклая оболочка конечного множества точек в трёхмерном пространстве — это выпуклый многогранник, вершины которого принадлежат исходному множеству точек. 2

Один из алгоритмов построения выпуклой оболочки называется «завертывание подарка». 4 Он работает, если на вход подаётся множество точек, в котором никакие 4 из них не лежат в одной плоскости. 4 То есть каждые 3 точки задают свою плоскость. 4

Алгоритм включает несколько этапов: 4

1. Инициализация. 4 Необходимо найти грань, с которой начнётся алгоритм. 4 Первую точку выбирают минимальную по оси Z. 4
2. Выбор грани. 4 Выбирают грань, которая будет максимально внешней — именно такая и лежит в выпуклой оболочке. 4
3. Добавление ребра. 4 Ребро добавляют так, чтобы точки в нём находились по часовой стрелке. 4
4. Проверка необходимости добавления рёбер. 4 Проверяют, лежит ли ребро в оболочке, и если лежит, не добавляют. 4
5. Закрытие ребра. 4 После использования ребра его «закрывают», чтобы дальше к нему не прибавить ни одну грань. 4
6. Переход к следующей итерации. 4 Если ребро помечено как «закрытое», то с ним ничего не делают, переходят к следующей итерации. 4

Результатом построения выпуклой оболочки будет многогранник с треугольными гранями. 1