- 締切済み
最小包含円(補足)
ametsuchiの回答
- ametsuchi
- ベストアンサー率31% (81/257)
seianさん、何度もどうも。なかなか鋭いですね～。 先ず、 １）"Minimum Bounding Sphere"はなるべく小さい方が望ましいが、厳密である必要はない。 ２）計算時間はなるべく短く。 というのが前提ですね。BoundingSphereがRayTracingで好まれているのは、ご存知と思いますが、直線（線分）との交叉検査がBoundingBoxよりも早いからです。これを作る時間はSphereの方が、Boxよりも時間がかかるが、それだけの「投資」をする価値があると言う訳です。 Sphereを作るのに要する計算時間はseljuさんの初めの点同士の総当たりで最大距離を求めるようなｎ^2に比例するような処理でなければ極端な差はなさそうですが、強いて言うと、seianさん案の方が速いでしょう。 更に、出来上がったSphereですが、私の意見では ■どちらも数学的には、最小でない と思います。根拠は、 １）着目２面以外に最大距離となる組み合わせが存在する可能性がある。 ２）「両端面上に複数の点がのっている場合は、各面ともそのうちの任意の1点を選ぶ」と言うことは、当初案（＝BoundingBoxの最大面ペアに内接する球）と同じになってしまう気がします。 しかし、どちらも厳密な最小包含球でないにせよ、統計的にどちらがコンパクト*)かと言うと、今seianさんが示された案だと思います。 従って私の結論は、 ■seianさんの方法を支持します。 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ *)数学でいう「コンパクト」ではなく、日常的な意味です。
関連するQ&A
- 続 最小包含円
たびたびすみません。 まだ、問題が発生しそうなので、もう一度お願いします。 >私も、初期球に関しては、ちょっとおかしいと感じ、 >プログラム上は、旧アルゴリズム（総当たり最長距離）で、今も動かしています。 >実のところ、最適な向き（最小）のBoxの求め方もわからなかったので、そのままにしてしまいました。 >私の場合、まずCAD上で描いて試しているのですが、 >>３ｂ）iー点がこの球に入っていなかったら、このi-点を通り、反対側が元の球を通るように、新球を定める。（容易） >これを繰り返していくと、予定より大きな球になる場合が発生しています。 >元の球に接するように作ると、最初の２点が球の内側に入ってしまうため、１点しか通らない球で定まってしまいます。 >２点球で定まらない場合は、確実に３点球で定まるべきだと思うのですが、何か勘違いしているのでしょうか。
- 締切済み
- 数学・算数
- 最小包含円
空間上に適当に散りばめられた点群を囲む、最小の球（中心と半径）を求めるプログラムを作っています。 用途はＣＡＤですので、数学的な厳密解ではなく、トレランスを与えたあいまいな最適解を求めたいのですが、 もっとも低コストな求め方、エレガントな解法、この分野に強い方、教えて頂けないでしょうか。 今現在は、こんな感じで誤魔化しています。 (1) 最大距離になる２点を直径として、その内側に他の点群がすべてあったらそれを採用。 (2) (1)の外側に点群があったら、(1)の中心点から一番遠い点を使い、 ３点による球で、再び内側に点群がすべてあるか確認。 (3) (2)の球の外側に点群があったら、再び中心から最大距離の１点と、 (2)の３点のうちの、上記の点との最近点とすりかえて、球を定義、再び全点確認。 (4) (3)を繰り返す。 とりあえず稼動確認したところ、それなりに良さそうな球が求まったのですが、いまいち納得できません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 高校数学、立体図形
図1のように 全ての辺の長さが√３＋１の正４角錐OABCDがある。この4角錐の内部で各面と球が接している時、次の問に答えよ。 （１）底面ABCDの対角線の交点をHとするとき、OHの長さを求めよ。 （２）この球の半径を求めよ。 （３）球面上の点からOAまでの最短距離を求めよ。 （問題集の解答） （１） ３角形OAC合同３角形BACより、OH=BH=AB／２＝（√６＋√２）／２ （２） 図１のようにAB、CDの中点をM,Nとし、面OMNを取り出すと、図２のようになる。 ここで、内接球の切り口は三角形OMNの内接円になっている。 角の２等分線の定理より、OI対IH=MO対MH=√３対１より、球の半径は（√６＋√２）／２ ×１／（√３＋１）＝√２／２ （３） 面OAC を取り出すと、図３のようになる。 三角形OIJ∽OAHであり、OI＝（√６＋√２）／２ー√２／２＝√６／２ よって求める距離はIJ-√２／２＝（√３－√２）／２ （疑問） 図2に赤文字で書いていることですが、内接球の接点がどこになるかはどうやってかんがえればよいのでしょうか？ 正4面体の全ての面に内接する球ならば球の中心から各面の接点までの距離が一定という事から考えて各正三角形の重心というのはわかるし、立方体の各面に接する球ならば各正方形の対け苦戦の交点というのはわかりますが、本題の場合に（また、一般の場合に）どう考えればよいのかがわかりません。教えてください。
- ベストアンサー
- 数学・算数
- こんにちは。数学の問題について質問です。
こんにちは。数学の問題について質問です。 １辺の長さが4の正八面体ABCDEFがある。 半径ｒの８個の球が正八面体ABCDEFの外側にあり、隣り合う球は互いに接している。各球は各面と、各面の重心に接している。 ｒを求めなさい。 解説付きで回答おねがいしますｍ（＿＿）ｍ
- ベストアンサー
- 数学・算数
- 正四面体に内接する４個の球の半径の求め方
正四面体に内接する４個の球の半径の求め方 「１辺の長さが６の正四面体ABCDがある。 頂点Aから底面BCDへ引いた垂線の足をHとする。 また、直線BHと辺CDとの交点をMとする。 半径がrの球が４個あり、どの球も他の３個の球と接しており、また、正四面体ABCDはこの４個の球を内部に含み、四面体のどの面も３個の球と接している。 このとき、ｒの値を求めなさい。」 について、同じ質問をしている方がいましたが、『高校への数学』では 対称性を用いて解答していました。 「正四面体の対称面（２頂点A、Dと辺BCの中点を含む面）で考えると、４個の 球のうち２個の中心がその面上に存在し・・・」と解説してました。 ここでわからないのが、なぜその対称面上に２個の球の中心が存在するのか というところです。 クラスの人に聞いても、「対称性から明らか」と言われてそれ以上詳しく聞けません。 この「対称性から」という、何でもかんでもひっくるめた言い方がいつも気持ち悪く感じます。 私が納得したいのは、 ○ こう言う理由で、２個の円の中心が対称面に存在する ○ こう言う理由で、対称性（面対称、点対称、回転対称）というものが言える（いきなり「対称性から・・・」ではなく） です。 面倒くさい質問かもしれませんが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- ２つの球面の交わりの円
２つの球面の交わりの円 ２点（０、０、１）、（２、２、５）を直径の両端とする球面をＳ１、２点（－１、０、３）、（３、４、１）を直径の両端とする球面をＳ２ とし、Ｓ１、Ｓ２の交わりの円Ｃの中心Ｃの座標と半径を求めよ。 教えてほしいところ 自分は中心間の距離はＯ２の半径より短いのでまず、中心は球２の内部にあると考えました。 そして、中心座標の位置関係と内部にあることから球と球の交点座標はＯ1よりすべて左側にあると判断しました。 しかし、間違いらしいです。僕の考え方のどこが間違いなんでしょうか？？ また、Ｏ２とＰＣが垂直であるとなぜいえるんですか？？
- ベストアンサー
- 数学・算数
- ２つの球面の交わりの円
２つの球面の交わりの円 ２点（０、０、１）、（２、２、５）を直径の両端とする球面をＳ１、２点（－１、０、３）、（３、４、１）を直径の両端とする球面をＳ２ とし、Ｓ１、Ｓ２の交わりの円Ｃの中心Ｃの座標と半径を求めよ。 教えてほしいところ 自分は中心間の距離はＯ２の半径より短いのでまず、中心は球２の内部にあると考えました。 そして、中心座標の位置関係と内部にあることから球と球の交点座標はＯ1よりすべて左側にあると判断しました。 しかし、間違いらしいです。僕の考え方のどこが間違いなんでしょうか？？ また、Ｏ２とＰＣが垂直であるとなぜいえるんですか？？
- ベストアンサー
- 数学・算数
- 正四面体の内接球
正四面体の内接球の中心は、外接球の中心でもある。 これが証明できません。どなたかベクトルとか使わない証明をご存知の方、教えてください。 逆の命題、「正四面体の外接球の中心は内接球の中心でもある」は以下のように示すことができると思います。 正四面体をABCD 外接球の中心をＯ Ｏから面ABCに下ろした垂線の「足」をW Ｏから面ABDに下ろした垂線の足をX Ｏから面ACDに下ろした垂線の足をY Ｏから面BCDに下ろした垂線の足をZ 外接球の半径をRとする。 （補題）外接球の中心から各面に下ろした垂線とその面との交点は面の重心である。 外接球であるから、OA=OB=OC=OD=R 面ABCを考える △OWAと△OWBと△OWCで OA=OB=OC （=R 外接球の半径） OW=OW=OW （共通） ∠OWA = ∠OWB = ∠OWC = 90°（垂線だから） 斜辺ともう一つの辺が等しいので △OWA≡△OWB≡△OWC ∴AW=BW=CW Wは正三角形ABCの外心である。 正三角形において、外心と内心と重心は一致するから、Wは重心でもある。 他の3つの面も同様に考えられるから、X,Y,Zはそれぞれ重心となる。 （本題） △OWAと△OYAを考えて、 AW=AY （合同な正三角形の重心と頂点との距離） AO=AO （共通） ∠OWA = ∠OYA = 90°（垂線だから） ∴△OWA≡△OYA ∴OW=OY 同様に、OW=OX=OY=OZ ゆえに、Oは内接球の中心である。 このとき、Oと各面との接点はW,X,Y,Zである。 逆は難しくてどうしてもわかりません。内接円の類推で、内接球の中心が二等分「面」上にあることを使うのだと思うのですが。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 2次関数の最大・最小
2次関数の最大・最小 aが実数として、a<=x<=a+2で定義される関数f(x)=x^2-2x+3がある。この関数の最大値、最小値をそれぞれM(a),m(a)とするとき、関数b=M(a),b=m(a)のグラフをab平面に（別々に）書け。 最大・最小となる候補を利用 y=d(x-p)^2+qのグラフが下に凸の場合、 ・区間α<=x<=βにおける最小値は、x=pが区間内であれば、頂点のｙ座標q そうでなければ、区間の端点でのf(α）,f(β）のうち小さいほう ・区間α<=x<=βにおける最大値は、区間の端点での値f(α）,f(β）のうちの大きいほう である。結局、「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるから、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。 教えてほしいところ 「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるのは理解できます。しかし、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。という部分が理解できません。 何故、たどったものがそれぞれ最大値または最小値のグラフだといえるんですか？？ 論理的に教えてください
- ベストアンサー
- 数学・算数
- 点の動きにより滑らかな曲線を描く
点の動きにより滑らかな曲線を描く 始点から動き始めて自身の軌跡と一回だけ交差したあとで終点とする これにより面を二つの部分に分ける それぞれの領域は 端点二つを含むものと 端点を含まないものに区別することができる このような領域分けを次の三種類の面上で行う 面一：無限平面 面ニ：球面 面三：無限長円筒面 それぞれの面において描ける領域分けのパターンは各何通りか ＊この問題に対する回答は 面一：二種類 面二：一種類 面三：三種類 これであってますでしょうか
- ベストアンサー
- 数学・算数
補足
早速ありがとうございます。 おっしゃる通り、現実問題としては計算コストとの関係で手法は決まると思います。ただ昨日の回答では明らかに最小球でない解が求まってしまう場合があることに気が付いたものですから・・・・。 > １）着目２面以外に最大距離となる組み合わせが存在する可能性がある。 それは当然ではないでしょうか? 必ずしも最大距離である必要はないと思います。 > ２）「両端面上に複数の点がのっている場合は、各面ともそのうちの任意の1点を選ぶ」 > と言うことは、当初案（＝BoundingBoxの最大面ペアに内接する球）と同じになってしまう気がします。 初期球の中心を何処にするかと言うだけの話です。当初案ではBoxの中心だったので上の()内で示した例のような場合、Boxの最長辺を直径とする球で十分な筈のものがこのような配置だとこの両端面上の点が球外と判定され、これらを含めるために更に大きな球となってしまいます。 一般に両端面に複数店が存在する場合にはおっしゃる通り当初案と変わらないと言うことがほとんどでしょうが、これらの点が最長辺の1辺の両端近傍に集中している場合には同じようなことが起こるような気がします。 計算コストを考えれば、ametsuchiさんのが最初にお示しになったBox内接球から始めた方が返って速いかも知れませんね。特に点が球形に近い分布をするのであれば両者の初期球の違いはほとんどなくなってしまいますから・・・。