gur*_*lex 3 algorithm 3d complexity-theory convex-hull
我有给定为一组的三元组的3D表面(X_I,Y_I,z_i),其中X -1和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/Kirkpatrick-Seidel_algorithm
以下是四种方法的演示,其中包含算法链接:
http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html