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

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

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


algorithm 3d convex-hull complexity-theory
person gurney alex    schedule 24.08.2011    source источник
comment
n^3 дьявольски: en.m.wikipedia.org/wiki/Convex_hull_algorithms   -  person David Heffernan    schedule 24.08.2011

Ответы (2)


arrow_upward
5
arrow_downward

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

Вот пара со временем выполнения 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

person Tom Zych    schedule 24.08.2011
comment
я быстро погуглил, но было непонятно, какие алгоритмы можно применить к › 2d - person gurney alex; 24.08.2011

arrow_upward
2
arrow_downward

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

person Mariy    schedule 24.08.2011
comment
Ответы только по ссылкам не идеальны, но этот ответ будет сложно обобщить. Если ссылка не работает, вставьте ее в wayback; это было заархивировано, когда я проверил сегодня. Если это не поможет, поищите в Google jason yang convex hull. - person Tom Zych; 09.11.2015