質問ではないのですが・・・・。
昨日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次元のことを考えるのは
あまり自信が持てませんので、どなたかコメントを頂ければ幸いです。

A 回答 (3件)

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



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


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

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

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

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

この回答への補足

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

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

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

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

補足日時:2001/06/13 15:22
    • good
    • 0

すいません、一つ訂正。



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

1)交叉検査がBoxより速い。

の他、当然ながら、

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

この1)2)が相俟って、総合的にRayTracingの処理効率を挙げているのです。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/06/13 15:27

seianさん、何度もどうも。

なかなか鋭いですね~。

先ず、

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

2)計算時間はなるべく短く。

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

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

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

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

と思います。根拠は、

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

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

従って私の結論は、

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

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

この回答への補足

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

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

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

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

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

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

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

補足日時:2001/06/13 14:09
    • good
    • 0

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

今、見られている記事はコレ!

  • 数学は日常生活に役立っているのか?専門家に聞いてみた

    3月14日は、1997年に財団法人日本数学検定協会が制定した数学の日である。あなたは学生の頃、数学は得意だっただろうか? 筆者のように得意ではなかった人なら、「将来、これが何の役に立つのだろう……」と四苦八苦...

  • この問題解けますか?「1・1・5・8」を使って10を作るパズル

    テンパズルというのをご存知でしょうか。この名前は知らなくともやったことのある方も多いと思いますが、どういうものかと言いますと、4つのひと桁の数字を足したり引いたり掛けたり割ったりして10にする、というも...

  • 数学は実生活で役立つのか

    学校で学んだ事柄が後々の仕事に役立ったなどという話は、よくあるケースですが、学んでいる最中はなかなか気づかないものです。子どもから「数学ってなんの役に立つの?」と聞かれて、数学が苦手だった親はどう答え...

  • 無駄に覚えている数字ってどのくらいあります?

    覚えたくても覚えられない数字がある一方で、なんとはなしに記憶した数字がずっと頭に残っているケースもあります。くっきりと覚えてはいるものの「多分、これ一生使わないんだろうな…」と思っている数字、今日はそ...

  • あなたも挑戦!?バカ田大学入試

    大人気ドラマ「ガリレオ」、観ている方も多いのではないでしょうか。学生時代に数学が苦手で、もう数式なんて見たくない!と思っていても、さらさらと難解な数式を操る湯川先生(福山雅治さん)の姿を見るとかっこい...

おしトピ編集部からのゆる~い質問を出題中

お題をもっとみる

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