在宅ワークのリアルをベテランとビギナーにインタビュー>>

線分と線分が交わる条件を簡単に求める方法ってないでしょうか?

線分が2つ(8つの値)があります
(ax1,ay1)-(ax2,ay2)
(bx1,by1)-(bx1,by1)

この8つの値の大小関係だけで交差するかどうかの判定って
可能でしょうか?
直線の式y = ax + bを2つをわりだし
その解がそれぞれの線分の範囲内にあるかで求めていたのですが
線分の数が多いためパフォーマンスに影響がでてきてしまいました。
(C言語で計算させています。)

数学は苦手なので、困っております。
或いは良い案があればお願いします

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

A 回答 (3件)

説明は省略しますが、


(ay1-ay2)(bx1-ax1)-(ax1-ax2)(by1-ay1)・・・(1)式
(ay1-ay2)(bx2-ax1)-(ax1-ax2)(by2-ay1)・・・(2)式
(by1-by2)(ax1-bx1)-(bx1-bx2)(ay1-by1)・・・(3)式
(by1-by2)(ax2-bx1)-(bx1-bx2)(ay2-by1)・・・(4)式

(1)式と(2)式の積が0以下で
(3)式と(4)式の積が0以下の場合交差します。
    • good
    • 1
この回答へのお礼

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

お礼日時:2003/10/07 10:10

8つの値の大小関係だけでは交差するかどうかは分かりませんが、


交差しないことが判定できる場合があります。
ax1、ax2のいずれもがbx1、bx2の両者より大きい場合などです。
(あとは、共に小さい場合とyについて同じことが言える場合。)
このようなケースを予め判定して除外してしまえば、
パフォーマンスは、ある程度改善すると思います。
    • good
    • 0
この回答へのお礼

参考になりました。
ご回答ありがとうございます。

お礼日時:2003/10/07 10:09

交差はそれしかないでしょうね。


2線分を直線と仮定して交点を求め、交点が線分上にあるかどうかを判定するしかないでしょう。
    • good
    • 0
この回答へのお礼

早速の回答ありがとうございました。

お礼日時:2003/10/07 10:09

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

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

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

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

Q2直線が交わるかどうかの判定式について

点(a,b)、点(c、d)を結ぶ直線Xと
点(e,f)、点(g、h)を結ぶ直線Yがある場合

この2直線が交差するかどうか判定するには
どういう公式に当てはめればいいのか、教えてください。

なお、直線X,Yは平行の場合もあります。

Aベストアンサー

ベクトル(c - a, d - b)
とベクトル(g - e, h - f)
とを考えて、一方が他方の実数倍であれば2直線は平行。
そうでなければ2直線は交わる。

Q2線の交点の求め方教えて下さい。

プログラムを組んでいるのですが、困っています。

2線の斜線が、交差する点の求め方を教えて下さい。

Aベストアンサー

 J-Jさんのご回答で求めることができますよね。
 ただし、これが「一般の2直線の交点を求める」ということであればもう少し慎重になる必要があります。問題を整理して、
 直線a:点a1(Xa1,Ya1)と点a2(Xa2,Ya2)を結ぶ直線
 直線b:点b1(Xb1,Yb1)と点b2(Xb2,Yb2)を結ぶ直線
とします。すると直線の傾きは、
 直線aでは A=(Ya2-Ya1)/(Xa2-Xa1)、
 直線bでは B=(Yb2-Yb1)/(Xb2-Xb1)
ですが、それぞれXa2=Xa1、Xb2=Xb1のときに零による除算が発生します。これを事前にチェックして対応する必要があります。
 さらに直線の傾きが等しいとき(A=B)についても同様のことが言えます。もっともこの場合には交点なしというコードを返すようにしないといけませんが。
 さらにさらに、これが直線ではなくて「2線分の交点を求める」という問題ならば、求めた交点が線分上にのっているかどうかも確認しなければいけません。
 汎用の交点を求める関数を作っておくのも今後のために悪くないと思いましたので蛇足回答をいたしました。

 J-Jさんのご回答で求めることができますよね。
 ただし、これが「一般の2直線の交点を求める」ということであればもう少し慎重になる必要があります。問題を整理して、
 直線a:点a1(Xa1,Ya1)と点a2(Xa2,Ya2)を結ぶ直線
 直線b:点b1(Xb1,Yb1)と点b2(Xb2,Yb2)を結ぶ直線
