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

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

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

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

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

No.1 回答者： ymmasayan 回答日時： 2003/10/06 17:51

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

２線分を直線と仮定して交点を求め、交点が線分上にあるかどうかを判定するしかないでしょう。

この回答へのお礼

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

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

No.2 回答者： ranx 回答日時： 2003/10/06 18:19

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

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

この回答へのお礼

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

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

No.3 ベストアンサー 回答者： yuusukekyouju 回答日時： 2003/10/06 21:06

説明は省略しますが、

(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以下の場合交差します。

この回答へのお礼

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

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