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

Question

我有一个 3D 表面，作为一组三元组 (x_i, y_i, z_i)，其中 x_i 和 y_i 大致在一个网格上，每个 (x_i, y_i) 都有一个关联的 z_i 值。典型的网格是 20x20

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

score 5 · Accepted Answer

里面有很多，你没搜到吗？

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

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

score 2 · Accepted Answer

2

O(n^3) 版本可能是 3d Hull 的 Jarvis 算法。看看这个算法，我觉得描述得很好：

于 2011-08-24T09:27:12.893 回答

2 回答 2