10

私は錐台（角錐台）を持っており、この錐台の境界球をできるだけ小さく計算する必要があります。錐台の真ん中に中心を選択し、半径を「遠い」角の1つまでの距離にすることができますが、通常、錐台の狭い端の周りにかなりのたるみが残ります。

これは単純なジオメトリのように見えますが、私には理解できないようです。何か案は？

4

8 に答える 8

5

これはおそらくあなたが探している答えではありませんが、錐台のすべての頂点を計算し、それらをミニボールの実装のような一般的な最小境界球アルゴリズムにプラグインすることができます.

于 2010-02-03T19:43:26.547 に答える
5

もちろん、 http://www.cgafaq.info/wiki/Minimal_enclosing_sphereがあります(Google 経由)。

2つの可能性があると思います。1 つ (錐台が非常に平らな場合) は、底面の反対側の点が球上の反対側の点になることです。もう 1 つの方法 (錐台が非常に高い場合) は、錐台の反対側の点が球体上にあり、これらの 4 つの点 (ベース上の 1 つの点、ベース上の最初の点の反対側の点、 1 つは上の正方形の最初の反対側、もう 1 つは上の正方形の最初の隣接するもの)。

最初の球体を見つけます。錐台がそれに収まる場合、それがあなたの答えです。それ以外の場合は、2 番目の球体が答えになります。

于 2010-02-03T20:02:28.943 に答える
4

この問題には、いくつかのアルゴリズムと実装があります (この投稿も参照してください)。

  • 2D と 3D については、Gärtner の実装がおそらく最速です。

  • 高次元 (最大 10,000 など)については、Gärtner、Kutz、および Fischer によるアルゴリズムの実装であるhttps://github.com/hbf/miniballを参照してください (注: 私は共同研究者の 1 人です)。 -著者)。

  • 非常に高い次元の場合、コアセット(近似) アルゴリズムの方が高速です。

特定のアプリケーションでは、最初の 2 つのアルゴリズムのいずれかを試すことができます。どちらもO(n)非常に小さな定数で実行され、数値的に安定しています。

于 2013-02-20T12:04:07.387 に答える
2

これを行う方法は、錐台の 4 点に適合する球を見つけることです。これが適切な錐台である場合 (切頭ピラミッド - 私の悪い私は円筒形の錐台を想定していました)、上部のクワッドの反対側のコーナーから 2 つのポイントを取得し、下部のクワッドから他の 2 つのポイントを取得し、上部の 2 つと位相がずれています。 . 次に、これを使用して球体を取得します。

于 2010-02-03T19:45:08.730 に答える
0

同一平面上にない 4 つの点の任意のセットが球を定義します。錐台に 4 辺のピラミッドを使用していると仮定すると、70 の可能な 4 つのポイントのセットがあります。70 個すべての球体を試して、どれが最小かを確認してください。

錐台にはおそらくいくつかの対称性があるため、反対側の角にある 4 つの点を選択して、台座のソリューションを使用できます。

于 2010-02-03T19:46:24.247 に答える
0

厳密に言えば (これによると)錐台の底面は任意の多角形にすることができ、また厳密に言えば、その多角形は凸面である必要さえありません。とはいえ、問題の一般的な解決策を得るには、上記で提案したように (ほぼ) すべての頂点を使用する必要があると思います。ただし、(上で示唆したように) いくつかの球体の比較のみを必要とするソリューションの特殊なケースがあるかもしれません。上記の Anthony によるリンクが気に入っています。Megiddo は、O(n) (!) 時間で解が得られると彼が主張する変換を提供します。悪くない ！

于 2010-02-03T22:50:47.550 に答える
0

錐台の中心を下る「垂直」線上で、錐台の下部と上部のエッジまでの距離が同じである点を見つける必要があります (対称であると仮定します)。

下の点が Xb、Yb、Zb、上の点が Xt、Yt、Zt で、直線が点 Xp、Yp、Zp にベクトル Ax、By、Cz を加えたものになるように解いてください。

だから方程式を解いて

sqrt( (Xb - (Xp + VAx) )^2 + (Yb - (Yp + VBy))^2 + (Zb - (Zp + VCy))^2) = 
sqrt( (Xt - (Xp + VAx) )^2 + (Yt - (Yp + VBy))^2 + (Zt - (Zp + VCy))^2).

そこにある唯一の変数はスカラー V です。

于 2010-02-03T19:56:26.490 に答える