3D面上的凸包算法：z = f(x, y)

Question

我有一个由三元组 (x_i, y_i, z_i) 组成的 3D 表面数据，其中 x_i 和 y_i 大致处于网格上，每个 (x_i, y_i) 对应一个唯一的 z_i 值。典型的网格大小为 20x20。

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

- gurney alex

---

n^3是恶魔：http://en.m.wikipedia.org/wiki/Convex_hull_algorithms - David Heffernan

Answer 1

这里有很多内容，你没有搜索吗？

以下是一些时间复杂度为O(n log h)的算法，其中n是输入点的数量，h是结果顶点的数量：

Chan算法

Kirkpatrick-Seidel算法

这里演示了四种方法，并提供了算法链接：

演示链接

- Tom Zych

---

我进行了一些快速的谷歌搜索，但并不清楚有哪些算法可应用于超过2维。 - gurney alex

Answer 2

O(n^3)版本可能是三维凸壳的Jarvis算法。 看看这篇文章，我认为讲得很清楚：

- Mariy

---

“链接式答案”并不理想，但这个问题很难概括。如果链接失效，请将其粘贴到“wayback”中；我今天检查时已经存档。如果那样不行，请搜索“jason yang convex hull”。 - Tom Zych