алгоритм выпуклой оболочки для 3d-поверхности z = f (x, y)

Question

У меня есть трехмерная поверхность, заданная в виде набора троек (x_i, y_i, z_i), где x_i и y_i находятся приблизительно на сетке, и каждая (x_i, y_i) имеет одно значение z_i.Типичная сетка 20x20

Мне нужно найти точки, которые принадлежат выпуклой оболочке поверхности, в пределах заданного допуска.Я ищу эффективный алгоритм для выполнения вычислений (мой клиент предоставил версию O (n³), которая занимает ~ 10 с на наборе данных из 400 точек ...)

Answer 1

Там довольно много, вы не искали?

Вот пара с O ( n log h ), где n - количество точек ввода, а h - количество вершин результата:

http://en.wikipedia.org/wiki/Chan%27s_algorithm

http://en.wikipedia.org/wiki/Kirkpatrick-Seidel_algorithm

Вот демонстрация четырех методов со ссылками на алгоритмы:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

Answer 2

Версия O (n ^ 3), вероятно, является алгоритмом Джарвиса для 3d Hull.Посмотрите на этот алгоритм, я думаю, он хорошо описан: