最小包含円(補足)

質問

質問ではないのですが・・・・。
昨日seljuさんの質問に対して書いたことがちょっと正確でないことに
気が付いたのですが、今朝見たらもう既に締め切られた後でしたので・・・。

http://oshiete1.goo.ne.jp/kotaeru.php3?q=88669

seljuさんの質問(に対するametsuchiさんの回答)に対して、
「初期球としてはこのBoxに内接する球ではなく、このBoxの中心を中心とし、
このBoxの一番長い辺の1/2を半径とする球でいいようにも思えるのですが・・・」
と書いたのですが、場合によってこの方法では最小にならないことに気が付きました。
（例えば、最長辺の両端の面を構成した2点が最長辺のうちの1つの辺の両端点で
他の点はすべてBoxの中心付近にある場合など）
結局、

「Boxの最長辺の両端の面を構成した(つまり両端面上にある)2点を直径とする球を
初期球とする」

に変更すればよいように思えます。この場合たまたま一方もしくは両端面上に複数の
点がのっている場合は、各面ともそのうちの任意の1点を選べばいいでしょう。
私はCADなどやっとことがない方なので、どうも3次元のことを考えるのは
あまり自信が持てませんので、どなたかコメントを頂ければ幸いです。

回答No.3

selju

すみません、問題提示したseljuです。

私も、初期球に関しては、ちょっとおかしいと感じ、
プログラム上は、旧アルゴリズム（総当たり最長距離）で、今も動かしています。
実のところ、最適な向き（最小）のBoxの求め方もわからなかったので、そのままにしてしまいました。

私の場合、まずCAD上で描いて試しているのですが、

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

これを繰り返していくと、予定より大きな球になる場合が発生しています。
元の球に接するように作ると、最初の２点が球の内側に入ってしまうため、１点しか通らない球で定まってしまいます。
２点球で定まらない場合は、確実に３点球で定まるべきだと思うのですが、何か勘違いしているのでしょうか。

すみません、前のを締め切ってしまったので、
もう一度「続 最小包含円」作ります。
よろしくお願いします。

補足

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

上記は、「球の外側に点があった場合、球とその点を含む最小球は球の中心とその外側の点を結んだ直線が球と交わる2点の内、外側の点から遠い方の交点とその外側の点の2点を直径の両端とする球である」ということを書いていると思うので、それでいいと思うのですが・・・。大きくなってしまうと言うのはどうしてでしょう? 確かにこうして求めたものが最小球であるか否かは私にはよく分からないのですが・・・。

所で、3点球というのは何なんでしょう? 3点のを通る円を大円とする球ということですか? 2点球というのは2点を直径の両端とする球ということなのだと思いますが・・・。

新たに質問を作ってていただけるということなので私の方はここで閉めたいと思います。

回答No.2

ametsuchi

すいません、一つ訂正。

BoundingSphereがRayTracingで好まれる理由ですが、

１）交叉検査がBoxより速い。

の他、当然ながら、

２）Boxより小さく、Box検査（またはSphere検査）ではねられる確率が高い。

この１）２）が相俟って、総合的にRayTracingの処理効率を挙げているのです。

お礼

selju さんが新たに質問をおつくりになったようなのでこちらは閉めたいと思います。ありがとうございました。

回答No.1

ametsuchi

seianさん、何度もどうも。なかなか鋭いですね～。

先ず、

１）"Minimum Bounding Sphere"はなるべく小さい方が望ましいが、厳密である必要はない。

２）計算時間はなるべく短く。

というのが前提ですね。BoundingSphereがRayTracingで好まれているのは、ご存知と思いますが、直線（線分）との交叉検査がBoundingBoxよりも早いからです。これを作る時間はSphereの方が、Boxよりも時間がかかるが、それだけの「投資」をする価値があると言う訳です。

Sphereを作るのに要する計算時間はseljuさんの初めの点同士の総当たりで最大距離を求めるようなｎ^2に比例するような処理でなければ極端な差はなさそうですが、強いて言うと、seianさん案の方が速いでしょう。

更に、出来上がったSphereですが、私の意見では

■どちらも数学的には、最小でない

と思います。根拠は、

１）着目２面以外に最大距離となる組み合わせが存在する可能性がある。
２）「両端面上に複数の点がのっている場合は、各面ともそのうちの任意の1点を選ぶ」と言うことは、当初案（＝BoundingBoxの最大面ペアに内接する球）と同じになってしまう気がします。

しかし、どちらも厳密な最小包含球でないにせよ、統計的にどちらがコンパクト*)かと言うと、今seianさんが示された案だと思います。

従って私の結論は、

■seianさんの方法を支持します。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
*)数学でいう「コンパクト」ではなく、日常的な意味です。

補足

早速ありがとうございます。

おっしゃる通り、現実問題としては計算コストとの関係で手法は決まると思います。ただ昨日の回答では明らかに最小球でない解が求まってしまう場合があることに気が付いたものですから・・・・。

> １）着目２面以外に最大距離となる組み合わせが存在する可能性がある。

それは当然ではないでしょうか? 必ずしも最大距離である必要はないと思います。

> ２）「両端面上に複数の点がのっている場合は、各面ともそのうちの任意の1点を選ぶ」
> と言うことは、当初案（＝BoundingBoxの最大面ペアに内接する球）と同じになってしまう気がします。

初期球の中心を何処にするかと言うだけの話です。当初案ではBoxの中心だったので上の()内で示した例のような場合、Boxの最長辺を直径とする球で十分な筈のものがこのような配置だとこの両端面上の点が球外と判定され、これらを含めるために更に大きな球となってしまいます。
一般に両端面に複数店が存在する場合にはおっしゃる通り当初案と変わらないと言うことがほとんどでしょうが、これらの点が最長辺の1辺の両端近傍に集中している場合には同じようなことが起こるような気がします。

計算コストを考えれば、ametsuchiさんのが最初にお示しになったBox内接球から始めた方が返って速いかも知れませんね。特に点が球形に近い分布をするのであれば両者の初期球の違いはほとんどなくなってしまいますから・・・。