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

質問

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

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

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

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

回答No.3

yuusukekyouju · ベストアンサー

説明は省略しますが、
(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以下の場合交差します。

お礼

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

回答No.2

ranx

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

お礼

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

回答No.1

ymmasayan

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

お礼

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