たびたびすみません。
まだ、問題が発生しそうなので、もう一度お願いします。

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


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

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

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

A 回答 (14件中1~10件)

nagataさんの方法で心配なのはどの程度真の中心に近づいているのかが保証できるのかということだと思います。


例えば真の中心から s 以内であると判断できるのであれば、その時の仮の中心から一番遠い点との距離を L とすれば、仮の中心からの距離が L-2s から L の間の点について調べればいいだけの話ですので s がある程度小さければその個数はたかが知れており、解析的に解くことは十分可能だと思います。
複数の点が非常に接近して存在し、それらが上記範囲に入ってしまうような場合は扱いが面倒になるかもしれませんが処理は可能だと思います。

nagataさんが心配しておられる2点間で振動するような場合は、振動が確認された時点でこの2点が最小球を構成する最遠2点か否かを判定すればいいのではないでしょうか?
そうであれば終了ですし、そうでなければ、この2点の中心を仮の中心として再出発すればいいと思われます。
    • good
    • 0
この回答へのお礼

遅くなりましたが、皆さんおはようございます。
現実プログラムの修正で、ちょっと返事が遅くなりました。申し訳ございません。

ametsuchiさんが整理してくれたように、
>B)「2,3,4点総当たり」しない効率的な方法で、厳密解が得られないか?
これを探していたのですが、未だうまい方法が見つかっていません。
>C)反復手法、それも絶対収束する方法。
これを利用する方法をこれからちょっと考えてみようと思います。
当初、必ず数点が円上、球上にくるはずだから、この方法は今回はあわないと、勝手に決め込んで試していませんでした。
ある程度、収束処理をして絞り込み、最後は総当たりでトドメ。を試そうかと思います。

ちなみに、実際のプログラムで適用している今現在の処理は、2Dのみ対応に絞って、
(1) 点群から外殻を構成する点のみに絞り込み。
(2) 総当たり処理。
これで、対応しています。点の数が少ないのでまあ良いかなという運用的回避策です。
3D球への対応は、上記のとおり、これから作り込みといったところです。

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

皆さんさん、おはようございます。



■前置き:

先ず、例によって誤りを訂正。すいません。No.11で「「解析的な解」を求める可能性は=0か」は勿論、「2,3,4点の組み合わせ」で総当たりすれば、可能です。

■厳密解:

seianさんがNo.4で正しく整理してくれたように、

1)2点で決る場合
2)3点で決る場合
3)4点で決る場合

があります。プログラム上は、勿論、

4)0点の場合---------------->球は決らない。
5)n点が1点に縮退する場合--->この点を中心とし、半径=0の球

も考慮しないといけません。実は恥ずかしながら、一般に円の場合最大3点、球の場合、最大4点だと思いながら、具体例を想定して、seljuさんの主張する3点で納得してました。

点の数が非常に少なければ、全ての2,3,4点の組み合わせを考えてもいいのでしょう。nagataさん、No.7で折角いいアイデア出したのに、No.12で

「点A、Bが交互に最も遠い点になるとしたら、球の中心は線分ABの中点を通り、線分ABを法線に持つ平面上にあるとか」

というのは、seianさんのNo.4はおろか、前スレッドのseljuさんの元々のアイデアより後退しています。この2点では駄目だから3点法を考えたものの、私やseianさんの指摘するような問題が色々出てきたのです。

■整理:

だから、私なりに整理すると、

A)「2,3,4点総当たり方式」で厳密解を求める方法で、処理効率上問題ないか?
===>多分将来リバースエンジニアリングを考えるとNG?

B)「2,3,4点総当たり」しない効率的な方法で、厳密解が得られないか?
===>seianさんが模索している、もしくはしていた。おそらくseljuさんも。

C)反復手法、それも絶対収束する方法。
===>nagataさんの案もそのうちの一つ。

A)では面白くないし、C)なら、できるだけ収束し易いエレガントな方法が望ましい。で、何とかならんものかと考えたいのですが、今日一杯は時間が取れず、若い柔軟な頭に先ずは期待しようかなと..。
    • good
    • 0

今晩は、nagataです。

結構ウケたみたいで嬉しいです。
いろいろアイデアがうかんだので聞いてください。

