-PR-
解決済み

最小包含円

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

お礼率 35% (7/20)

空間上に適当に散りばめられた点群を囲む、最小の球(中心と半径)を求めるプログラムを作っています。
用途はCADですので、数学的な厳密解ではなく、トレランスを与えたあいまいな最適解を求めたいのですが、
もっとも低コストな求め方、エレガントな解法、この分野に強い方、教えて頂けないでしょうか。

今現在は、こんな感じで誤魔化しています。
(1) 最大距離になる2点を直径として、その内側に他の点群がすべてあったらそれを採用。

(2) (1)の外側に点群があったら、(1)の中心点から一番遠い点を使い、
3点による球で、再び内側に点群がすべてあるか確認。

(3) (2)の球の外側に点群があったら、再び中心から最大距離の1点と、
(2)の3点のうちの、上記の点との最近点とすりかえて、球を定義、再び全点確認。

(4) (3)を繰り返す。

とりあえず稼動確認したところ、それなりに良さそうな球が求まったのですが、いまいち納得できません。
よろしくお願いします。
通報する
  • 回答数5
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.3
レベル11

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

3度目です。以下のSiteをご覧下さい。非常にシンプルで効果的なアルゴリムです。私の案は撤回します。

1)BoundingBoxを作る(=x,y,z最大最小値)

2)BoundingBoxに内接する球を求め、これを初期球とする。

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

だけで完成です。
-PR-
-PR-

その他の回答 (全4件)

  • 回答No.1
レベル11

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

大変失礼ですが、あまりエレガントな解法とは思えません。なぜなら、

1)「最大距離になる2点」を探すというのは、1/2*n^2回に比例する比較が必要。

2)最小の球とは限らないのではないか。常に大きくしているだけ。「絞る」

下記にBoundingSphereに関するアルゴリズムがあります。中は見てません。


  • 回答No.2
レベル11

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

先程の文章、「絞る」で切れてました。要は、計算時間を食わない範囲で、球の半径を「小さくする」ことも考えるべきではないかということです。

私も職業としてCADには20年程関わっていますが、生憎BoundingBoxしか使っていません。CGの世界では計算時間のかかるRayTracingで、No.1のような「BoundingSphere」が提案され、高速化に寄与しています。

下記のアルゴリズムを追うのがメンドイので、下記アルゴリズムとは別に自分なりの方針を掲げると、

1)BoundingBox作成
2)BoundingBoxに外接する、BoundingSphere作成(これが上限)
3)BoundingBoxに内接する、Sphere作成(これが下限)
4)半径だけでなく、中心も動かして、反復計算させる。(上限・下限で挟み撃ち)
  • 回答No.4
レベル8

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

ametsuchiさん > 2)BoundingBoxに内接する球を求め、これを初期球とする。

細かいようですがBoundingBoxは一般には直方体になるわけで、
初期球としてはこのBoxに内接する球ではなく、このBoxの中心を中心とし、
このBoxの一番長い辺の1/2を半径とする球でいいようにも思えるのですが
如何なものでしょう。
  • 回答No.5
レベル11

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

seianさんの指摘される通り、「Boxの一番長い辺の1/2を半径とする球でいい」です。失礼しました。

書いた後、コンビニで買い物している最中に「内接」という表現が数学的に正確でないことに気が付いたのですが、「まあ、分かってくれるだろう」と妥協してしまいました。
お礼コメント
selju

お礼率 35% (7/20)

返事おそくなって申し訳ございません。
ametsuchiさん、seianさん、早速の回答ありがとうございます。
おかげさまで、誤魔化していた部分が、ようやく確かな答えとして結果がでるようになりました。
CADを経験されている方のアドバイスがあると、非常に助かります。
まだ幾つか誤魔化してCADをカスタマイズした部分があるので、また、よろしくお願いします。

ありがとうございました。
投稿日時 - 2001-06-13 08:49:11
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

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

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

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