はじめまして。
3D関係のプログラムを組む上で、線分同士の判定を行う必要があるのですが
数学の知識が乏しく困っています。

3次元空間内の線分ABとCDが交差しているか判定し、
交差していればその交点を求めたいのです。
2次元の場合はできたのですが、3次元になるとどうやって計算すればよいのか
わかりません。(交差以外に、ねじれの位置関係があるんですよね?)
どなたか教えていただけると助かります。

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

A 回答 (7件)

1)一般に「捩れの位置」になりますから、互いに最短の位置を求める問題に帰着します。

a-kumaさんの言われるような連立一次方程式では未知数が2つ、式がx,y,z3つとなるので解けません。2次元ならyosizoさんの言われるように未知数と式の数が2つで簡単に解けます。

2)線分AB、CDの何れかの長さが<ε以下、または、線分AB、CDはほぼ平行ならゼロ割を起こすか答えが求まっても答えの精度が著しく低下します。このチェックも実際のプログラムでは絶対に必要です。

3)で、以下、2)のチェック済みであると仮定して.....。

4)たまたま最近3D-CAD用に作ったもので数式の求めた方を忘れてしまったが、

// t0:AB方向単位ベクトル、t1:CD方向単位ベクトル、として、
// float spd = <t0・t1>即ち、ベクトルt0とt1の内積

float det= spd*spd - 1.0f; // spd:AB方向単位ベクトル
v01 = C - A; //3Dベクトル (C-A)
u0 = (spd*<v01・t1> - <v01・t0>) / det;
u1 = (<v01・t0> - spd*<v01・t1>) / det;

として、パラメータ、u0,u1が求まります。ここに、
u0:AB方向パラメータ、u0=0の時、q0(u0)=Aで、u0はAからの距離を表わす。
■q0(u0)=A+u0*t0...............Equ.1)
u1:CD方向パラメータ、u1=0の時、q1(u1)=Cで、u1はCからの距離を表わす。
■q1(u1)=C+u1*t1...............Equ.2)

これで、捩れの位置に2点求まるのですが、

・2点が距離の許容誤差よりも離れていたら、エラーとする。
・2点が距離の許容誤差以内なら、2点の中点を取る。
・中点がいやなら、重みを掛ける(場合もある)。

この説明で不十分ならあとで補足します。
    • good
    • 0

motsuanさん、アドバイスありがとうございます。



>外積を直接とっちえばいいものを ..中略...のような周りくどいことをやらないと 答えがもとめられないのかちょっと不思議に思います

一般に外積計算は内積計算に比べて「コストのかかる」計算であり、なるべく使わないようにしているだけです。motsuanさんのやり方の分かり易さや、「外積計算」の有用性については百も承知しているつもりです。

もし、私のやり方の方が「コストのかかる」計算であったなら、折角今回初めて「専門家」を自称したのにおハズカシい限りで、訂正させてもらいます。

motsuanさんのやり方も私がいう「一般性のある」やり方で、敬意を表します。3D幾何計算ライブラリなどでは直線(線分)同士は、「交点」ではなく「最近点」として求めるのが普通です。
    • good
    • 0
この回答へのお礼

返事が遅くなり、失礼しました。
詳しい解説、ありがとうございます。
>3D幾何計算ライブラリなどでは直線(線分)同士は、「交点」ではなく「最近点」として求めるのが普通です。
そうなんですか、しりませんでした。勉強になります。

今回の皆さんの回答を参考にしてプログラムに落とし込んでみます。

お礼日時:2001/05/14 10:18

もうすでに完全に説明されているようですが、


なんとなく私も前に計算してなるほどと
なんか関心してしまったことがあるので
(他の方からみると見苦しいとは思いますが)
書きこませてください。

ametsuchiさんのアルゴリズムは
多分以下のように求めれば
すべてベクトル演算で求められると思います。
(ねじれの位置の場合も線分の中に対応する点が
 あれば一番近づいている点をあたえると思います。)

