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

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

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

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

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

とりあえず稼動確認したところ、それなりに良さそうな球が求まったのですが、いまいち納得できません。
よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (5件)

3度目です。

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

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

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

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

だけで完成です。

参考URL:http://www.3dspot.com/rtnews/rtnews7b.html
    • good
    • 0

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

失礼しました。

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

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

ありがとうございました。

お礼日時:2001/06/13 08:49

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



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

先程の文章、「絞る」で切れてました。

要は、計算時間を食わない範囲で、球の半径を「小さくする」ことも考えるべきではないかということです。

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

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

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

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

なぜなら、

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

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

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

参考URL:http://www.acm.org/tog/resources/RTNews/html/rtn …
    • good
    • 0

このQ&Aに関連する人気のQ&A

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

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

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

Q三角形の外接円の中心座標を求めるプログラム

三点の座標(x1,y1),(x2,y2),(x3,y3)が与えられたときに、三角形の外接円の中心座標と半径を求めるプログラムが欲しいです。

垂直二等分線の交点を求めるやり方は既に知っているのですが、連立方程式になってしまいます。
ですので出来ればこれを一発で求められる連立じゃない式が欲しいのですが、ご存じないでしょうか?

x = 何とか
y = 何とか
みたいな感じです。

Javaでやろうとしていますが、計算式さえわかれば自分で書けると思うので、中心座標のx,yを求める式を教えて下さい。

過去質問を探してみましたが、みんな連立方程式で解けば良いとおっしゃっていまして…

Aベストアンサー

地道に解いた結果をもちいれば良いと思います。
中心を(p,q)とおくと

(x-p)^2+(y-q)^2=R^2
に(x1,y1),(x2,y2),(x3,y3)を代入して
(x1-p)^2+(y1-q)^2=R^2 (1)
(x2-p)^2+(y2-q)^2=R^2 (2)
(x3-p)^2+(y3-q)^2=R^2 (3)

(1)-(2)
(x1-p)^2-(x2-p)^2+(y1-q)^2-(y2-q)^2=0
(x1-x2)(x1+x2-2p) + (y1-y2)(y1+y2-2q)=0
-2(x1-x2)p -2(y1-y2)q +x1^2 -x2^2 +y1^2 -y2^2 =0

(1)-(3)
-2(x1-x3)p -2(y1-y3)q +x1^2 -x3^2 +y1^2 -y3^2 =0


p = {(y1-y3)(y1^2 -y2^2 +x1^2 -x2^2) +(y1-y2)(y1^2 -y3^2 +x1^2 -x3^2)} / {2(y1-y3)(x1-x2)+2(y1-y2)(x1-x3)}

q = {(x1-x3)(x1^2 -x2^2 +y1^2 -y2^2) +(x1-x2)(x1^2 -x3^2 +y1^2 -y3^2)} / {2(x1-x3)(y1-y2)+2(x1-x2)(y1-y3)}


とかなり複雑な式になりました。
計算がどこかで間違っているかもしれませんが、残念ながらあまり美しくはなりませんね。

地道に解いた結果をもちいれば良いと思います。
中心を(p,q)とおくと

(x-p)^2+(y-q)^2=R^2
に(x1,y1),(x2,y2),(x3,y3)を代入して
(x1-p)^2+(y1-q)^2=R^2 (1)
(x2-p)^2+(y2-q)^2=R^2 (2)
(x3-p)^2+(y3-q)^2=R^2 (3)

(1)-(2)
(x1-p)^2-(x2-p)^2+(y1-q)^2-(y2-q)^2=0
(x1-x2)(x1+x2-2p) + (y1-y2)(y1+y2-2q)=0
-2(x1-x2)p -2(y1-y2)q +x1^2 -x2^2 +y1^2 -y2^2 =0

(1)-(3)
-2(x1-x3)p -2(y1-y3)q +x1^2 -x3^2 +y1^2 -y3^2 =0


