空間上に適当に散りばめられた点群を囲む、最小の球(中心と半径)を求めるプログラムを作っています。
用途は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「円ドル双方向換算」マクロを作成しているのですが・・・(長文です)

Function 円ドル換算(円元金 As Integer)
' 受け取ったドル元金から円換算額を算出して返す
' 引数:ドル元金(Integer型)
' 返数:円換算(Integer型)
Dim 換算レート As Double
Dim ドル換算額 As Double

' 換算レート(1ドル価格)を設定する
換算レート = 109.5

' 円元金からドル換算額を算出する
ドル換算額 = 円元金 / 換算レート

' ドル換算額を呼び出し元に戻す
円ドル換算 = ドル換算額
End Function
Function ドル円換算(ドル元金 As Integer)
' 受け取った円元金からドル換算額を算出して返す
' 引数:円元金(Integer型)
' 返数:ドル換算
Dim 換算レート As Double
Dim 円換算額 As Double

' 換算レート(1ドル価格)を設定する
換算レート = 1 / 109.5

' ドル元金から円換算額を算出する
円換算額 = ドル元金 / 換算レート

' 円換算額を呼び出し元に戻す
ドル円換算 = 円換算額
End Function
Sub 円ドル双方向換算()
Dim ユーザー選択 As Integer
Dim 元金 As Integer
Dim 換算額 As Integer

' 円元金を取得する
円元金 = Range("B3").Value

' ドル元金を取得する
ドル元金 = Range("B3").Value

' 換算する通貨を判定し、それぞれについて換算を行う
If Range("B2") = 1 Then '円ドル換算を行う場合
換算額 = 円ドル換算(ドル元金)
換算額 = Application.WorksheetFunction.Round(円ドル換算, 1) '四捨五入して小数点1桁に変換する
Range("B4").Value = 円ドル換算 '円ドル換算値を出力する
ElseIf Range("B2") = 2 Then 'ドル円換算を行う場合
換算額 = ドル円換算(円元金)
換算額 = Application.WorksheetFunction.Round(ドル円換算, 1) '四捨五入して小数点1桁に変換する
Range("B4").Value = ドル円換算 'ドル円換算値を出力する
End If
End Sub

B2のセルにくる数字が1のときは円→ドルに、2のときはドル→円に換算するマクロを作りたいのですが・・・
元金はセルB3に、換算額はセルB4に表示します。
かなり初心者なので、模範解答を示してもらえると助かります^^;
よろしくお願いします><

Function 円ドル換算(円元金 As Integer)
' 受け取ったドル元金から円換算額を算出して返す
' 引数:ドル元金(Integer型)
' 返数:円換算(Integer型)
Dim 換算レート As Double
Dim ドル換算額 As Double

' 換算レート(1ドル価格)を設定する
換算レート = 109.5

' 円元金からドル換算額を算出する
ドル換算額 = 円元金 / 換算レート

' ドル換算額を呼び出し元に戻す
円ドル換算 = ドル換算額
End Function
Function ドル円換算(ドル元金 As Integer)
' 受け取った円元金からドル換算額...続きを読む

Aベストアンサー

もう少し親切にするなら、
B2に「入力規則」-「リスト」で「元の値」に「円→ドル,ドル→円」として
ユーザー定義関数側を
Function 通貨換算(元金 As Integer,モード As String)
と変更し、更にIf部分を
If モード = "円→ドル" Then
通貨換算 = Round(元金/レート,1)
Else
通貨換算 = Round(元金*レート,1)
End If
と変更すれば、「1はどっちへの換算だっけ?」と迷わず済みます。

なお、#1で回答した中の、
' 返数:換算結果(Integer型)
は不要ですね。

Q球面上の3点と半径から球の中心点を求める

球面上の3点P1(x1,y1,z1),P2(x2,y2,z2),P3(x3,y3,z3)と半径rが与えられたとき、球の中心点Pq(xp,yq,zq)を求める方法を教えて下さい。

球面上3点と半径rが条件として与えられた場合、球の中心点は2個ありそうな気もしますが(何らかの条件で...)、よく分かりません。

何方か、宜しくお願いします。

Aベストアンサー

中心Pq(xq,yq,zq)、半径rの球の方程式は
(x-xq)^2+(y-yq)^2+(z-zq)^2=r^2 …(A) となります。
球面が3点を通るから、(A)の式に代入すると
(x1-xq)^2+(y1-yq)^2+(z1-zq)^2=r^2 …(1)
(x2-xq)^2+(y2-yq)^2+(z2-zq)^2=r^2 …(2)
(x3-xq)^2+(y3-yq)^2+(z3-zq)^2=r^2 …(3)
となります。
(1)~(3)の式を変形すると、xq,yq,zqについての3元2次連立方程式となるので、xq,yq,zqが各々求められます。
なお、2次方程式の判別式が正の数になる場合は中心が2つとなり、0の場合は1つ(重解)、負の数の場合は存在しないことになります。

