続 最小包含円

質問

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

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

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

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

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

回答No.4

seian

ちょっと整理をしてみました。
最小球を場合分けすると以下のようになると思います。

a. 最遠2点で最小球が定まる。

b. 3点で定まる円を大円とする球が最小球となる。
ただし、最遠2点がこの3点に含まれるとは限らない。

c. 4点で最小球が定まる。

5点以上の点が最小球上に乗ることも考えられますがこれは c のケースで
カバーできると思いますので問題ないと思います。
selju さんの方法は a、b には対処できていますが c のケースには対処できていないので遭遇すると永久ループに陥ってしまいます。(3点球というのは b のようなものですよね?）

b のレベルで同じ3点の組合せを2回調べようとした時点で c のレベルのサーチに移る、
ということをすれば原理的には求まるとは思いますが4点の組合せを考えると・・・。
b、c、共に範囲は異なりますが、最遠2点を求めた段階でかなりの部分を枝狩り出来てしまうので、
それを行えば多少はかなり速くなるとは思うのですが現実的な範囲に納まるかどうかは疑問です。

何かいい方法はないんでしょうか??

お礼

す、すごい。確信を突いているような気がします。
３点球と表現したものも、そのとおりです。
とりあえず２Ｄで考えているので、３点円と一緒かなと思っていたのですが、４点以上のケースが３Ｄだとありえるのでしょうか。
２Ｄ，３Ｄで考え方を分ける必要あり？
２Ｄの場合、４点による円は、３点による円でカバーできないもんなんでしょうか。
どうも頭が固くて、CAD使って描かないとわからないもので。

プログラムでは、CADの精度上の誤魔化しを入れているので、数学的に本当に永久ループに陥るのかどうか、ちょっとしっくりきていません。
これだ！というやり方ってないのでしょうか。

回答No.3

ametsuchi

seljuさん、使用目的を勘違いしてました。おハズカシい。大変失礼しました。トレランスとは、CAD用語でいう、ホントの”Tolerance”、たとえば0.1mmとかそういうオーダの世界の話なんですね..。兎に角トンでもない大ボケお詫びいたします。点数など、絶対付けないで下さい。前に頂いたのも返上したい気分です。

目的はCADで、Interactiveに球を定義する、というようなもんなんでしょうか？返事はいりませんが..。

だとすると、点数ｎも大変大きな数を想像していたのですが、数点かも知れないんですね？２D CADの世界では、３点から円、円弧を決めるなんてよくありますが、３D CADで球を定義する場合、中心と半径を与えるのが多いように思ってました。実は自動車など、自由曲面・自由曲線を主体に扱ってきたので、球面（の一部）は殆ど扱ってこなかったのです。

で、「点列から最小包含球」と聞いて、高速化のための処理と早とちりした次第。兎に角お役に立てず申し訳なかったです。

お礼

私の方こそ説明下手で申し訳ございません。
最終目的も先に書いとけば良かったですね。
つい、数学のカテゴリーということで、そっちよりに書いた方が良い回答を得られるかなと思ったもので。

>目的はCADで、Interactiveに球を定義する、というようなもんなんでしょうか？

まさにそのとおりです。3DCADのカスタマイズなのですが、
それこそ中心と半径でしか球を定義できない機能を、もっと使いやすくするのが目的です。
具体的には、ある形状を円柱材料から切り出すとき、
必要最小径の円柱材料がわかれば、コスト削減につながったりします。（この場合の"コスト"はまさに"＄"です。）

実際対象なる形状も、自由曲面を含む部品もあれば、単純な積み木形状、
リバースエンジニアリングの数万点の点群からなる部品をも扱いたいと考えています。

教えて頂いた高速化の処理は、全部品干渉チェックとか、設計意図を織り込む、よりファジーな自動設計プログラムの開発に役立てようと思っています。

こんな内容を、理解して聞いてくれる方がいることが、
私にとってはとても嬉しく思います。
いつも、孤軍奮闘なもので…。

回答No.2

ametsuchi

一寸補足。

seljuさんの方法、よくよく吟味してみると、コストは非常にかかるが、非常に「Tightな」BoundingSphereができるので、なかなかいいと見直しました。

・３点の内、追加点に一番近い点を置き換える
・３点から球を一意に決める

なんてのも、いいセンスしてると思います。

問題はそれだけコストをかける値打ちがあるかどうかです。対象とRay（＝半直線）の交叉性を高速に検出する必要のある、RayTracingなら、私が示した方法より、いいかもしれない。RayTracingでは、画素数分のRayだけでなく、反射、屈折に伴い、Rayが分岐していく。

「Motion Blur」や「Delth of Field」などの「Distributed Raytracing」では計算時間が更に何10倍以上も時間がかかります。だから、この場合、ある程度コストをかけてもBoundingSphereは小さければ小さいほどいいかも知れません。

ただ、最大距離２点を探すのに1/2*n^2回計算するのは何とかなりませんか？BoundingBoxと、seianさんが言われたような方法で、かなりそれに近い２点を求めることができると思います。

しかし、普通のCADシステムでそこまでやる必要があるか否か疑問です。

・実際に想定されるデータを基に、先ずコストと効果をキチンと調べてみたら如何でしょうか？

回答No.1

ametsuchi

私より、seianさんの方が緻密な頭脳なようなので、彼の答に期待することにしましょう。

１）例の参考URLでは既に説明したとおりで、

ａ）全点をなめてx,y,z方向各々最大最小値を求める。（＝BoundingBox）

ｂ）「widest dimensional span」即ち、BoundingBoxの３方向で一番大きいスパンに接するような球を初期値とする。中心はBox中心。大多数の点は球内に入る。このロジックはseianさん方式がいいかもしれない。

ｃ）全ての点に付いて、

ｃ１）球内ならこれを無視。
ｃ２）球外の点について、この点と旧球の中心をとおりこの点と反対側は旧球に接するように新球を定める。

ですよね。これは勿論、おっしゃるように「元の球に接するように作ると、最初の２点が球の内側に入ってしまうため、１点しか通らない球で定まってしま」います。勘違いではないです。逆に質問ですが、

質問１）３点球ですが、元の球より小さくなるところがあり、ここで、元は入っていたのに、新球からはみ出てしまう点が出てくる可能性がありますね？永久ループするかどうか分からないけど、条件次第で、永久ループまたはそれに近いことになりませんか？永久ループしない自信がありますか？

質問２）最小包含球の目的自体、数学的な厳密解を要求している訳じゃないですよね？ｑ=88669ではそう書いてありました。ならば、

・なるべく小さい半径だが、確実に全点を包含する球を高速で求めること。

が目的ですよね？

■恐らく球半径の大きさという観点からは、seljuさん方式の方がベターでしょう。
■問題は処理効率です。
・初めに最大距離の点ペアを求めるには「n^2」回の計算が必要です。
・その後の処理の処理ループ（＝while Loop?）も何回回るか分からない。下手すると永久ループかそれに近い可能性もある。
・各ループの中で、また、ｎに比例する処理が必要。私や、seianさんが示した方法なら、確実に、ｎに比例した処理で終わりです。

お礼

回答ありがとうございます。
ametsuchiさんの言われるとおり、私自身が作ったものは、
永久ループになる場合があります。いえ、ありました。
実際の処理では、ループ化を検知した時点で終了、もしくは、適当回数回った時点で終了してました。
「時間がかかるわりに、全点が入る球が求まらないまま終わる」、これが発生することが最大の問題でした。
今現在は、教えて頂いた処理が保険で動くので、結果がでないということはなくなりました。

使用目的が、反復処理ではなく、CAD上で円もしくは、球そのものの位置、大きさを求めることなので、人の見た目で違っていると判断できるレベルの誤差は避けたいと思っております。

実際のCAD上で４点描いて、試してみると、想像以上に誤差が出ていることがわかりました。（特に半径ではなく中心位置のずれ）
人の見た目の判断基準はあいまいなので、
どのくらいの結果が理想的かといわれると、ちょっと難しいのですが、
オペレーター曰く、
・半径誤差は０．１ｍｍ程度。（１００ｍｍR球に対して）
・誤差が発生する場合は、その誤差の程度が知りたい。
・簡単形状に誤差が発生するのは許せない。

あいまいさに条件を付けた、ちょっと製造業の泥臭い仕様との板挟みになっております。
すみません、「厳密解を得たいが、CAD的な誤差は許す。」
「厳密解がだせればベスト、だめなら最適解で我慢するよ。」って感じでしょうか。
どちらかというと、上記のような結果重視で、高速化は、ついでにお願い。くらいの要件です。

教えて頂いた高速処理は、それはそれで非常に参考になりました。
別のところで利用できそうです。