動作環境

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

線分の交差判定

二線分が交差するか確認をしようとしている。

計算幾何学 by 杉原厚吉さん
p42
に方法は記載されている。

scipyなどで実装されたコードがないか探した。

Numpy and line intersections

answered Nov 16 '16 at 16:55
user1248490

上記の解答例を使ってみた。

code

line_intersect_180415.py

import numpy as np

# on Python 3.5.2


def line_intersect(a1, a2, b1, b2):
    # Reference
    # https://stackoverflow.com/questions/3252194/numpy-and-line-intersections
    # answered Nov 16 '16 at 16:55
    # user1248490
    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

# case 1 (intersection)
a1 = np.array([-1, 0])
a2 = np.array([1, 0])
b1 = np.array([0, 1])
b2 = np.array([0, -1])
res = line_intersect(a1, a2, b1, b2)
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 = line_intersect(a1, a2, b1, b2)
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 = line_intersect(a1, a2, b1, b2)
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 = line_intersect(a1, a2, b1, b2)
print(res)

run

$ python3 line_intersect_180415.py 
[[0. 0.]]
[[3. 0.]]
[[-3.  0.]]
[[0. 0.]]

交差する二線分、交差しない二線分、ともに値が返る。

可視化

Jupyterで座標を可視化。

line_intersect_graph_180415.ipynb

%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d
from pylab import rcParams

'''
v0.1 Apr. 15, 2018
    - draw 4 cases
    - add draw_scatter()
'''

rcParams['figure.figsize'] = 7, 7
rcParams['figure.dpi'] = 110

fig = plt.figure()


def draw_scatter(ax, xs, ys, title):
    ax.scatter(xs[:2], ys[:2], c='blue')
    ax.scatter(xs[2:], ys[2:], c='red')
    ax.set_title(title)
    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.grid(True)
    

# case 1
ax1 = fig.add_subplot(2, 2, 1)
xs1 = [-1, 1, 0, 0]
ys1 = [0, 0, 1, -1]
draw_scatter(ax1, xs1, ys1, 'case 1')

# case 2
ax2 = fig.add_subplot(2, 2, 2)
xs2 = [-1, 1, 0, 3]
ys2 = [0, 0, 1, 0]
draw_scatter(ax2, xs2, ys2, 'case 2')

# case 3
ax3 = fig.add_subplot(2, 2, 3)
xs3 = [-2, 1, 0, -3]
ys3 = [0, 0, 1, 0]
draw_scatter(ax3, xs3, ys3, 'case 3')

# case 4
ax4 = fig.add_subplot(2, 2, 4)
xs4 = [0.5, 1, 0, 0]
ys4 = [0, 0, 1, -1]
draw_scatter(ax4, xs4, ys4, 'case 4')

fig.tight_layout()

StackoverFlowのコード

case 1以外は交差していない。
StackoverFlowのコードは「二線分が無限長さを持った場合の交点を求める」処理のようだ。