6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

線分交差判定

Posted at

線分が交差しているかを判定するアルゴリズム

import numpy as np
a1 = np.array([1,1])
a2 = np.array([5,5])
# crossing
b1 = np.array([3,1])
b2 = np.array([1,3])
# non-crossing
c1 = np.array([3,1])
c2 = np.array([5,3])

def judge(p1,p2,p3,p4):
    t1 = (p1[0] - p2[0]) * (p3[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p3[0])
    t2 = (p1[0] - p2[0]) * (p4[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p4[0])
    t3 = (p3[0] - p4[0]) * (p1[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p1[0])
    t4 = (p3[0] - p4[0]) * (p2[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p2[0])
    return t1*t2<0 and t3*t4<0

print judge(a1,a2,b1,b2)
print judge(a1,a2,c1,c2)
print judge(b1,b2,c1,c2)

True
False
True

returnの行の不等号(<)を等号つき(<=)にすると、クロスじゃなくてぎりぎり重なっているのもOKになる

6
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?