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