ベクトルを[v]と表します。
2つ直線[p](u)、[q](v)をパラメータ表示で表します。
それぞれ定点を[p0]、[q0]、大きさが任意の方向ベクトルを[s]、[t]とすると
[p](u)=[p0]+[s]u
[q](v)=[q0]+[t]v
と表せます。このとき
[p](u)-[q](v)=0
となる u、v があればそれが交点を与えます。
3次元空間で交わる場合には、
当然どの平面に射影したとしても(どっちの方角から見ても)
交点を結んでいなくてはなりません。
したがって適当な平面へ射影した場合の交点を求めれば良いわけです。
これがkent-mildsのおっしゃっていることで
やっぱり一番現実的なのでしょうね。

でも、なんとなく、
一番近づく点の特殊な場合が交点であって欲しい
という気持ちを収めるために以下のように基準面を選びます。
すなわち、一番近づく点が射影したときに交点となる平面は
[s]、[t]のベクトルで張る平面ですから、この平面を基準に考えます。
(以下、内積を・で、外積を×で表します。)

[p](u)と[q](v)を[s]、[t]のベクトルで張る平面に射影すると
1点に重なるためには[p](u)-[q](v)が面の法線と平行でなくてはなりません。
したがって、([p](u)-[q](v))×[s]と([p](u)-[q](v))×[t]は
面に平行なベクトルになりますから、これが[s]×[t]と直行する必要があります。
すなわち、
([s]×[t])・(([p](u)-[q](v))×[s])=0・・・(*)
([s]×[t])・(([p](u)-[q](v))×[t])=0
が求める点の条件で、これから u, v が決まります。たとえば u を求めると、
([p](u)-[q](v))×[t]
 =([p0]-[q0])×[t] + [s]×[t]u =0
両辺に[s]×[t]を掛けて
([s]×[t])・(([p0]-[q0])×[t] )+([s]×[t])・([s]×[t])u =0。
これを解いて
u =-([s]×[t])・(([p0]-[q0])×[t] )/([s]×[t])・([s]×[t])。
同様に(tとsを入れ替えて)、
v =([s]×[t])・(([p0]-[q0])×[s] )/([s]×[t])・([s]×[t])
となります。

わたしはなんで
([p](u)-[q](v))と[s]×[t]の外積を直接とっちえばいいものを
(*)のような周りくどいことをやらないと
答えがもとめられないのかちょっと不思議に思います。
以上です。お邪魔しました。
    • good
    • 0
この回答へのお礼

返事が遅くなり、失礼しました。
詳しい解説、ありがとうございます。
今回の皆さんの回答を参考にしてプログラムに落とし込んでみます。

お礼日時:2001/05/14 10:15

すいません。

もう2つ補足。

1)a-kumaさんらの方法でもできないことはないのですが、一般性がなく、式3つのうちどの2つを選択するか決めなくてはいけません。私の方法なら、場合分けも不要で答えは一意的に求まります。

2)線分上に求まるか否かのチェックはa-kumaさんの言われるとおりです。パラメータの取り方が違っていますが、本質的な差異ではありません。私が示したパラメータだと、

■0<= u0,u1 <=線分長

だとOKです。

・しかし実際のプログラムでは、

■-tol<= u0,u1 <=線分長+tol

のようにすることが多いです。ここに,tolとは距離の許容誤差です。

※何か不明な点があったら聞いて下さい。
    • good
    • 0

補足します。



2線分上の点はパラメータで表現すると、

■q0(u0)=A+u0*t0...............Equ.1)
■q1(u1)=C+u1*t1...............Equ.2)

ですが、

・ベクトルq1(u0)-q0(u1)と、ベクトルt0、が直交
・ベクトルq1(u0)-q0(u1)と、ベクトルt1、が直交

という条件を課すと、2つのパラメータ、u0,u1に関する2元一次連立方程式になります。これを解いたのが、先程の、

