6. Построение выпуклой оболочки в трехмерном пространстве.

Построение выпуклой оболочки в трехмерном пространстве(Р^3).

Алгоритм заворачивания подарка:

• ставим подарок на одну точку;

• опускаем его на три точки, закрепляем бумагу на этих точках;

• поворачиваем подарок, получаем новую плоскость, проходящую через две уже известные точки и одну новую.

• повторяем третий пункт до полного оборачивания.

Алгоритм построения выпуклой оболочки

Найдем точку с минимальной координатой Y, если их несколько, то из найденных выберем точку с минимальной координатой X, затем Z.(эта точка "a" точно вершина выпуклой оболочки). Время O(n).

Найдем ребро: спроецируем всю сцену на плоскость XY, по алгоритму для Р^2 найдем следующую точку "b". Соединим отрезком точки "a" и "b"(в реальных координатах, а не на проекции).

Следствие: существует плоскость, которая содержит этот отрезок, и все остальные точки лежат по одну сторону от этой плоскости (плоскость перпендикулярна плоскости XY). Время O(n).

Найдем треугольник основания: спроецируем все точки на плоскость перпендикулярную найденному ребру "ab". Само ребро выродится в точку. По алгоритму для Р^2 найдем следующую точку "с". Соединим отрезками точки "a" и "с", "b" и "с" (в реальных координатах, а не на проекции), получим треугольник. Время O(n).

Далее для каждого нового ребра повторяем построение треугольника (время O(n^2) – обрабатываем n точек для каждого из n треугольников.): организуем множество ребер, которые еще не были рассмотрены. Изначально это множество содержит три ребра треугольника abc. При рассмотрении какого-либо ребра вынимаем его из множества, находим новую точку и два соответствующих новых ребра. Каждое из двух новых ребер ищем во множестве. Если его там нет, то добавляем ребро к множеству [отрезки во множестве упорядочим по номеру точек начала и конца ребра => время вставки во множество O(logn)], если есть – вынимаем имеющееся. Так до тех пор, пока множество не окажется пустым, что будет признаком окончания процесса построения выпуклой оболочки. Множество обрабатывается O(n) раз.

Общее время решения задачи - O(n^2), как и в плоском случае.