3d 表面的凸包算法 z = f(x, y)

我有一个以一组三元组 (x_i, y_i, z_i) 形式给出的 3D 表面，其中 x_i 和 y_i 大致位于网格上，并且每个 (x_i, y_i) 都有一个关联的 z_i 值。典型的网格是20x20

我需要在给定的公差范围内找到哪些点属于曲面的凸包。我正在寻找一种有效的算法来执行计算（我的客户提供了 O(n³) 版本，在 400 点数据集上需要大约 10 秒...）

那里有很多，你没搜过吗？

这是一对 O(n log h) 运行时，其中n是输入点数，h是结果的顶点数：

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

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

以下是四种方法的演示，以及算法的链接：

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