p = {(y1-y3)(y1^2 -y2^2 +x1^2 -x2^2) +(y1-y2)(y1^2 -y3^2 +x1^2 -x3^2)} / {2(y1...続きを読む

QLNK2019: 未解決の外部シンボルのエラーが出る

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自キャラのデータ
Point2D g_jikipos = {40, 400};//自キャラの座標

//画像ハンドル
int g_jikiimage[11];

//色々なファイルの読み込み
int LoadFiles(){
//画像ファイル読み込み
if(LoadDivGraph("media\\player01.bmp",
11,11,1,64,64,g_jikiimage) == -1) return -1;

return 1;
}


 mymain.h
//他から呼び出させるMyMainの関数
void MyMain();
int LoadFiles();


 myhelper.h(サンプルなので打ちミスはない)
#include "DxLib.h"
#include <limits.h>
#include <math.h>

//構造体宣言
//座標またはベクトルを記録する構造体
struct Vector{
float x,y;
};
typedef Vector Point2D;
//線を記録する構造体
struct Line2D{
Point2D startpos, endpos;
float katamuki;//傾きをラジアン値で記録
Vector speed;//移動している場合は速度をセット
};
//球体を記録する構造体
struct Ball2D{
Point2D position;
float hankei;//半径
};
//四角形を記録する構造体
struct Rect2D{
Point2D lefttop;
Point2D rightbottom;
float width;
float height;
};


//ライブラリ関数
Point2D PosInView(Point2D in);
int XInView(float inx);
int YInView(float iny);
void ScrollToLeft(float jikiposx);
void ScrollToRight(float jikiposx);
void ScrollToUp(float jikiposy);
void ScrollToDown(float jikiposy);
void DrawLineInView(float x1, float y1, float x2, float y2, int Color, int Thickness);
void DrawCircleInView(float x, float y, float r, int Color, int FillFlag);
void DrawAnimation(float x, float y, double ExtRate, double Angle,int TurnFlag,
int *imgarray, int allframe, float fps);
//ベクトル関数
Vector CreateVector(Vector in, float veclen);
Vector AddVector(Vector v1, Vector v2);
Vector SubVector(Vector v1, Vector v2);
Vector AddVectorInFrameTime(Vector pos, Vector speed);
Vector AddVectorInFrameTime2(Vector pos, Vector speed, Vector accel);
Vector Normalize(Vector in);
Vector RotateVector(Vector in, float radian);
float VectorLengthSquare(Vector in);
float DotProduct(Vector v1, Vector v2);
float CrossProduct(Vector v1, Vector v2);
void SetLine2DKatamuki(Line2D *in);
void DrawLine2D(Line2D in, int Color, int Thickness);
void DrawBall2D(Ball2D in, int Color, int Fill);
//当たり判定関数
bool HitTestLineAndBall(Line2D linein, Ball2D ballin);
bool IsPointAtLineFace(Line2D linein, Point2D ptin);
bool HitTestLineAndLine(Line2D line1, Line2D line2);
bool HitTestBallAndBall(Ball2D a, Ball2D b);
bool HitTestPointAndBox(Rect2D rect, Point2D pt);
//タイマー関数
void SetSimpleTimer(int idx, int time);
int GetPassedTime(int idx);


//グローバル変数
extern float g_frametime;
extern Rect2D g_framerect;//画面領域(当たり判定)
extern Point2D g_current_field_pos;//現在の左上座標
extern Rect2D g_stagesize;//ステージサイズ

//定数宣言
const float ZEROVALUE = 1e-10f;
const float PIE = 3.1415926f;
const int SCROLL_LIMIT = 200;
----------------------------------------------------------------
 エラー内容
1>myhelper.obj : error LNK2019: 未解決の外部シンボル "void __cdecl MyMain(void)" (?MyMain@@YAXXZ) が関数 _WinMain@16 で参照されました
1>C:\Documents and Settings\Owner\My Documents\Visual Studio 2008\Projects\my\Debug\my.exe : fatal error LNK1120: 外部参照 1 が未解決です
1>my - エラー 2、警告 0
ビルド: 0 正常終了、1 失敗、0 更新不要、0 スキップ
----------------------------------------------------------------
画像を貼り付けときます
(見えにくい場合→http://www.dotup.org/uploda/www.dotup.org154142.jpg.html)
初心者なのでわかりやすくお願いします

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自...続きを読む

Aベストアンサー

ファイル構成から推測するに
mymain.cpp というファイルに
void MyMain(void) {
// ここに処理を書く
}
という関数が必要なようです。

Q3次元座標を原点中心に回転したい

任意のゼロでないベクトル(a,b,c)を原点中心に回転し、z軸に合致させるとする。同じ回転移動を3次元座標上の任意の点(x,y,z)に対して行った時の移動後座標が知りたいのです。

計算と結果を教えて下さい。

Aベストアンサー

A No. 1 です。補足。

「回転行列」
http://www.cg.info.hiroshima-cu.ac.jp/~miyazaki/knowledge/tech07.html

ロドリゲスの公式もあります。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング