35

numpy を使用して 2 つの線分の交点を計算するにはどうすればよいですか?

私が持っているコードではsegment1 = ((x1,y1),(x2,y2))、segment2 = ((x1,y1),(x2,y2)). 注記segment1は等しくありませんsegment2。したがって、私のコードでは、勾配と y 切片も計算しています。それを回避できればいいのですが、方法がわかりません。

Python で作成した関数で Cramer の規則を使用してきましたが、これを行うためのより高速な方法を見つけたいと思います。

4

10 に答える 10

45

https://web.archive.org/web/20111108065352/https://www.cs.mun.ca/~rod/2500/notes/numpy-arrays/numpy-arrays.htmlから直接盗まれた

#
# line segment intersection using vectors
# see Computer Graphics by F.S. Hill
#
from numpy import *
def perp( a ) :
    b = empty_like(a)
    b[0] = -a[1]
    b[1] = a[0]
    return b

# line segment a given by endpoints a1, a2
# line segment b given by endpoints b1, b2
# return 
def seg_intersect(a1,a2, b1,b2) :
    da = a2-a1
    db = b2-b1
    dp = a1-b1
    dap = perp(da)
    denom = dot( dap, db)
    num = dot( dap, dp )
    return (num / denom.astype(float))*db + b1

p1 = array( [0.0, 0.0] )
p2 = array( [1.0, 0.0] )

p3 = array( [4.0, -5.0] )
p4 = array( [4.0, 2.0] )

print seg_intersect( p1,p2, p3,p4)

p1 = array( [2.0, 2.0] )
p2 = array( [4.0, 3.0] )

p3 = array( [6.0, 0.0] )
p4 = array( [6.0, 3.0] )

print seg_intersect( p1,p2, p3,p4)
于 2010-07-15T03:13:46.953 に答える
9

これはおそらく遅い応答ですが、私が「numpylineintersections」をグーグルで検索したときの最初のヒットでした。私の場合、平面に2つの線があり、それらの間の交差をすばやく取得したかったので、ハミッシュのソリューションは遅くなります。つまり、すべての線分にネストされたforループが必要になります。

forループなしでそれを行う方法は次のとおりです（非常に高速です）。

from numpy import where, dstack, diff, meshgrid

def find_intersections(A, B):

    # min, max and all for arrays
    amin = lambda x1, x2: where(x1<x2, x1, x2)
    amax = lambda x1, x2: where(x1>x2, x1, x2)
    aall = lambda abools: dstack(abools).all(axis=2)
    slope = lambda line: (lambda d: d[:,1]/d[:,0])(diff(line, axis=0))

    x11, x21 = meshgrid(A[:-1, 0], B[:-1, 0])
    x12, x22 = meshgrid(A[1:, 0], B[1:, 0])
    y11, y21 = meshgrid(A[:-1, 1], B[:-1, 1])
    y12, y22 = meshgrid(A[1:, 1], B[1:, 1])

    m1, m2 = meshgrid(slope(A), slope(B))
    m1inv, m2inv = 1/m1, 1/m2

    yi = (m1*(x21-x11-m2inv*y21) + y11)/(1 - m1*m2inv)
    xi = (yi - y21)*m2inv + x21

    xconds = (amin(x11, x12) < xi, xi <= amax(x11, x12), 
              amin(x21, x22) < xi, xi <= amax(x21, x22) )
    yconds = (amin(y11, y12) < yi, yi <= amax(y11, y12),
              amin(y21, y22) < yi, yi <= amax(y21, y22) )

    return xi[aall(xconds)], yi[aall(yconds)]

次に、それを使用するには、引数として2行を指定します。ここで、argは2列の行列であり、各行は（x、y）ポイントに対応します。

# example from matplotlib contour plots
Acs = contour(...)
Bsc = contour(...)

# A and B are the two lines, each is a 
# two column matrix
A = Acs.collections[0].get_paths()[0].vertices
B = Bcs.collections[0].get_paths()[0].vertices

# do it
x, y = find_intersections(A, B)

楽しんで

于 2012-02-02T10:44:41.650 に答える
7

これは、@Hamish Grubijan の回答のバージョンであり、各入力引数の複数のポイントに対しても機能します。つまり、、、、a1は2D ポイントの Nx2 行配列にすることができa2ますb1。関数は内積に置き換えられますb2。perp

T = np.array([[0, -1], [1, 0]])
def line_intersect(a1, a2, b1, b2):
    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
于 2016-11-16T16:55:20.083 に答える