类似于Matlab卷积的Javascript三维凸壳算法

Question

我一直在努力寻找一个用于Javascript的凸壳库，它可以提供与Matlab convhulln函数相同的输出。

我正在将一些代码从Matlab转录到Javascript中，并且我需要找到组成一组顶点的凸包的三角形。Matlab使用convhulln (利用qhull函数)计算一些三维点的凸包。在这种情况下，当我将相同的顶点传递给每个人时，Matlab convhulln会输出一组与quickhull3d不同的三角形面。一些面孔重合，但通常大多数不重合。它们唯一的相似之处是它们都输出相同数量的面(尽管面的实际顶点不相同)。

http://www.mathworks.com/help/matlab/ref/convhulln.html

在Javascript中，我尝试了不同的库，每个库都给出了不同的输出。

在npm中，我尝试过：

quickhull3d - https://github.com/maurizzzio/quickhull3d

convex-hull

delaunay-triangulate

大多数其他算法都是为2D点设计的，所以我已经排除了它们。

如果您有任何想法、建议或反馈，我们将非常感谢！谢谢!

下面是我正在使用的顶点，以及MATlab的convhulln和quickhull3d的结果。请注意，我使用了一种排序算法，从第一个顶点到最后一个顶点对它们进行排序。这应该不会影响实际的三角面，因为我在MATlab和JS代码中对它们进行了完全相同的排序。

这是两个船体的曲线图。

​

​

​

​

注意那些洞。我已经和quickhull3d算法的开发者谈过了(感谢你的回复！！)他提出，他使用的三角测量过程可能与matlab使用的不同。

vertices = [ 
  [ 0.9510565162951535, -0.3090169943749474, 0 ],
  [ 0.5877852522924731, -0.8090169943749475, 0 ],
  [ 6.123233995736766e-17, -1, 0 ],
  [ -0.5591929034707466, 0.8290375725550418, 0 ],
  [ -0.9510565162951535, -0.3090169943749475, 0 ],
  [ -0.9510565162951536, 0.3090169943749473, 0 ],
  [ -0.5877852522924732, 0.8090169943749473, 0 ],
  [ -1.8369701987210297e-16, 1, 0 ],
  [ 0.5877852522924729, 0.8090169943749476, 0 ],
  [ 0.9510565162951535, 0.3090169943749476, 0 ],
  [ 0.984807753012208, 0, -0.17364817766693033 ],
  [ 0.30432233187297814, -0.9366078308002486, -0.17364817766693033 ],
  [ -0.796726208379082, -0.5788554735638644, -0.17364817766693033 ],
  [ -0.7967262083790821, 0.5788554735638641, -0.17364817766693033 ],
  [ 0.3043223318729779, 0.9366078308002487, -0.17364817766693033 ],
  [ 0.5000000000000001, -0.5, 0.7071067811865475 ],
  [ -0.5, -0.5000000000000001, 0.7071067811865475 ],
  [ -0.5000000000000001, 0.5, 0.7071067811865475 ],
  [ 0.4999999999999999, 0.5000000000000001, 0.7071067811865475 ],
  [ 6.123233995736766e-17, 0, 1 ] 
]

来自quickhull3d的三角形: dim = 36x3

    trianglesqh = [ 
  [ 0, 1, 11 ],
  [ 0, 9, 18 ],
  [ 0, 10, 9 ],
  [ 0, 11, 10 ],
  [ 0, 15, 1 ],
  [ 0, 18, 15 ],
  [ 1, 2, 11 ],
  [ 1, 15, 2 ],
  [ 2, 12, 11 ],
  [ 2, 15, 16 ],
  [ 2, 16, 12 ],
  [ 3, 6, 17 ],
  [ 3, 7, 14 ],
  [ 3, 13, 6 ],
  [ 3, 14, 13 ],
  [ 3, 17, 7 ],
  [ 4, 5, 13 ],
  [ 4, 12, 16 ],
  [ 4, 13, 12 ],
  [ 4, 16, 17 ],
  [ 4, 17, 5 ],
  [ 5, 6, 13 ],
  [ 5, 17, 6 ],
  [ 7, 8, 14 ],
  [ 7, 17, 18 ],
  [ 7, 18, 8 ],
  [ 8, 9, 10 ],
  [ 8, 10, 14 ],
  [ 8, 18, 9 ],
  [ 10, 11, 12 ],
  [ 10, 12, 14 ],
  [ 12, 13, 14 ],
  [ 15, 18, 19 ],
  [ 15, 19, 16 ],
  [ 16, 19, 17 ],
  [ 17, 19, 18 ] 
]

来自MATlab的三角形: dim = 36x3

trianglesm = [
  [ 0, 1, 11 ],
  [ 0, 9, 18 ],
  [ 0, 10, 9 ],
  [ 0, 11, 10 ],
  [ 0, 15, 1 ],
  [ 0, 18, 15 ],
  [ 1, 2, 11 ],
  [ 1, 18, 2 ],
  [ 2, 3, 11 ],
  [ 2, 15, 16 ],
  [ 2, 16, 3 ],
  [ 3, 4, 12 ],
  [ 3, 12, 11 ],
  [ 3, 16, 4 ],
  [ 4, 5, 12 ],
  [ 4, 17, 5 ],
  [ 5, 8, 13 ],
  [ 5, 13, 12 ],
  [ 5, 16, 17 ],
  [ 5, 17, 6 ],
  [ 6, 7, 14 ],
  [ 6, 14, 13 ],
  [ 6, 17, 7 ],
  [ 7, 8, 14 ],
  [ 7, 17, 18 ],
  [ 7, 18, 8 ],
  [ 8, 9, 10 ],
  [ 8, 10, 14 ],
  [ 8, 18, 9 ],
  [ 10, 11, 14 ],
  [ 11, 12, 13 ],
  [ 11, 13, 14 ],
  [ 15, 18, 19 ],
  [ 15, 19, 16 ],
  [ 16, 19, 17 ],
  [ 17, 19, 18 ]
]

Answer 1

您可以尝试鲍耶-沃森算法，但使用的是外接球面和四面体：https://en.m.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm。