動作環境
GeForce GTX 1070 (8GB)
ASRock Z170M Pro4S [Intel Z170chipset]
Ubuntu 16.04.4 LTS desktop amd64
TensorFlow v1.7.0
cuDNN v5.1 for Linux
CUDA v8.0
Python 3.5.2
IPython 6.0.0 -- An enhanced Interactive Python.
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
GNU bash, version 4.3.48(1)-release (x86_64-pc-linux-gnu)
scipy v0.19.1
geopandas v0.3.0
MATLAB R2017b (Home Edition)
ADDA v.1.3b6
gnustep-gui-runtime v0.24.0-3.1
PyMieScatt v1.7.0
geometry > link > Numpy and line intersections > 二線分が無限長さを持った場合の交点
の続き。
処理概要
- 二線分がある（有限長さ）
- 二線分が交差しているか確認する
無限長さの二線分の交点は取得できる場合、交点が線分の内部にあるかどうかは距離から判断できる。
code
geometry_lineintersect_180415.py v0.1, v0.2
geometry_lineintersect_180415.py
import numpy as np
import sys
'''
v0.2 Apr. 15, 2018
- add Test_intersect()
- add is_intersected()
- add is_inside_of_lineA()
v0.1 Apr. 15, 2018
- add get_intersection_point_unlimited_length()
'''
def get_intersection_point_unlimited_length(a1, a2, b1, b2):
# Reference
# https://stackoverflow.com/questions/3252194/numpy-and-line-intersections
# answered Nov 16 '16 at 16:55
# user1248490
'''
Find intersect points assuming lines have unlimited lengths
'''
T = np.array([[0, -1], [1, 0]])
da = np.atleast_2d(a2 - a1)
db = np.atleast_2d(b2 - b1)
dp = np.atleast_2d(a1 - b1)
dap = np.dot(da, T)
denom = np.sum(dap * db, axis=1)
num = np.sum(dap * dp, axis=1)
return np.atleast_2d(num / denom).T * db + b1
def is_inside_of_lineA(a1, a2, intersect):
wrk = a1 - a2
da1a2 = np.sqrt(wrk[0]**2 + wrk[1]**2)
wrk = a1 - intersect
d1 = np.sqrt(wrk[0]**2 + wrk[1]**2)
wrk = intersect - a2
d2 = np.sqrt(wrk[0]**2 + wrk[1]**2)
return (abs(da1a2 - (d1+d2)) < sys.float_info.epsilon)
def is_intersected(a1, a2, b1, b2):
its = get_intersection_point_unlimited_length(a1, a2, b1, b2) # its: intersect
res = is_inside_of_lineA(a1, a2, its[0]) # [0] only 1 element
return res
def Test_intersect():
# case 1 (intersection)
a1 = np.array([-1, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([0, -1])
res = is_intersected(a1, a2, b1, b2) # its: intersect
print(res) # True
# case 2 (no intersection)
a1 = np.array([-1, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([3, 0])
res = is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
# case 3 (no intersection)
a1 = np.array([-2, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([-3, 0])
res = is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
# case 4 (no intersection)
a1 = np.array([0.5, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([0, -1])
res = is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
テストコード
line_intersect_180415.py
import numpy as np
import sys
import geometry_lineintersect_180415 as GLI
# on Python 3.5.2
'''
v0.1 Arp. 15, 2018
- check 4 cases for intersections
- import [geometry_lineintersect_180415]
'''
GLI.Test_intersect()
print('---')
# case 1 (intersection)
a1 = np.array([-1, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([0, -1])
res = GLI.is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
# case 2 (no intersection)
a1 = np.array([-1, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([3, 0])
res = GLI.is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
# case 3 (no intersection)
a1 = np.array([-2, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([-3, 0])
res = GLI.is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
# case 4 (no intersection)
a1 = np.array([0.5, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([0, -1])
res = GLI.is_intersected(a1, a2, b1, b2) # its: intersect
print(res)
実行
$ python3 line_intersect_180415.py
True
False
False
False
---
True
False
False
False
線分の状況は下記に図示している。
geometry > link > Numpy and line intersections > 二線分が無限長さを持った場合の交点
検索用キーワード
- 交差判定
- 交点列挙
- 交差検出
Qiita link
Qiitaには他のシンプルな判定方法が紹介されている。
線分交差判定 by @hokekiyoo さん
のコードはPython2用ですが、同じ結果が得られました。