3d 曲面的凸包算法 z = f(x, y) [英] convex hull algorithm for 3d surface z = f(x, y)

问题描述

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

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 log 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/~lambert/java/3d/hull.html

这篇关于3d 曲面的凸包算法 z = f(x, y)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！