座標を結んだ線分の交差

Question

配列 x, y に（実数）値が与えられており、
(x[1], y[1]) を座標平面上の点 P1 、(x[2], y[2]) を点 P2 、…
と考えたとき、

P1とP2を結んだ線分と、P3とP4を結んだ線分が交差しているかを判断する
プログラム（アルゴリズム）はどのように考えることができるでしょうか？
結ぶ2点を通る直線の傾きなどを求めても、どのように利用すればよいか思いつきませんでした。

C言語というより数学の話かもしれませんが、ご教示いただければ幸いです。
なかなか方法を思いつかず、私の考察を提示できずに恐縮ですが宜しくお願いいたします。

yonfa · Accepted Answer

完全にまたがる場合のみ交差とする、ってことでしたね。
勘違いしていました。失礼しました。

> なぜ外積値から判定できるのかについて理解しきれていませんが…。
一応、補足しておきますが、説明が下手ですみません。
(P1→P2)×(P1→P3) のベクトル方向を考えた場合、
(P1→P2)から(P1→P3)に（180度未満で重なる方向に）回転させて右ねじの進む方向が外積のベクトル方向となります。
このことから、
(P1→P2)×(P1→P3)のz成分 > 0 なら P3 は(P1→P2)の左側、
(P1→P2)×(P1→P3)のz成分 < 0 なら P3 は(P1→P2)の右側
ということになります。

したがって、
2点（P3とP4）がベクトル(P1→P2)の左右に分かれる場合、外積のz成分が正負に分かれる（z成分同士の積は負）ということになります。
線分P3P4が直線P1P2をまたがるということです。

2点が共にベクトルの左側（あるいは右側）であれば、z成分は共に正数（あるいは負数）となり、z成分同士の積は正ということになります。
線分P3P4は直線P1P2をまたがらないということです。

yonfa · Answer

ベクトルの外積を利用して実装されるということなので、少し補足しておきます。
実際に使用されるのは外積の z 成分のみですので、2つの外積の z 成分の積が0以下という条件でよいことになります。

気をつけて欲しいのは、2つの線分が同一直線上にある場合（外積の大きさが2つとも0の場合）についての考慮がしてありませんので、その辺の判定も盛り込むようにしてください。

rabbit_cat · Answer

線分同士の交差判定には定石があります。

P1とP2を結ぶ直線は
(y-y[1])(x[2]-x[1]) - (y[2]-y[1])(x-x[1]) = 0　… (1)

P3とP4を結ぶ直線は
(y-y[3])(x[4]-x[3]) - (y[4]-y[3])(x-x[3]) = 0 … (2)

・(1)の左辺のx,yにP3の座標を代入したもの
と
・(1)の左辺のx,yにP4の座標を代入したもの
の積が0以下

かつ

・(2)の左辺のx,yにP1の座標を代入したもの
と
・(2)の左辺のx,yにP2の座標を代入したもの
の積が0以下

であれば、線分同士は交差しています。

yonfa · Answer

まったく視点を変えてベクトルで考えてみてはどうでしょう。
（質問者様へ、ベクトルわからなかったら聞き流しておいてください。）

ベクトルP1P3とP1P2の外積とP1P4とP1P2の外積(以後、P1P4×P1P2 と書きます)の方向が反対なら、線分P3P4は直線P1P2と交差することになります。
P1P3×P1P2 の大きさが0の場合はP1、P2、P3は同一直線上にあることになります。

したがって、２つの線分が交差する条件は次のような式になります。
if (((P1P3×P1P2 と P1P4×P1P2 の方向が反対) || (P1P3×P1P2 か P1P4×P1P2 のどちらかのみ大きさが0)) &&
　　((P3P1×P3P4 と P3P1×P3P4 の方向が反対) || (P1P3×P1P2 か P1P4×P1P2 のどちらかのみ大きさが0))){
　　　2つの線分は交差
}

ベクトルなんて遥か昔の記憶なのですが、たぶん考え方は合っていると思います。（数学得意な方、間違い指摘していただけるとありがたいです＾＾；）

noname#23393 · Answer

>2直線の式はなんとか出せるのですが、
>プログラム上でこの式をどのように扱えばよいか悩んでしまいました。

直線の式を出すだけではなく、それらを用いて交点の座標を表す式まで計算しないとコードには持っていけませんよね。

>直線がy軸に平行であったり、交わらない場合の交点を算出しようとするあたりの対応で止まってしまいました…。

このあたりの場合分けが必要な計算(分母が0になる可能性がある等)は方程式を手計算で解く段階で洗い出せるかと思います。
今回の場合は仰るとおり「いずれか、もしくは両方の直線がy軸に平行な場合」と「2直線の傾きが等しい場合」が出てくるようです。
普通に方程式を解くときと同様にこれらを場合分けしてコーディングすれば良いのではないでしょうか。

また、交わらない場合に交点を算出する事に関しては、#1さんの仰るとおり、とりあえず線分ではなく直線と思って交点を出して、それがもとの線分の上にあるかを調べれば良いでしょう。

yonfa · Answer

線分の交点を求め、その交点が両方の線分上にあれば交差していると考えられます。
交点が、線分の端点と同じ場合は、交差していないという判断でいいのかな？

後は、実際にプログラムを作ってみて、うまくいかなかったら、再度質問してみてください。

座標を結んだ線分の交差

完全にまたがる場合のみ交差とする、ってことでしたね。

ベクトルの外積を利用して実装されるということなので、少し補足しておきます。

線分同士の交差判定には定石があります。

まったく視点を変えてベクトルで考えてみてはどうでしょう。

>2直線の式はなんとか出せるのですが、

線分の交点を求め、その交点が両方の線分上にあれば交差していると考えられます。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング