search
LoginSignup
0
Help us understand the problem. What are the problem?

posted at

2つの線分の交差判定(python)

背景

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本の演習問題にて、2つの線分(4点が与えられたとき)の交差判定を行うプログラムを書いたので、今後の参考のためにまとめました。

この記事で説明しないこと

以下のサイトに「線分が交差するとは」といった説明やその判定条件についてまとめられているため、この記事では割愛いたします。

すごくざっくりとまとめると、以下です。

  • 「交差する」とは、一方の線分を直線にしたとき、もう一方の線分が分断される、それが相互に成り立つか
  • 領域を用いて条件の判定が可能。分断されているかは式の積が0未満かで判別できる。
y1 - ax1 -b < 0 \\
y2 - ax2 -b > 0 \\
(y1 - ax1 -b)(y2 - ax2 -b) < 0

参考サイト

  1. 【Python】線分交差判定のプログラムを書いた
  2. ☆もっと簡単に-線分交差判定-☆

本題

上記の参考サイト1の実装例では、今回の演習問題ではACが取れません。
その理由として、2つの線分が1直線上にあるときや端が重なっているときに、問題側では交差と見做していることが挙げられます。

そこで、x座標、y座標ごとに座標が一切被っていない場合はfalseを返す処理を追加しました。
具体的な処理はそれぞれの最大値と最小値を比較し、最大値 < 最小値の時にfalseを返すというものです。
以下、4点[xi, yi]の座標が与えられたときの実装例です。

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))


def max_min_cross(p1, p2, p3, p4):
    min_ab, max_ab = min(p1, p2), max(p1, p2)
    min_cd, max_cd = min(p3, p4), max(p3, p4)

    if min_ab > max_cd or max_ab < min_cd:
        return False

    return True


def cross_judge(a, b, c, d):
    # x座標による判定
    if not max_min_cross(a[0], b[0], c[0], d[0]):
        return False

    # y座標による判定
    if not max_min_cross(a[1], b[1], c[1], d[1]):
        return False

    tc1 = (a[0] - b[0]) * (c[1] - a[1]) + (a[1] - b[1]) * (a[0] - c[0])
    tc2 = (a[0] - b[0]) * (d[1] - a[1]) + (a[1] - b[1]) * (a[0] - d[0])
    td1 = (c[0] - d[0]) * (a[1] - c[1]) + (c[1] - d[1]) * (c[0] - a[0])
    td2 = (c[0] - d[0]) * (b[1] - c[1]) + (c[1] - d[1]) * (c[0] - b[0])
    return tc1 * tc2 <= 0 and td1 * td2 <= 0


ans = "No"
if cross_judge(A, B, C, D):
    ans = "Yes"

print(ans)

この実装で、2つの線分として4点が与えられたときの線分の交差判定の問題は(おそらく)解けるかと思います。

まとめ

線分の交差判定(というより主に数直線が交わってるかの判定)について記載しました。
似たような問題を解いている方の少しでも力になれれば幸いです。

ここまでお読みいただきありがとうございました。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?