我给一组三元的三维表面（x_i，y_i，z_i），其中x_i和y_i大致在一个网格，每个（x_i，y_i）有一个单一的关联z_i值。典型的网格是20×20

I have a 3D surface given as a set of triples (x_i, y_i, z_i), where x_i and y_i are roughly on a grid, and each (x_i, y_i) has a single associated z_i value. The typical grid is 20x20

我需要找到哪个点属于该表面的凸包，一个给定的容差范围内。我在寻找一个有效的算法进行计算（我的客户提供了一个O（n³）版本，这需要〜在400点数据集10秒......）

I need to find which points belong to the convex hull of the surface, within a given tolerance. I'm looking for an efficient algorithm to perform the computation (my customer has provided an O(n³) version, which takes ~10s on a 400 point dataset...)

推荐答案

有不少在那里，没有你搜索？

There's quite a lot out there, didn't you search?

下面是一对夫妇带O（ N 的日志的 ^ h 的）运行时，其中的 N 的输入点数和 ^ h 的是结果的顶点数量：

Here are a couple with O(n log h) runtime, where n is number of input points and h is number of vertices of the result:

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

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

下面是四种方法演示，链接到的算法：

Here is a demonstration of four methods, with links to the algorithms:

http://www.cse.unsw.edu .AU /〜兰伯特/爪哇/ 3D / hull.html