float det = spd*spd - 1.0f; // spd:AB方向単位ベクトル
v01 = C - A; //3Dベクトル (C-A)
u0 = (spd*<v01・t1> - <v01・t0>) / det;
u1 = (<v01・t0> - spd*<v01・t1>) / det;

です。
    • good
    • 0
この回答へのお礼

すみません、これは↓のNo3 Kent-mild さんへのお礼です。
#ここの使い方に慣れてなくて、意味のない書き込みをしてしまいました・・・

返事が遅れて大変失礼しました。
みなさんからの回答を参考にしてプログラムを組んでみようと思います。
ありがとうございました。

お礼日時:2001/05/14 10:24

プログラムで簡単に組める方法で説明します。


2次元ではできてらっしゃるようなので、2次元の説明は省略します。
3次元空間が(x,y,z)座標で定義されている場合、
xy平面上の交点のz座標が同一なら交差、一致しなければねじれです。
交点の座標はすぐでるのはわかりますよね?
    • good
    • 0
この回答へのお礼

3D幾何計算ライブラリなどでは直線(線分)同士は、「交点」ではなく「最近点」として求めるのが普通です。

お礼日時:2001/05/14 10:18

線分AB上の任意の点Pはベクトル表現で



p = t×a + (1 - t)×b
  但し 0≦t≦1

です(本当は、記号の上に矢印を書きたいところなんですが)。
同様に、線分CD上の任意の点Qは

q = s×c + (1 - s)×d
  但し 0≦s≦1

です。線分が交差しているということは、PとQが同一になるという
ことですから、

p = q

を満たす t と s が有るかどうか、ということですね。
3次元であれば、各要素毎に3本の式ができ、変数が二つですから
簡単ですね。

例えば、x と y について、t と s についての連立方程式を解いて、
それぞれ0~1に入っていなければ、交差してない。
もし、その範囲に入っていたとすれば、z の式に代入してみて
等式を満たすようであれば、交差する、という判定でしょうか。
    • good
    • 0
この回答へのお礼

返事が遅くなり、失礼しました。
詳しい解説、ありがとうございます。
今回の皆さんの回答を参考にしてプログラムに落とし込んでみます。

お礼日時:2001/05/14 10:21

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

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

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

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

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

Q曲線y=f(x)上にあるA(x,y)の接線とy軸の交点をBとした時、線分ABはx軸によって二等分され

曲線y=f(x)上にあるA(x,y)の接線とy軸の交点をBとした時、線分ABはx軸によって二等分される。上記の条件を満たし、(2,1)をとおる曲線求めよ、という問題について

上記の問題で解き方が腑に落ちず困っています。理解された方、教えていただきたいのですが、

回答では、Bはy軸の交点にあることから、x=0であるので、接点の方程式に代入すると、
y=y−xy'
となり、線分ABは二等分されるのでA,Bのy座標の絶対値は等しい、とありました。
しかし、その後の式で、
y−xy'=−y
とありましたが、上記右辺の−yはBのx=0をy−xy'へ代入したものであると考えているのですが、
なぜ接線の方程式にBのx=0を代入し、y座標y−xy'を求めた後、その後再びy−xy'へx=0を代入しているのでしょうか?

説明が長くて申し訳ないです。
みなさんにお力を貸していただければと思います。よろしくお願いします。

Aベストアンサー

あー、主さんは曲線上Aの座標(x、y)とAのところの接線の上の座標を混同していますね。
Aのところの接線の方程式はx、yとはちがうX、Yをつかわなくてはならない。
これを使うと、接線の方程式は、A(x、y)を通り、傾きy'の直線だから、
Y―y=y'(X―x)、これからBのy座標は左の式にX=0を入れて
Y=y―xy'・・・① と出てくる。
そして、このy切片Yは条件からAのy座標yと真反対だからY=―y、これを①に入れて
―y=y―xy'・・・②

この①②のことを解説の式は言っていますよ。

Q2つの線分に垂直な線分の交点