まず、収束に関して大きな問題に気づいたんですが平面上に2点(1、0)(ー1、0)
があってpが(0、1)にあったとして、このアルゴリズムを走らすとあんまり
良い結果が得られそうにありません。やってみてください。pのy座標は確かに
減って行くのですが、永久に0になれません。これはこのアルゴリズムの本質的、
かつ致命的な欠点のように思われます。

なのでこのアルゴリズムは捨てて次のようなことを考えています。

最も遠い点に向かって繰り返し中心を動かします。で、
このアルゴリズムを走らすと最も遠い点になる点というのは幾つかの
非常に限られた点だけだと思われます。おそらくこれが最小円を決定する
上でのクリティカルな点であると思われます。
なのでこれらの点になにか強力な解析的手法を適用するというのはどうでしょう。

例えば点A、Bが交互に最も遠い点になるとしたら、球の中心は線分ABの中点を
通り、線分ABを法線に持つ平面上にあるとか、そういうことが言えないでしょうか。
ちと厳密な話は分かりませんが、そんなことを考えています。
    • good
    • 0

「目から1/4うろこ」です。

nagataさん今晩は。シロートなんて謙遜する割に鋭いですね~。これで飯食ってる私は立つ瀬がないな~。

「1/4」にさせてもらったのは、当初(=最初のスレッド)から、挟み撃ちで、
・球の中心(=x,y,z)
・球の半径(=r)
を動かして収束させられるだろう、と判断していたためです。

しかし、

1)Newton法のように次の近似をかなりよくしないと収束が遅い。
2)次ステップのために中心と半径をどう動かしたら最適か?
3)反復法でなく、言わば「解析的な解」を求める可能性は=0か、=0であることは証明できるか?

というところにひっかかっていたからです。0ではなく1/4にしたのは、中心の進む方向を「現在中心から一番遠い点の方向」と明確に提案しているからです。

dをどう決めるか、聞きたいところですね。また、収束に要する反復回数も...。たただ、私みたいにNewton法的なスピードを要求するのは贅沢で、nagataさんの方法が

"Simple is the best"

なのかもしれません。脱帽しました。

それから、seljuさん。90°云々と言いましたが、間違っている気がします。取り消します。
    • good
    • 0

> 移動距離 d は最も遠いものと次に遠いものとの距離の差の1/2にでもしてやれば



またうそを書いてしまいました。どうもすみません。
この2点がたまたま同じような距離の所にあった場合に収束が遅くなってしまいますし、判定を誤ってしまいますね。
結構難しそうですね。
やっぱりnagataさんのおっしゃるように過去の履歴ですかね?
    • good
    • 0

「目からうろこ」です、nagataさん!!


なんだか面倒な方にばかり落ち込んでいってしまっていたようです。

BoundingBoxの中心から始めれば真の位置からそう遠くはないだろうし、移動距離 d は最も遠いものと次に遠いものとの距離の差の1/2にでもしてやれば確実に収束しそうです。
比較の対象もBoundingBoxの内接球(ametsuchiさんが最初に初期球としたもの)の内部は無視してしまってもいいのではないでしょうか?

早く試してみてください、seljuさん!!
    • good
    • 0

> さて本題ですが、どうも先ほどの整理には問題があるようです。


> b の所で()内に書いた条件は逆で、3点球の探索は最遠2点と他の1点で行えばいいような気がします。
> (証明は出来ませんが。)

上記は誤りです。反例が直ぐに見つかってしまいました。
(大体において"()内"ではありませんでしたね。)

とすると3点をどのように見つけていけばいいのでしょう。
多少は枝刈りをするにしてもseljuさんのやり方で行くしかないんでしょうかね?
どうも2次元的手法をそのまま3次元で実行する部分がしっくりこないのですが・・・・。
    • good
    • 0

始めまして。


素人ですが次のようなアルゴリズムを考えました。

------------------------------------
球の中心pを適当に決める。
移動距離dを適当に決める。

while(!(dが十分小さい))
{
while(pが収束、振動していない){点pから最も遠い点の方向に向かって点pを距離d移動させる。}
dを小さくする。
}
------------------------------------