Q1ドル121.5円の時、1香港ドル15.6円でした。1ドル125.6円の時、1香港ドル16円でした。

1ドル121.5円の時、1香港ドル15.6円でした。
1ドル125.6円の時、1香港ドル16円でした。

ドル円は4円差があるのですが、香港ドルは0.4円しか差がありません。
この差を利用して儲けることができるのでしょうっか?

Aベストアンサー

> 1ドル121.5円の時、1香港ドル15.6円でした。

で、そのとき、1ドルは何香港ドルだったのか。「1ドル121.5円の時、1香港ドル15.6円、1ドルが(121.5÷15.6)より多い香港ドル」だったとするなら、円をドルに替えてそれを香港ドルに替えてそれを円に替えると得をする。
 こういう状況を「裁定機会」と言う。もし裁定機会が生じたら、1/1000秒にも満たないうちに誰か(のコンピュータ)がこの取引をやってしまうんで、すぐに換算レートが修正されて、裁定機会は消滅しちゃいます。すなわち、1ドルが(121.5)÷(15.6)香港ドル、というレートに修正されてしまうと、円をドルに替えてそれを香港ドルに替えてそれを円に替えても、また円を香港ドルに替えてそれをドルに替えてそれを円に替えても、元のままです。
 円・ドル・香港ドルに限らず、商品(石油とか)や債券との間でも裁定機会は滅多に生じず、生じても即座に消滅する。(てか、古典的経済学では「裁定機会は存在しない」というのが定説だった。でも最近になって実際にデータを詳細に調べたら(まれに瞬間的に)裁定機会が生じていることが発見された、という話なんです。)

> 1ドル121.5円の時、1香港ドル15.6円でした。

の時点でドルを買った人Aと、香港ドルを買った人Bとがいたとする。その後、第二の時点で

> 1ドル125.6円の時、1香港ドル16円でした。

となった。つまり、ドルも香港ドルも高くなった。この時点で、Aが手持ちのドルを円に替え、Bは手持ちの香港ドルを円に替えたとすると、A,Bどちらも、買うのに使った円よりも多くの円を手に入れる。
 これは単に、Aは円とドルの間の為替差益、Bは円と香港ドルの間の為替差益によって、この場合はたまたま儲けたというだけのことです。
 第二の時点でまだ売らずにおけば、後でもっと為替差益が大きくなってさらに儲けられるチャンスが来た(だから第二の時点で売らなきゃ良かった)かもしれないし、あるいは、売らずにおいたらその後「売ったら損になる」状況が続いて資金が塩漬けになっちゃう(だから第二の時点で売っといてよかった)かもしれない。
 要するに、売りたいときに売りたいものを持ってないと意味がない訳で、そのためにはあらかじめ「将来売りたくなるもの」を予想して買っておかなくてはならん。博打の一種にすぎません。

> 1ドル121.5円の時、1香港ドル15.6円でした。

で、そのとき、1ドルは何香港ドルだったのか。「1ドル121.5円の時、1香港ドル15.6円、1ドルが(121.5÷15.6)より多い香港ドル」だったとするなら、円をドルに替えてそれを香港ドルに替えてそれを円に替えると得をする。
 こういう状況を「裁定機会」と言う。もし裁定機会が生じたら、1/1000秒にも満たないうちに誰か(のコンピュータ)がこの取引をやってしまうんで、すぐに換算レートが修正されて、裁定機会は消滅しちゃいます。すなわち、1ドルが(121.5)÷(15.6)香...続きを読む

Q球の中心の求め方

今(X1,Y1,Z1)(X2,Y2,Z2)(X3,Y3,Z3)の三つの座標と半径rが分かっています.
この座標の中心(Xq,Yq,Zq)は(X-Xq)^2+(Y-Yq)^2+(Z-Zq)^2=r^2を元に連立方程式を立てれば解けるらしいのですが私には難しくて解けません.
この解(例:Xq=???)を知っている方がいらっしゃいましたらどうか教えてください.

Aベストアンサー

(X1-Xq)^2+(Y1-Yq)^2+(Z1-Zq)^2=r^2 …(1)
(X2-Xq)^2+(Y2-Yq)^2+(Z2-Zq)^2=r^2 …(2)
(X3-Xq)^2+(Y3-Yq)^2+(Z3-Zq)^2=r^2 …(3)

(1)-(2)
(X1-X2)*(X1+X2-2Xq)+(Y1-Y2)*(Y1+Y2-2Yq)+(Z1-Z2)*(Z1+Z2-2Zq)=0 …(4)
(1)-(3)
(X1-X3)*(X1+X3-2Xq)+(Y1-Y3)*(Y1+Y3-2Yq)+(Z1-Z3)*(Z1+Z3-2Zq)=0 …(5)
(4),(5)を(Yq,Zq)について連立方程式として解き、
その(Yq,Zq)を(1)に代入してできるた
Xqの二次方程式を解いてXqを求めて下さい。

