アプリ版:「スタンプのみでお礼する」機能のリリースについて

空間上に適当に散りばめられた点群を囲む、最小の球(中心と半径)を求めるプログラムを作っています。
用途はCADですので、数学的な厳密解ではなく、トレランスを与えたあいまいな最適解を求めたいのですが、
もっとも低コストな求め方、エレガントな解法、この分野に強い方、教えて頂けないでしょうか。

今現在は、こんな感じで誤魔化しています。
(1) 最大距離になる2点を直径として、その内側に他の点群がすべてあったらそれを採用。

(2) (1)の外側に点群があったら、(1)の中心点から一番遠い点を使い、
3点による球で、再び内側に点群がすべてあるか確認。

(3) (2)の球の外側に点群があったら、再び中心から最大距離の1点と、
(2)の3点のうちの、上記の点との最近点とすりかえて、球を定義、再び全点確認。

(4) (3)を繰り返す。

とりあえず稼動確認したところ、それなりに良さそうな球が求まったのですが、いまいち納得できません。
よろしくお願いします。

A 回答 (5件)

3度目です。

以下のSiteをご覧下さい。非常にシンプルで効果的なアルゴリムです。私の案は撤回します。

1)BoundingBoxを作る(=x,y,z最大最小値)

2)BoundingBoxに内接する球を求め、これを初期球とする。

3)全点なめ、
3a)iー点がこの球に入っていたらOK。
3b)iー点がこの球に入っていなかったら、このi-点を通り、反対側が元の球を通るように、新球を定める。(容易)

だけで完成です。

参考URL:http://www.3dspot.com/rtnews/rtnews7b.html
    • good
    • 0

seianさんの指摘される通り、「Boxの一番長い辺の1/2を半径とする球でいい」です。

失礼しました。

書いた後、コンビニで買い物している最中に「内接」という表現が数学的に正確でないことに気が付いたのですが、「まあ、分かってくれるだろう」と妥協してしまいました。
    • good
    • 1
この回答へのお礼

返事おそくなって申し訳ございません。
ametsuchiさん、seianさん、早速の回答ありがとうございます。
おかげさまで、誤魔化していた部分が、ようやく確かな答えとして結果がでるようになりました。
CADを経験されている方のアドバイスがあると、非常に助かります。
まだ幾つか誤魔化してCADをカスタマイズした部分があるので、また、よろしくお願いします。

ありがとうございました。

お礼日時:2001/06/13 08:49

ametsuchiさん > 2)BoundingBoxに内接する球を求め、これを初期球とする。



細かいようですがBoundingBoxは一般には直方体になるわけで、
初期球としてはこのBoxに内接する球ではなく、このBoxの中心を中心とし、
このBoxの一番長い辺の1/2を半径とする球でいいようにも思えるのですが
如何なものでしょう。
    • good
    • 0

先程の文章、「絞る」で切れてました。

要は、計算時間を食わない範囲で、球の半径を「小さくする」ことも考えるべきではないかということです。

私も職業としてCADには20年程関わっていますが、生憎BoundingBoxしか使っていません。CGの世界では計算時間のかかるRayTracingで、No.1のような「BoundingSphere」が提案され、高速化に寄与しています。

下記のアルゴリズムを追うのがメンドイので、下記アルゴリズムとは別に自分なりの方針を掲げると、

1)BoundingBox作成
2)BoundingBoxに外接する、BoundingSphere作成(これが上限)
3)BoundingBoxに内接する、Sphere作成(これが下限)
4)半径だけでなく、中心も動かして、反復計算させる。(上限・下限で挟み撃ち)
    • good
    • 0

大変失礼ですが、あまりエレガントな解法とは思えません。

なぜなら、

1)「最大距離になる2点」を探すというのは、1/2*n^2回に比例する比較が必要。

2)最小の球とは限らないのではないか。常に大きくしているだけ。「絞る」

下記にBoundingSphereに関するアルゴリズムがあります。中は見てません。

参考URL:http://www.acm.org/tog/resources/RTNews/html/rtn …
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!