2次元平面に点P(x0,y0)、点A(x1,y1)、点B(x2,y2)があり、
点Aを通る線分PAに垂直な線分と
点Bを通る線分PBに垂直な線分の交点の
求め方を教えて下さい。

垂直ベクトルを求め、任意に座標を決めて
連立方程式を解くやり方だと上手くいかない時が
あります。シンプルに求める方法がありましたら
教えて下さい。

Aベストアンサー

 「~垂直な線分」は「~垂直な直線」の意味と解釈しますね。
 交点が存在するには、点P,A,Bが同一直線上に無いこと。従って、同一直線上にある場合は除外します。
 また、線分PAと線分PBが直行する場合は、点P,A,Bと交点で長方形が構成されるので特殊な場合として、置いておきます(答えは簡単にでますね)。
 では、上記の2つの場合以外のときには、P点を原点とし横軸(X軸)上にA点が位置するような座標(X、Y)を考えて、座標変換してはいかがなものでしょうか。新しい座標(X、Y)上でのPBに垂直な直線そのものが交点の座標を示すことになりませんか。

Q数学orアルゴリズムが得意の方(線分と線分の交点判別)

C言語のアルゴリズムを勉強中です。
線分A(A(x1,y1),B(x2,y2))と線分B(C(x3,y3),D(x4,x4))が交差するかどうかを判別し、交差するのであればその交点P(X,Y)を求める。
また、その交点がどちらか一方の線分上にあるかどうかも判別したいのです。
一番効率よくやるにはどのようにすればよいでしょうか。
例えば
1、三角形の符号付き面積を使って交差するかどうかと各点が線分上にあるかどうかを判別し、その後交点を求める
2、とり合えず交点を求めてその交点が各線分内(上)にあるかどうかを判別

他にもたくさんありそうですがとにかく出来るだけ計算回数を減らしたいのです。(さっき求めた~~を~~するといったかんじで)

出来れば流れ全体を書いていただきたいのですが書き込むのが大変だと思うのでせめて使う判別式だけでも教えてください。
これが出来たら、
多角形と多角形の交点判別のアルゴリズムにも挑戦しようと思っています。

数学の得意な方、アルゴリズムを考えるのが好きな方
よろしくお願いします。

Aベストアンサー

No.4,5のhogehoge2です。何度もすみません。
間違っていましたので、訂正いたします。

次の部分を
----------------------------------------
(2)
 det==0のとき(3)へ
 その他(else)のとき(6)へ

(3)
 y1==y2のとき(4)へ
 その他のとき(5)へ
----------------------------------------


次のようにご訂正ください。
----------------------------------------
(2)
 det==0のとき(3)'へ
 その他(else)のとき(6)へ

(3)'
 (x3-x1)*(y4-y1)-(y3-y1)*(x4-x1)==0のとき(3)へ
 その他のとき 線分AB、CDは共有点をもたない。

関数の終り

(3)
 x1==x2のとき(4)へ
 その他のとき(5)へ
----------------------------------------


以上

No.4,5のhogehoge2です。何度もすみません。
間違っていましたので、訂正いたします。

次の部分を
----------------------------------------
(2)
 det==0のとき(3)へ
 その他(else)のとき(6)へ

(3)
 y1==y2のとき(4)へ
 その他のとき(5)へ
----------------------------------------


次のようにご訂正ください。
----------------------------------------
(2)
 det==0のとき(3)'へ
 その他(else)のとき(6)へ

(3)'
 (x3-x1)*(y4-y1)-(y3-y1)*(x4-x1)==0のとき(3)へ
 その他...続きを読む

Q二次元空間から三次元空間への変換

具体的なイメージが浮かばないので、問題が解けません。
考え方と、行列を用いた回答を教えてください!!
問題は以下のとおりです。

右目と左目の距離が70mmである人が、目と紙の距離が140mmの時に見るとちょうどよくなるようなステレオ図を作れ。
うまい立体が思い浮かばない場合は、次の立体をステレオ図により再現せよ。
目の前350mmのところに中心をもつ一辺の長さが70mmの立方体。
ただし、立方体の各面は顔面に平行でないとする。