文字定数ばかりの一般式の導出ですので、式の項数が非常に多くなりますので計算間違いしないように根気よく計算してください。その場合、球面上の3点の任意の2つが一致しない条件や一直線上に並ばない条件やr>0の条件など、文字を使う上で忘れがちな条件を考慮する必要があるかと思います。

なお、文字変数でなくすべて、具体的な数字の定数であれば、計算は非常に楽に、球の中心座標が出せるでしょう。

やたらに、沢山の文字定数を使って一般化した公式を求めようとするのも考え物です。せっかく導いた公式が余りにも長すぎて暗記ができない、書き写すのに転記ミスが沢山発生するのでは、その公式は使い物になりませんね。Xqの式を数式処理ソフトで実際に計算してみましたが、ここに掲載できるような長さの式にはなりませんね(半角文字の1600文字より遥かに長い式です。)。

(X1-Xq)^2+(Y1-Yq)^2+(Z1-Zq)^2=r^2 …(1)
(X2-Xq)^2+(Y2-Yq)^2+(Z2-Zq)^2=r^2 …(2)
(X3-Xq)^2+(Y3-Yq)^2+(Z3-Zq)^2=r^2 …(3)

(1)-(2)
(X1-X2)*(X1+X2-2Xq)+(Y1-Y2)*(Y1+Y2-2Yq)+(Z1-Z2)*(Z1+Z2-2Zq)=0 …(4)
(1)-(3)
(X1-X3)*(X1+X3-2Xq)+(Y1-Y3)*(Y1+Y3-2Yq)+(Z1-Z3)*(Z1+Z3-2Zq)=0 …(5)
(4),(5)を(Yq,Zq)について連立方程式として解き、
その(Yq,Zq)を(1)に代入してできるた
Xqの二次方程式を解いてXqを求めて下さい。

文字定数ばかりの一般式の導出ですので、式の項数が非常に多くなりますので...続きを読む

Q円とドルの往復の際、平均レートで処理するとなぜ損になるのか

どうも数字に弱いので、どなたかこの疑問に答えていただけると幸いです。
米国への海外出張の際、現地での現金払いは、円からドルに換金した時と、ドルから円に戻した時のレートの平均値を取り、海外で使ったドルを円に換金して支払う、てな決まりが現在あるのですが、前回の収支を見ると、明らかに出張者が損します。なぜなんでしょうか。(そんな方法を採用している自体バカじゃないかというのは置いておいてください、、、)
例 20,000を円からドルへ レート:1ドル200円としてドルは100ドル
海外で50ドルを使用
残りの50ドルを円へ レート:1ドル100円として円は5,000円
(マーケットレートがあまり変わらない場合、円に戻す方がレートが悪いのでこういう想定にしました)
レートの200円と100円との平均は150円
海外で使用した50ドルを1ドル150円で換算すると7,500円
しかし、実際は20,000円持って行って返ってきたのが5,000円だから使用したのは15,000円で、7,500円しかもらえなかったら7,500円損する。
この差が出るのは
1. そもそも使った50ドルは200円で買ったドルなのだから、価値は10,000円。7,500円としか評価されなければ2,500円の損
2.返ってきたドルも、100円なのに150円と過剰評価されているので1ドル当たり50円損していて合計2,500円の損

でもこの2つの損を合計しても、5,000円の損であって、実際損した7,500円にならないのは何でなんでしょうか。
よろしくお願いいたします。

どうも数字に弱いので、どなたかこの疑問に答えていただけると幸いです。
米国への海外出張の際、現地での現金払いは、円からドルに換金した時と、ドルから円に戻した時のレートの平均値を取り、海外で使ったドルを円に換金して支払う、てな決まりが現在あるのですが、前回の収支を見ると、明らかに出張者が損します。なぜなんでしょうか。(そんな方法を採用している自体バカじゃないかというのは置いておいてください、、、)
例 20,000を円からドルへ レート:1ドル200円としてドルは100ドル
海外で50ド...続きを読む

Aベストアンサー

>2.返ってきたドルも、100円なのに150円と過剰評価されているので1ドル当たり50円損していて合計2,500円の損
これがおかしいのでは.
返ってきたドルは,1ドル200円で買ったものなのに,1ドル100円になったしまったら,1ドルあたり100円損なんで,合計5000円の損ですね.2.は会社は無関係なんで,150円という数字は関係ないです.

Q無数の点を包み込む球の求め方

