問題タブ [polyhedra]

3Dの凸多角形があります。簡単にするために、頂点のある正方形とし(0,0,0),(1,1,0),(1,1,1),(0,0,1).ます。これらの頂点を反時計回りに配置する必要があります。私はここで解決策を見つけました。ポリゴンの中心の角度を決定し、それらを並べ替えることをお勧めします。それがどのように機能するのかはわかりません。誰かが解決策を持っていますか？堅牢で、頂点が非常に接近したときにも機能するソリューションが必要です。

サンプルのMATLABコードをいただければ幸いです。

ランダムな多角形の面積とランダムな多面体の体積を計算したい。Google で検索した結果、テッセレーションとモンテカルロ法にたどり着きました。ただし、収束による近似ではなく、正確な計算にのみ関心があります。誰かが正確な式を暗記している、またはそのような式が記述されているページへのリンクを持っているでしょうか?

特殊な多角形または多面体に適用するために数式は必要ありません。それらが単純な（交差しないエッジ）凸形状に適用される場合、私はすでに満足しています。頂点座標のリスト以外には何も使用したくありません。特定の順序で配置することもできます[(x1, y1), ..., (xn, yn)]。[(x1, y1, z1), ..., (xn, yn, zn)]

Fortran、C/C++、Pythonおよびを読むことができますMATLAB。したがって、これらの言語のいずれかで記述された、または疑似コードで記述されたアルゴリズムは、好評を博しています。

このコードを実行して 3D メッシュ出力を表示しようとしましたが、奇妙な理由で、nf と頂点数の出力が表示されますが、その後セグメンテーション エラーが発生します。Moar の出力行は std に書き込まれません。理由はありますか？

譲渡可能効用特性関数ゲーム (協力ゲーム理論) で最も有名な解の概念は、どの連合によっても改善できない実行可能なペイオフ配分のセットとして定義されるゲームのコアです。幾何学的には、コアは閉じた凸多面体です: http://www.jstor.org/stable/2630190

これらのゲームでは、ペイオフの割り当てはコアにあるか、コアにないかのいずれかです。TUGlab の一連のツールには、ペイオフの割り当てがコアにあるかどうかを計算できるコマンドが あります: http://webs.uvigo.es/mmiras/TUGlab/特定のペイオフ配分の距離はコアまでです。閉じた凸多面体としてコアの幾何学的特徴付けがある場合、点とその多面体の間の幾何学的距離を特性関数の「コアからの距離」として計算する方法があるはずです。残念ながら、MATLAB で実装できるこの距離を計算するための式またはアルゴリズムを実際に示している論文は見つかりませんでした。

私の推測では、2 つの多面体間の距離を計算する Stephen Cameron のコードに手がかりがあるかもしれません。しかし、私の問題はそれよりも単純なはずです。点と多面体の間の距離だけです。最後に、a) 特性関数、b) ペイオフ分布を入力として取り、ペイオフ分布と特性関数のコアとの間の距離を出力として与える MATLAB プログラムが必要です。もちろん、コアが空でないと仮定します。

n 個の3 次元オブジェクト (多面体) があるとします。すべてのオブジェクトの交差を計算する最速の方法は O(n ^ 2) ですか?

現在、基本的に T(n) を n ^ 2 に等しくするライブラリを使用しています。

これは文字通り n ^ 2 ステップかかります。

私が考えることができる唯一の高速な方法は、依然として O(n ^ 2) ですが、T(n) = n(n+1) / 2、または (n*n + n) / 2 です。

擬似コードは次のとおりです。

この方法では、2 つのオブジェクトが 2 回交差するかどうかを確認する必要がありません。反復処理中のリストには約 3000 個のオブジェクトがあることがわかっています。このアルゴリズムは 4501500 ステップかかりますが、元のアルゴリズムはそのほぼ倍の 9000000 ステップかかります。

何か不足していますか？これは私たちが得ることができる最高のものですか？