geometry > numpy > 二線分（有限長さ）の交差判定 > 無限長さの二線分の交点を使った判定 > geometry_lineintersect_180415.py v0.1, v0.2

動作環境

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には他のシンプルな判定方法が紹介されている。

title:交差

線分交差判定 by @hokekiyoo さん
のコードはPython2用ですが、同じ結果が得られました。