こんにちは。
空間上にある無数の点を包み込む球を求めるにはどのように考えたらよろしいのでしょうか?
試しに凸面の立体(多面体)を求めてみましたがここからどうしてよいか分かりませんでした。
何かよい方法というのはあるのでしょうか?

Aベストアンサー

こんなの?

参考URL:http://www.ipsj.or.jp/07editj/promenade/4309.pdf

Qドルと円の計算式 スイマセン、基本的な質問です。

ドルと円の関係を考えていたら頭がこんがらがってしまって・・・
計算式を教えてください。

例)
1ドル=95円で100万円ぶんドルを購入しました。
1ドル=100円の時、そのすべてを円に変えました。

いくら得したか分かる式を教えてください。
※銀行等の手数料等は一切加味せず、出ている数字のみで計算、
小数点以下切捨てでという前提でお願いします。

95円で100万円買うと10526ドル?
100円で100万買うと10000ドル??
差額の526ドルが儲けなんでしょうが、そのレートは100円で計算???
それとも買ったときの95円????

もう頭の中が?でいっぱいです(笑)
簡単に分かる方法ないですか?
よろしくお願い致します。

Aベストアンサー

95円のレートで100万円分のドルを買うと10526ドル。
10526ドルを100円のレートで円に換えると、10526×100で1,052,600円です。ですから5万2千600円の得です。まあ、526ドルの得と考えても良いですけど。結局526ドルを100円のレートで交換すれば52600円ですから同じです。

Q円弧3点の座標から円の中心座標と半径の求め方をお願いいたします。

円弧3点の座標から円の中心座標と半径の求め方をお願いいたします

Aベストアンサー

円の方程式の一般系は、
x^2 + y^2 + lx + my + n = 0である。
三点を(x1,y1),(x2,y2),(x3,y3)とすると、
これらを代入すれば、

(x1)^2 + (y1)^2 + l(x1) + m(y1) + n = 0---(1)
(x2)^2 + (y2)^2 + l(x2) + m(y2) + n = 0---(2)
(x3)^2 + (y3)^2 + l(x3) + m(y3) + n = 0---(3)

(1)(2)(3)のl,m,nに関する3元連立方程式となるので、
これをとき、それぞれの解を求める。
そして,求まった解をそれぞれ、l',m',n'とおく。
後は、x^2 + y^2 + l'x + m'y + n' = 0とし、
以下のように変形していく。

(x + l'/2)^2 + (y + m'/2)^2 + n' - (l'/2)^2 - (m'/2)^2 = 0
(x + l'/2)^2 + (y + m'/2)^2 = {(m'/2)^2 + (l'/2)^2 - n'}

これにより、円の中心の座標は、(-l'/2,-m'/2)であり、
円の半径は、√{(m'/2)^2 + (l'/2)^2 - n'}となります。

円の方程式の一般系は、
x^2 + y^2 + lx + my + n = 0である。
三点を(x1,y1),(x2,y2),(x3,y3)とすると、
これらを代入すれば、

(x1)^2 + (y1)^2 + l(x1) + m(y1) + n = 0---(1)
(x2)^2 + (y2)^2 + l(x2) + m(y2) + n = 0---(2)
(x3)^2 + (y3)^2 + l(x3) + m(y3) + n = 0---(3)

(1)(2)(3)のl,m,nに関する3元連立方程式となるので、
これをとき、それぞれの解を求める。
そして,求まった解をそれぞれ、l',m',n'とおく。
後は、x^2 + y^2 + l'x + m'y + n' = 0とし、
以下のように変形していく。

...続きを読む

Q1ドル118円の時、円からドルに換金したドルと、1ユーロ151円の時、

1ドル118円の時、円からドルに換金したドルと、1ユーロ151円の時、円からユーロに換金したユーロをいくらかずつ所有しています。1ドル80円、1ユーロ114円となった今、これらの外貨を最小限の損失で運用するにはどうしたらいいでしょうか?

Aベストアンサー

先日TVで見たのですが、ドル円の予想で110~120円になるには10年くらいかかるという専門家が6人中3人でした。
ドルやユーロが通用するところへ旅行に行ったとき使ってくるくらいです。

Q変形図形の重心点(中心点)の求め方

長方形のひとつの角を小さい四角で切り取ったような図形の中心点を求めたいのですが、割り出せるものなのでしょうか?数学に詳しいものではありません。
長方形や正方形なら対角線の交わった点だったような気がします。よろしくお願いいたします。

Aベストアンサー

(1)元の大きい長方形の対角線の交点をAとします。
(2)切り取る小さい長方形の対角線の交点をBとします。
(3)BからAに向けて直線を引き、Aを通り越してさらに延長します。
(4)延長した直線上に点Cをとります。このとき、
   CA:CB=[小さい長方形の面積]:[大きい長方形の面積]
 が成立するようにすると、Cが求める図形の重心です。


人気Q&Aランキング

おすすめ情報