最小包含円

質問

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

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

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

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

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

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

回答No.3

ametsuchi · ベストアンサー

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

１）BoundingBoxを作る（＝x,y,z最大最小値）

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

３）全点なめ、
３ａ）iー点がこの球に入っていたらＯＫ。
３ｂ）iー点がこの球に入っていなかったら、このi-点を通り、反対側が元の球を通るように、新球を定める。（容易）

だけで完成です。

参考URL：

http://www.3dspot.com/rtnews/rtnews7b.html

回答No.5

ametsuchi

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

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

お礼

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

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

回答No.4

seian

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

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

回答No.2

ametsuchi

先程の文章、「絞る」で切れてました。要は、計算時間を食わない範囲で、球の半径を「小さくする」ことも考えるべきではないかということです。

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

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

１）BoundingBox作成
２）BoundingBoxに外接する、BoundingSphere作成（これが上限）
３）BoundingBoxに内接する、Sphere作成（これが下限）
４）半径だけでなく、中心も動かして、反復計算させる。（上限・下限で挟み撃ち）

回答No.1

ametsuchi

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

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

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

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

参考URL：

http://www.acm.org/tog/resources/RTNews/html/rtnews8b.html