理系の学生、または数学ができる方、ぜひお願いします!!

Aベストアンサー

この問題、2つ変なところがあります。
(1) stereogramを140mmの所に置いて観察できるヒトは近眼です。普通これが見えるためには凸レンズ(老眼鏡)が必要。すると、像が拡大されて見えます。この事まで考慮しないと、「目の前350mmのところに中心をもつ一辺の長さが70mmの立方体」を実際に見せてあげることは出来ません。
(2) 350mm先にある大きい立体を右目だけ、左目だけで観察してみれば分かるように、140mmのところに置いたスクリーン上では右目用の図と左目用の図は部分的に重なり合ってしまいます。だから、赤と青で描いて、左右の目に赤・青の色つき眼鏡を掛けるとか、もっと小さい物を見せるとか、工夫しないといけません。
出題者はここまで考えているのかなあ。

 目がピンホールカメラみたいに、うんと近いところにもピントが合うものとして考える(多分出題者の意図はこっちでしょう)なら、瞳は点で表されます。顔面から(従って左右目の瞳からも)140mmの距離にある平面状のスクリーンSに3次元空間中の点p=(x,y,z)を投影したとき、どこに来るのか。つまり、右の瞳Rと点Pとを結ぶ直線がSと交わる点はどこか。これをPrとしましょう。同様に左の瞳Lと点Pとを結ぶ直線がSと交わる点をPlとする。
見せたい立体を構成する各点の座標PをPr, Plに変換してスクリーン状に点を打てばstereogramができあがるわけです。
まず右目だけ考えます。右目の瞳を原点とする3次元座標系(x,y,z)、ただしx-y平面がスクリーンと平行である、そういう座標系を考える。この座標系で問題の図形の各頂点の座標を表す方法は、自分で考えてね。
 スクリーンS上にも座標系(X,Y)を作ります。原点はz軸とSとの交点とし、X軸はx軸と平行であるとしましょう。つまりスクリーンはz=Dという方程式で表される平面です。D=140mm。
 点Pの座標(x,y,z)と原点とを結ぶ直線とSとの交点はどこに来るか。パラメータtを使って直線を((x/z)t, (y/z)t, t)と表すことが出来ますね。だから、t=Dの時、X=(x/z)D, Y=(y/z)D、これがスクリーンに投影された点Pの像の位置PRです。
 さて、物体が直線の辺を持っているとき、スクリーン上でもこの辺の像は直線になります。だから、多面体のように辺が直線で構成された物なら、頂点の座標だけこの方法で変換して、あとは線分で繋いでやれば良いんですね。
 左目についても同じようにやります。70mmだけ見せたい物体の座標をずらす必要があることにご注意。
 あとはご自分で。でっきるかな。できるのか。

この問題、2つ変なところがあります。
(1) stereogramを140mmの所に置いて観察できるヒトは近眼です。普通これが見えるためには凸レンズ(老眼鏡)が必要。すると、像が拡大されて見えます。この事まで考慮しないと、「目の前350mmのところに中心をもつ一辺の長さが70mmの立方体」を実際に見せてあげることは出来ません。
(2) 350mm先にある大きい立体を右目だけ、左目だけで観察してみれば分かるように、140mmのところに置いたスクリーン上では右目用の図と左目用の図は部分的に重なり合ってしまいます。...続きを読む

Q長さ1、A,Bをもつ3本の線分を与え、これらを用いて長さABの線分を作

長さ1、A,Bをもつ3本の線分を与え、これらを用いて長さABの線分を作図せよという問題で、どのように作図してなぜABの長さになるかの証明方法を教えてください。何でもいいので。

Aベストアンサー

 相似な直角三角形を利用して、例えば、添付図のように作図してはいかがですか?
 このような図を使うと、いくつかのバリエーションが考えられますよ。


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

人気Q&Aランキング

おすすめ情報