-PR-
締切り
済み

続 最小包含円

  • 暇なときにでも
  • 質問No.89655
  • 閲覧数508
  • ありがとう数20
  • 気になる数0
  • 回答数14
  • コメント数0

お礼率 35% (7/20)

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

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


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

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

>これを繰り返していくと、予定より大きな球になる場合が発生しています。
>元の球に接するように作ると、最初の2点が球の内側に入ってしまうため、1点しか通らない球で定まってしまいます。
>2点球で定まらない場合は、確実に3点球で定まるべきだと思うのですが、何か勘違いしているのでしょうか。
通報する
  • 回答数14
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全14件)

  • 回答No.5
レベル11

ベストアンサー率 31% (81/257)

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, ...続きを読む
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°以内であるか吟味する必要がある。
お礼コメント
selju

お礼率 35% (7/20)

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

この、角度判別を織り込むとひょっとして、うまく行くような気がしてきました。
ありがとうございます。
投稿日時 - 2001-06-14 16:07:44


  • 回答No.6
レベル8

ベストアンサー率 50% (16/32)

> 4点以上のケースが3Dだとありえるのでしょうか。 正四面体の頂点に点がある場合を考えれば明らかだと思います。 どの3点をとって3点球を作っても他の1点はこの球の中には収まりません。 点群の外側をつないだ多面体をイメージした場合、分かりやすくいえば、 2点球となるのはこの多面体が棒状で両先端が球に接する時、 3点球となるのはこの多面体が円盤状でそのヘリの部分が球に接する時のよう ...続きを読む
> 4点以上のケースが3Dだとありえるのでしょうか。

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

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

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

ベストアンサー率 50% (16/32)

ちょっと整理をしてみました。 最小球を場合分けすると以下のようになると思います。 a. 最遠2点で最小球が定まる。 b. 3点で定まる円を大円とする球が最小球となる。 ただし、最遠2点がこの3点に含まれるとは限らない。 c. 4点で最小球が定まる。 5点以上の点が最小球上に乗ることも考えられますがこれは c のケースで カバーできると思いますので問題ないと思います。 sel ...続きを読む
ちょっと整理をしてみました。
最小球を場合分けすると以下のようになると思います。

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

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

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

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

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

何かいい方法はないんでしょうか??
お礼コメント
selju

お礼率 35% (7/20)

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

プログラムでは、CADの精度上の誤魔化しを入れているので、数学的に本当に永久ループに陥るのかどうか、ちょっとしっくりきていません。
これだ!というやり方ってないのでしょうか。
投稿日時 - 2001-06-14 16:00:32
  • 回答No.3
レベル11

ベストアンサー率 31% (81/257)

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

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

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

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

お礼率 35% (7/20)

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

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

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

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

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

こんな内容を、理解して聞いてくれる方がいることが、
私にとってはとても嬉しく思います。
いつも、孤軍奮闘なもので…。
投稿日時 - 2001-06-14 13:33:51
  • 回答No.1
レベル11

ベストアンサー率 31% (81/257)

私より、seianさんの方が緻密な頭脳なようなので、彼の答に期待することにしましょう。 1)例の参考URLでは既に説明したとおりで、 a)全点をなめてx,y,z方向各々最大最小値を求める。(=BoundingBox) b)「widest dimensional span」即ち、BoundingBoxの3方向で一番大きいスパンに接するような球を初期値とする。中心はBox中心。大多数の点は球 ...続きを読む
私より、seianさんの方が緻密な頭脳なようなので、彼の答に期待することにしましょう。

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

a)全点をなめてx,y,z方向各々最大最小値を求める。(=BoundingBox)

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

c)全ての点に付いて、

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

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

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

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

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

が目的ですよね?

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

お礼率 35% (7/20)

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

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

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

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

教えて頂いた高速処理は、それはそれで非常に参考になりました。
別のところで利用できそうです。
投稿日時 - 2001-06-14 09:51:28
  • 回答No.2
レベル11

ベストアンサー率 31% (81/257)

一寸補足。 seljuさんの方法、よくよく吟味してみると、コストは非常にかかるが、非常に「Tightな」BoundingSphereができるので、なかなかいいと見直しました。 ・3点の内、追加点に一番近い点を置き換える ・3点から球を一意に決める なんてのも、いいセンスしてると思います。 問題はそれだけコストをかける値打ちがあるかどうかです。対象とRay(=半直線)の交叉性を高速 ...続きを読む
一寸補足。

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

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

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

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

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

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

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

・実際に想定されるデータを基に、先ずコストと効果をキチンと調べてみたら如何でしょうか?
  • 回答No.7
レベル8

ベストアンサー率 33% (10/30)

始めまして。 素人ですが次のようなアルゴリズムを考えました。 ------------------------------------ 球の中心pを適当に決める。 移動距離dを適当に決める。 while(!(dが十分小さい)) { while(pが収束、振動していない){点pから最も遠い点の方向に向かって点pを距離d移動させる。} dを小さくする。 } ------------ ...続きを読む
始めまして。
素人ですが次のようなアルゴリズムを考えました。

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

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

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

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

ベストアンサー率 50% (16/32)

> さて本題ですが、どうも先ほどの整理には問題があるようです。 > b の所で()内に書いた条件は逆で、3点球の探索は最遠2点と他の1点で行えばいいような気がします。 > (証明は出来ませんが。) 上記は誤りです。反例が直ぐに見つかってしまいました。 (大体において"()内"ではありませんでしたね。) とすると3点をどのように見つけていけばいい ...続きを読む
> さて本題ですが、どうも先ほどの整理には問題があるようです。
> b の所で()内に書いた条件は逆で、3点球の探索は最遠2点と他の1点で行えばいいような気がします。
> (証明は出来ませんが。)

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

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

ベストアンサー率 33% (10/30)

今晩は、nagataです。結構ウケたみたいで嬉しいです。 いろいろアイデアがうかんだので聞いてください。 まず、収束に関して大きな問題に気づいたんですが平面上に2点(1、0)(ー1、0) があってpが(0、1)にあったとして、このアルゴリズムを走らすとあんまり 良い結果が得られそうにありません。やってみてください。pのy座標は確かに 減って行くのですが、永久に0になれません。これはこのアルゴ ...続きを読む
今晩は、nagataです。結構ウケたみたいで嬉しいです。
いろいろアイデアがうかんだので聞いてください。

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

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

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

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

ベストアンサー率 31% (81/257)

皆さんさん、おはようございます。 ■前置き: 先ず、例によって誤りを訂正。すいません。No.11で「「解析的な解」を求める可能性は=0か」は勿論、「2,3,4点の組み合わせ」で総当たりすれば、可能です。 ■厳密解: seianさんがNo.4で正しく整理してくれたように、 1)2点で決る場合 2)3点で決る場合 3)4点で決る場合 があります。プログラム上は、勿論、 ...続きを読む
皆さんさん、おはようございます。

■前置き:

先ず、例によって誤りを訂正。すいません。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)なら、できるだけ収束し易いエレガントな方法が望ましい。で、何とかならんものかと考えたいのですが、今日一杯は時間が取れず、若い柔軟な頭に先ずは期待しようかなと..。
14件中 1~10件目を表示
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