非常に単純で分かりやすいアルゴリズムだと思うんですが、
ひょっとしてseljuさんはもうこのアルゴリズムを試されたことがありますか?
もし実験済であれば、どの程度有効なアルゴリズムだったか評価をお聞かせ願えませんか。
逆に質問してどうするんだと言う気もしますがお願いします。

ちなみに振動、収束の判定はPの移動履歴を5~6個取っておいてそれと現在のpとの距離を
求めることで判定できると思っています。
    • good
    • 0

> 4点以上のケースが3Dだとありえるのでしょうか。



正四面体の頂点に点がある場合を考えれば明らかだと思います。
どの3点をとって3点球を作っても他の1点はこの球の中には収まりません。

点群の外側をつないだ多面体をイメージした場合、分かりやすくいえば、
2点球となるのはこの多面体が棒状で両先端が球に接する時、
3点球となるのはこの多面体が円盤状でそのヘリの部分が球に接する時のような
特殊な場合であって、一般には4点で最小球と接すると考えるのが自然だと思います。

さて本題ですが、どうも先ほどの整理には問題があるようです。
b の所で()内に書いた条件は逆で、3点球の探索は最遠2点と他の1点で行えばいいような気がします。
(証明は出来ませんが。)
一通り探査して最小球が見つからなければ c の段階に移ればいいと思います。
なお、c の4点による探索はこの4点で構成される四面体の内部にこの外接球の中心が
ある場合にのみこの球が最小球の候補となります。
この条件はametsuchiさんが述べておられる平面における条件、
「三角形が鋭角三角形」= 外接円の中心が三角形の内部にある、に相当します。
    • good
    • 0

seljuさんのやり方の問題点を見つけました。

単純化のために2D問題としましょう。

P1(-1, 0)
P2(1, 0)
P3(0.8, 0.8)
P4(-0.01, -0,95)

なる4点を考えます。手順を追うと、

1) この内、最遠距離のペアはP1-P2で、距離=2.0です。これを直径とする円は原点を中心とする半径=1の円。
2) P3はこの円内に入りません。で、P1,P2,P3を通る円を求める。この円の中心は原点より上にズレ、P4はこの円内に入らない。
3) P4はP1に一番近いから、P4,P2,P3を通る円を求める。この円内にP1も入るから処理終了。

しかし、角P4P2P3は>90°であるから冗長な円である。もっと小さい円が存在する。この問題の場合、最小包含円はP1,P3,P4を通る円に他ならない。


この難点を克服するには、三角形の全ての角が:90°以内であるか吟味する必要がある。
    • good
    • 0
この回答へのお礼

げげっ。まさにそのとおり。
これはまずいことです。これは、早速直さなければなりません。(内輪ですが。)

この、角度判別を織り込むとひょっとして、うまく行くような気がしてきました。
ありがとうございます。

お礼日時:2001/06/14 16:07

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

このQ&Aと関連する良く見られている質問

Q4点を通る球の式を求めたい。

4点を通る球の式を求めたいのですが、
ネットなどを調べてもやり方が分からず、悩んでおります。
与えられた4点a,b,c,dから円の中心の座標(A,B,C)が求まれば、そこから半径rも求まり、
(x-A)^2+(y-B)^2+(z-C)^2=r^2
という式が導けると思うのですが。
考えた方法としては、
3点を通る平面の式
3点A:(x1,y1,z1)、B:(x2,y2,z2)、C:(x3,y3,z3)
{(y2-y1)(z3-z1)-(y3-y1)(z2-z1)}(x-x1)+{(z2-z1)(x3-x1)-(z3-z1)(x2-x1)}(y-y1)+{(x2-x1)(y3-y1)-(x3-x1)(y2-y1)}(z-z1)=0
を利用して、
点(a,b,c),(b,c,d),(c,d,a)を通る平面の式を求めて、その3平面が交わる点が球の中心座標。
または、球は中心座標から、与えられた4点までの距離がすべて同じなので、2点間の距離の公式を用いて、
与えられた4点への距離がすべて等しい点を求めることが出来るのではないか。
というのが思いついたのですが、実際にそれを解こうとすると出来ません。
どなたか、方法をご存じの方いらっしゃらないでしょうか?

