2

3D d_1, ..., d_nの一連の単位方向が与えられた場合、

それらの周りで最もタイトなコーンを見つける方法は?

たとえば、次のような別の単位ベクトルmと、角度を表すスカラー値alphaを見つけるにはどうすればよいですか。

foreach i, AngleBetween( m , d_i ) <アルファ

そしてアルファは最小です。

注が追加されました: 方向は半分以上のスペースにまたがることができます。このような「円錐」の場合、円錐の頂点から始まり、円錐の軸から所定の角度内にある半直線のセットを意味します。

4

2 に答える 2

1

一連の方向がすべて原点を通る 1 つの半空間内に収まる場合、単位半径球のベクトル ヒントの凸包を計算すると、その球に凸多角形が生成され、その多角形に外接する最小の円を見つけることができます。 . 適切な平面に射影することにより、球面計算を回避できます。

これは抽象的な見方であり、おそらくもっと具体的なアドバイスが必要だと思いますが、それでも役立つかもしれません: 凸包 + 最小外接円。

一連の方向が半空間を超える場合、この状況での「円錐」の意味を定義する必要があります。

于 2013-01-03T14:19:41.700 に答える
0

これは線形計画問題です。


px*d1x+py*d1y*pz*d1z >= cos(a)
px*d2x+py*d2y*pz*d2z >= cos(a)
...
pxを条件として、cos(a) を最大化する a, p を見つけます。 *dnx+py*dny*pz*dnz >= cos(a)

私はLPアルゴリズムを調べます。その間、私は出発点となる可能性のある非常によく似た問題を解決しました: https://github.com/VictorDavis/GeoConvexHull。おっしゃるとおり、凸包を見つけたら、最小の外接円を見つけることができます。ただし、n 点が同じ半球にあることを証明することは自明ではありません。おそらく、このアルゴリズムを調整して、「最小の円錐」の問題に答えることができます。

于 2014-08-29T18:34:45.647 に答える