とします。すると直線の傾きは、
 直線aでは A=(Ya2-Ya1)/(Xa2-Xa1)、
 直線bでは B=(Yb2-Yb1)/(Xb2-Xb1)
ですが、それぞれXa2=Xa1、Xb2=Xb1のときに零による除算が発生します。これを事前にチェックして対応する必要がありま...続きを読む

Q3次元空間内での線分の交差判定について

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

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

Aベストアンサー

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点の中点を取る。
・中点がいやなら、重みを掛ける(場合もある)。

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

1)一般に「捩れの位置」になりますから、互いに最短の位置を求める問題に帰着します。a-kumaさんの言われるような連立一次方程式では未知数が2つ、式がx,y,z3つとなるので解けません。2次元ならyosizoさんの言われるように未知数と式の数が2つで簡単に解けます。

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

3)で、以下、2)のチェック済みである...続きを読む

Q希硫酸の電気分解

希硫酸の電気分解

希硫酸を白金を陽極、銅を陰極にして電気分解をしたらそれぞれでの反応は
陽極:2H2O→O2+4e^- +4H^+
陰極:Cu^2+ +2e^-→Cu

でいいのでしょうか?陰極の反応がなぜ電子が水素イオンとでなく銅イオンと結びつくのか自信がありません。イオン化傾向が銅のほうが低く還元されやすいからでしょうか?

解説と正しい反応式を教えてください。よろしくお願いします。

Aベストアンサー

この場合、陰極は銅イオンはなく、水素イオンが電子を受け取り水素ガスになります。銅板は溶けません。

極板が逆であると仮定すると
陽極が銅だと   Cu → Cu2+ + 2e-
陰極が白金だと  Cu2+ + 2e-
となって陽極が溶けていき、陰極の白金の鏡面に純銅の膜ができると思います。
銅の電解精錬という方法に近いです。この場合は硫酸銅の稀硫酸溶液を使います。

Q直線と線分の交差判定について高速なアルゴリズム

タイトルの通りなのですが、
まさにその部分をプログラムで作っている最中です。

直線 : ax+by+c=0 で言うところの a,b,c のパラメータと
線分の2端点 ( x1 , y1 ) , ( x2 , y2 ) がわかっています。

その情報を使って今は
 ( ax1 + by1 + c ) * ( ax2 + by2 +c ) < 0
のときに交差している。

という風に処理しているんですが、 どうにもこの部分の処理で時間がかかっているみたいで、
なんとか高速化したいんですが、直線と線分の交差判定について触れてあるサイトが少なかったり、
今使っているアルゴリズムのサイトだったりしか見かけないので、どうにもこうにもなりません。

もしこれが最速のアルゴリズムならしかたないんですが、もし皆さんご存知でしたらお力添えをお願いします。

Aベストアンサー

そんだけ大量の演算を高速にやりたいなら、OpenCLとかによるGPGPUの利用を考えてはいかがでしょう。

参考URL:http://codezine.jp/article/detail/5439

Q傾いた四角形内の範囲の条件式

図のように4点ABCDで結ばれた傾いている長方形に、点Eが枠の中にあるのかを判断するには、
どういった条件式を書けば良いのでしょうか?

よろしくお願いします。

Aベストアンサー

No.1,2です。
外積を習っているかを全く考えていませんでした。
最初の外積の値は
(x2-x1)*(y5-y1)-(y2-y1)*(x5-x1)
となります。
残りも同じような式になります。
No.4の回答と考え方は同じなのですが、割り算がないため鉛直部分を考慮しなくてもよいので、一般的にはこの方法を使います。

先に触れましたように、凸図形の場合に一般的に使える方法です。(全ての内角が180度以下)
凹部(180度以上の内角)がある場合には凸図形に分解すれば同じ論理でできます。三角形に分解すると確実に凸図形に分解できます。

以上ご参考に


人気Q&Aランキング