4点を通る球の式を求めたいのですが、
ネットなどを調べてもやり方が分からず、悩んでおります。
与えられた4点a,b,c,dから円の中心の座標(A,B,C)が求まれば、そこから半径rも求まり、
(x-A)^2+(y-B)^2+(z-C)^2=r^2
という式が導けると思うのですが。
考えた方法としては、
3点を通る平面の式
3点A:(x1,y1,z1)、B:(x2,y2,z2)、C:(x3,y3,z3)
{(y2-y1)(z3-z1)-(y3-y1)(z2-z1)}(x-x1)+{(z2-z1)(x3-x1)-(z3-z1)(x2-x1)}(y-y1)+{(x2-x1)(y3-y1)-(x3-x1)(y2-y1)}(z-z1)=0
を利用して、
点(a,b,c),(b,c,d),(...続きを読む

Aベストアンサー

線分AB, BC, CDのぞれぞれに対して、
「線分の中点を通り、線分に垂直な平面」
を考えて、その3平面の交点が中心
という考え方で求められると思います。

これは、
(x-A)^2+(y-B)^2+(z-C)^2=r^2
に4点の座標を入れた4つの式を作り
  (文字4つ、式4つの連立方程式)
  <それを(1)~(4)式とします>
(1)-(2)式、(2)-(3)式、(3)-(4)式を考えたもの
  <A^2, B^2, C^2の項および文字rは消えるので、
   もはや単なる3元1次方程式です>
と同義です。

もちろんそれは、「2点間の距離の公式を用いて、与えられた4点への距離がすべて等しい点を求める」というのとも同義です。

Q2点を通る直線とある点からの直交点

 2点(x1,y1),(x2,y2)を通る直線と、別のある点(x3,y3)からこの直線に向かって引いた垂線との交点を求める式を教えてください。自分で方程式を解いて求めることも可能ですが、よく使われている簡略化された公式があるのかどうか知りたいと思っています。よろしくお願いします。

Aベストアンサー

>簡略化された公式
何でもかんでも、公式にしてしまっては、覚える方も大変でしょうね。

P1:(x1,y1),P2:(x2,y2)を通る直線と、別のある点P3:(x3,y3)から
この直線に向かって引いた垂線との交点をP:(x,y)とする。

“PのP1に対する相対座標”を“P2のP1に対する相対座標”
で表すと比較的簡潔な表現になることは、想像つきますね。

(1)点Pは線分P1P2上にあるから、
(P1P↑)=α(P1P2↑)[“↑”をベクトルの記号とみて下さい]…(a)

(2)線分PP3と線分P1P2は直交するから、
(P1P2↑)(PP3↑)=0[左の記号を内積とみて下さい]
従って、
(P1P2↑)(P1P↑)=(P1P2↑)(P1P3↑)…(b)

(以下回答)
(a)を(b)に代入して、
α=(P1P2↑)(P1P3↑)/|P1P2↑|^2…(c)
(c)を(a)に代入して、

■(P1P↑)={(P1P2↑)(P1P3↑)/|P1P2↑|^2}(P1P2↑)…答え

右辺は、(x1,y1),(x2,y2),(x3,y3)で記述されている。
この方法で計算ミスをする人は、いないでしょう。

>簡略化された公式
何でもかんでも、公式にしてしまっては、覚える方も大変でしょうね。

P1:(x1,y1),P2:(x2,y2)を通る直線と、別のある点P3:(x3,y3)から
この直線に向かって引いた垂線との交点をP:(x,y)とする。

“PのP1に対する相対座標”を“P2のP1に対する相対座標”
で表すと比較的簡潔な表現になることは、想像つきますね。

(1)点Pは線分P1P2上にあるから、
(P1P↑)=α(P1P2↑)[“↑”をベクトルの記号とみて下さい]…(a)

(2)線分PP3と線分P1P2は直交するから、
(P1P2↑)(PP3↑)=0[左の記号を内積...続きを読む

Q数Ⅲの問題です x>1とする x軸上の点P(a,0)を通るy=x/logxの接線が2本引けるaの範囲

数Ⅲの問題です
x>1とする
x軸上の点P(a,0)を通るy=x/logxの接線が2本引けるaの範囲を定めよ

グラフはかけて、aが1より大きい事は分かったんですが、aが何より小さいのかが分かりません
お願い致しますm(_ _)m

Aベストアンサー

こんな感じでやれると思います。

y=x/logx を微分する。
点(X,X/logX)における接線の方程式を求める。
点(a,0)を通る条件の式をつくる。
a=f(X) という形に整理する。そのとき、わり算できることを示しておくこと。
Y=f(X) と Y=a の交点の問題に置き換える。1つの a の値に対して2つのXが決まるという問題。そのためこのグラフはしっかりかかないといけない。

Q点Pを通り、28cmを2等分する直線の式を教えてください(><)

点Pを通り、28cmを2等分する直線の式を教えてください(><)

Aベストアンサー

その「28cm」とやらは, どこにどのような形で存在するのですか?

Q数学の確率の問題です。 ●赤球2個と白球2個の合計4個の球と袋およびテーブルがあり、はじめは4個の球

数学の確率の問題です。
●赤球2個と白球2個の合計4個の球と袋およびテーブルがあり、はじめは4個の球がすべての袋の中に入っている。以外の「操作」を繰り返す。
「操作」→袋から球を1個取り出し、テーブルの上に置く。その結果、テーブルの上の赤球が2個になったときだけテーブルの上に置いてあるすべての球を袋に戻す。
(1)「操作」を3回繰り返した時点でテーブルの上に球が置かれていない確率を求めよ。
(2)「操作」を4回繰り返した時点でテーブルの上に球が置かれていない確率を求めよ。
(3)「操作」を9回繰り返した時点でテーブルの上に球が置かれていない確率を求めよ。

答えは(1)1/3 (2)19/36 (3)17/81 です。
解き方分かる方いたら教えてくださいm(_ _)m

Aベストアンサー

(1)1,2回目で赤と白が出て3回目が赤の場合です。
  ○:白 ●:赤として
 ①○●●
 ②●○● 

①1/2×2/3×1/2=1/6
②1/2×2/3×1/2=1/6
合わせて1/3。

(2)4回目に最後の赤を引くか,4回連続赤を引く場合。
 ①○○●●
 ②○●○●
 ③●○○●
 ④●●●●
 
 ①1/2×1/3=1/6
 ②1/2×2/3×1/2=1/6
 ③1/2×2/3×1/2=1/6
 ④1/2×1/3×1/2×1/3=1/36
 全部合わせて 19/36

 おっと,①~③は④を除いて(球を袋に戻すこともなく)4回目が赤なので,単純に1/2でいいね。

(3)9回目・・・面倒だな・・・と思ったら・・・
 テーブルの上に球が無いときは,初期から2回目,3回目,4回目の3パターン。
 9回目でテーブルに球が無くなればいいので,2,3,4を組み合わせて合計9になる
 パターンを考えればいい。

 合計9になるパターンは順不同で
 ①2,2,2,3
 ②2,3,4
 ③3,3,3

 ①1/6×1/6×1/6×1/3=1/648
 ②1/6×1/3×1/2=1/36
 ③1/3×1/3×1/3=1/27

 数字の出現順を考えれば
 ①は4通り (3回目でなくなるは出現順で4通り)
 ②は6通り (3!)
 ③は1通り 

 計算すると答えは合います。
 実は,私は②の1/36で引っかかりました。(2)の答え19/36を持ってきてはダメ。
 (2)の④の2個赤,2個赤の連続も含めているので,これは除外しないといけない。

(1)1,2回目で赤と白が出て3回目が赤の場合です。
  ○:白 ●:赤として
 ①○●●
 ②●○● 

①1/2×2/3×1/2=1/6
②1/2×2/3×1/2=1/6
合わせて1/3。

(2)4回目に最後の赤を引くか,4回連続赤を引く場合。
 ①○○●●
 ②○●○●
 ③●○○●
 ④●●●●
 
 ①1/2×1/3=1/6
 ②1/2×2/3×1/2=1/6
 ③1/2×2/3×1/2=1/6
 ④1/2×1/3×1/2×1/3=1/36
 全部合わせて 19/36

 おっと,①~③は④を除いて(球を袋に戻すこともなく)4回目が赤なので,単純に1/2でいいね。

(3)9回目・・・面倒だな・・・と思ったら・・・
 テーブルの上に...続きを読む


人気Q&Aランキング

おすすめ情報