Дан набор очков S (x, y, z). Как найти convex hull этих точек?
Я попытался понять алгоритм из здесь, но не смог.
Он говорит:
Сначала спроецируйте все точки на плоскость xy и найдите край, который определенно находится на корпусе, выбрав точку с наивысшей координатой y, а затем выполнив одну итерацию упаковки подарка, чтобы определить другую конечную точку края. Это первая часть незавершенного корпуса. Затем мы итеративно строим корпус. Рассмотрим это первое ребро; Теперь найдите другую точку, чтобы сформировать первую треугольную грань корпуса. Мы делаем это, выбирая точку таким образом, чтобы все остальные точки лежали справа от этого треугольника, если смотреть должным образом (точно так же, как в алгоритме упаковки подарков, в котором мы выбрали такое ребро, что все остальные точки лежали справа от него). этот край). Теперь в корпусе три ребра; чтобы продолжить, мы выбираем одну из них произвольно и снова просматриваем все точки, чтобы найти другую точку, чтобы построить новый треугольник с этим ребром, и повторяем это до тех пор, пока не останется никаких ребер. (Когда мы создаем новую треугольную грань, мы добавляем два ребра в пул; однако мы должны сначала проверить, были ли они уже добавлены к корпусу, и в этом случае мы их игнорируем.) Есть O (n) граней, и каждая итерация занимает O (n) времени, так как мы должны сканировать все оставшиеся точки, давая O (n2).
Может ли кто-нибудь объяснить это более четко или предложить более простой альтернативный подход.
