3

20 面体を分割して球体の近似を作成するアプリケーションがあります。デカルト頂点座標は球座標に変換されるため、すべての頂点が単位球の表面上に配置されます。

次に行う必要があるのは、球面上の任意の点に最も近い頂点を見つけることです。私は2つの単純なアルゴリズムを思いつきました...

  1. ブルート フォース検索 - 頂点の数が少ない場合は問題ありませんが、細かい分割では過剰になります。

  2. ソート済み/インデックス付き検索 - 頂点を方位角と傾斜角によって何らかの順序でソートし、大まかなインデックスを作成して、その範囲を制限することでブルート フォース検索を高速化します。

上記の 2 つのうちの 1 つの代わりに使用できる、より巧妙で、できればより高性能なアルゴリズムがあるかどうか疑問に思っていました。

更新 1:アプリケーションの別の部分で、頂点が隣接する頂点に関する情報を格納していることを思い出しました。私の新しいアルゴリズムは

  1. 任意の開始頂点をピックします。位置を特定する点までの距離が小さい隣接点を見つけます。この近傍を新しい開始頂点として使用します。頂点までの距離がそれより短い頂点の近傍がなくなるまで繰り返します。この頂点は、ポイントに最も近いです。
4

3 に答える 3

2

回答をスキャンすると、私はベースから外れている可能性があると思いますが、あなたが求めていることは簡単です. おもう。

球上にある点だけを扱っているので、頂点から球の中心に線をドロップし、任意の点から中心に別の線をドロップして、それらの間に作成された角度を解くことができます。小さいほどよい。私が考える最も簡単で安価な方法は、内積です。角度は基本的に外れます。これに関するリンクは次のとおりです。 http://www.kynd.info/library/mathandphysics/dotProduct_01/ それらをテストするには、頂点を選択してテストし、次にその隣接をテストすることをお勧めします。それは常に最小の隣人の方向であるべきです（あなたが求めている頂点に近づくにつれて、角度は常に減少するべきです）

とにかく、それがあなたの求めているものであることを願っています。ああ、あなたの細分割アルゴリズムを探しているときにこのページに出くわしました。見つけにくい; リンクを投稿していただければ、私だけでなくもっと役立つと思います。

于 2013-01-29T04:17:23.600 に答える
1

考えられる解決策の 1 つは、頂点の BSP ツリーを構築することです: http://en.wikipedia.org/wiki/Binary_space_partitioning

于 2012-08-14T07:44:36.423 に答える
0

二十面体が北極に 1 つの頂点を持ち、南極に反対側の頂点を持つ場合、赤道に平行な平面にある 5 つの頂点のそれぞれに 2 つのグループがあります。ちょっとした幾何学で、これらの平面は N/S 57.3056° (dd.mmss ではなく 10 進数) にあることが分かります。これにより、正二十面体が 4 つの緯度ゾーンに分割されます。

  • 28.6528° の北 (南) は、より近い極の頂点に最も近くなります。
  • 赤道と北 (南) 28.6528° の間は、そのゾーンの 5 つの頂点の 1 つに近いです。

私はこれをナビゲーターのように作業しています。弧は度で測定され、北と南を示します。より数学的な規則を好む場合は、これらすべてを球座標のバージョンに簡単に変換できます。

コーディングはしていませんが、5 つの頂点までの距離を確認して最も近いものを選択する方が、球面を正 20 面体の面の投影に分割したり、球上の点を二十面体に戻し、その座標系で問題を処理します。

たとえば、更新 1 で提案するアプローチでは、少なくとも 6 つの頂点 (最初に任意に選択された頂点とその 5 つの隣接点) までの距離を計算する必要があります。

距離をデカルト座標で計算するか球座標で計算するかは問題ではありません (どの頂点が最も近いかだけを知りたい場合)。ただし、デカルト座標での計算では、三角関数の多くの呼び出しが回避されます。

一方、球の極に頂点を持つ 20 面体を配置していない場合は、そうする必要があります。

于 2012-08-14T09:45:04.010 に答える