Javascript Matlabのconvhullnに似た3次元凸包アルゴリズム

Question

私は、Matlabのconvhulln関数と同じ出力を与えるJavascript用の凸包ライブラリを見つけるのに苦労しています。

私はMatlabからJavascriptにいくつかのコードを転記しています。頂点の集合の凸包を構成する三角形を見つける必要があります。 Matlabは、convhulln（qhull関数を利用する）を使っていくつかの3D点の凸包を計算します。この場合、Matlabのconvhullnは、それぞれに同じ頂点を渡すと、異なる三角形の面をquickhull3dの面に出力します。一部の顔は一致しますが、一般的にはほとんど顔がありません。それらの唯一の類似点は、両方とも同じ数の面を出力することです（面の実際の頂点は同じではありません）。 JavaScriptで

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

、私は別のライブラリを試してみた、それぞれが異なる出力を提供します。..

私が試したNPMから：

quickhull3dからhttps://github.com/maurizzzio/quickhull3d

convex-hull 

delaunay-triangulate 

を

他のほとんどのアルゴリズムは2D点用に設計されているので、私はそれらを除外しました。

ご意見、ご感想、ご意見をいただければ幸いです。ありがとうございました！

私が使っている頂点と、MATLabのconvhullnとquickhull3dの両方の結果です。ソートアルゴリズムを使って最初の頂点から最後まで並べ替えることに注意してください。これは、MATlabとJSコードの両方で正確に同じ方法でソートしたので、実際の三角形の面には影響しません。

ここに2つの船体のプロットがあります。

穴に注目してください。私はquickhull3dアルゴリズム（あなたの応答のおかげで!!）の開発者に話し、彼は彼が使用した三角測量プロセスが1つのMATLABが使用するものとは異なるかもしれないと示唆しています。 quickhull3dから

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 ] 
] 

の三角形：MATLABから 薄暗い= 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 ] 
] 

三角形：あなたが外接し、四面体とボウヤー・ワトソンアルゴリズムが、試みることができる

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

薄暗い= 36x3 ：https://en.m.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm。