webentwicklung-frage-antwort-db.com.de

Knoten- und Schnittpunkte

Wie würde ich mit numpy den Schnittpunkt zwischen zwei Liniensegmenten berechnen?

In dem Code habe ich segment1 = ((x1, y1), (x2, y2)) und segment2 = ((x1, y1), (x2, y2)). Hinweis Segment 1 entspricht nicht Segment2. In meinem Code habe ich auch die Steigung und den y-Achsenabschnitt berechnet, es wäre schön, wenn das vermieden werden könnte, aber ich weiß nicht, wie es geht.

Ich habe Cramer-Regel mit einer Funktion verwendet, die ich in Python geschrieben habe, aber ich würde gerne einen schnelleren Weg finden, dies zu tun.

21
Xavier

Direkt aus http://www.cs.mun.ca/~rod/2500/notes/numpy-arrays/numpy-arrays.html gestohlen

#
# 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)
29
Hamish Grubijan
import numpy as np

def get_intersect(a1, a2, b1, b2):
    """ 
    Returns the point of intersection of the lines passing through a2,a1 and b2,b1.
    a1: [x, y] a point on the first line
    a2: [x, y] another point on the first line
    b1: [x, y] a point on the second line
    b2: [x, y] another point on the second line
    """
    s = np.vstack([a1,a2,b1,b2])        # s for stacked
    h = np.hstack((s, np.ones((4, 1)))) # h for homogeneous
    l1 = np.cross(h[0], h[1])           # get first line
    l2 = np.cross(h[2], h[3])           # get second line
    x, y, z = np.cross(l1, l2)          # point of intersection
    if z == 0:                          # lines are parallel
        return (float('inf'), float('inf'))
    return (x/z, y/z)

if __== "__main__":
    print get_intersect((0, 1), (0, 2), (1, 10), (1, 9))  # parallel  lines
    print get_intersect((0, 1), (0, 2), (1, 10), (2, 10)) # vertical and horizontal lines
    print get_intersect((0, 1), (1, 2), (0, 10), (1, 9))  # another line for fun

Erläuterung

Beachten Sie, dass die Gleichung einer Zeile ax+by+c=0 ist. Wenn sich also ein Punkt in dieser Zeile befindet, ist dies eine Lösung für (a,b,c).(x,y,1)=0 (. ist das Punktprodukt)

es sei l1=(a1,b1,c1), l2=(a2,b2,c2) zwei Linien und p1=(x1,y1,1), p2=(x2,y2,1) zwei Punkte.


Finden der Linie durch zwei Punkte:

sei t=p1xp2 (das Kreuzprodukt zweier Punkte) ein Vektor, der eine Linie darstellt.

Wir wissen, dass p1 in der Zeile t steht, weil t.p1 = (p1xp2).p1=0. . Wir wissen auch, dass p2 auf t steht, weil t.p2 = (p1xp2).p2=0. t muss also die Zeile sein, die p1 und p2 durchläuft. 

Das heißt, wir können die Vektordarstellung einer Linie erhalten, indem wir das Kreuzprodukt zweier Punkte auf dieser Linie nehmen .


Den Schnittpunkt finden:

Nun sei r=l1xl2 (das Kreuzprodukt zweier Linien) ein Vektor, der einen Punkt darstellt

Wir wissen, dass r auf l1 liegt, da r.l1=(l1xl2).l1=0. Wir wissen auch, dass r auf l2 liegt, da r.l2=(l1xl2).l2=0. r muss also der Schnittpunkt der Linien l1 und l2 sein. 

Interessanterweise können wir den Schnittpunkt finden, indem wir das Kreuzprodukt zweier Linien nehmen .

11
Norbu Tsering

Dies ist vielleicht eine späte Antwort, aber es war der erste Treffer, als ich "numpy line intersections" googelte. In meinem Fall habe ich zwei Linien in einer Ebene, und ich wollte schnell Schnittpunkte zwischen ihnen bekommen, und Hamishs Lösung wäre langsam - es wäre eine verschachtelte for-Schleife über alle Liniensegmente erforderlich. 

So machen Sie es ohne for-Schleife (es ist ziemlich schnell):

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)]

Um es zu verwenden, geben Sie zwei Zeilen als Argumente an, wobei arg eine 2-Spalten-Matrix ist, wobei jede Zeile einem Punkt (x, y) entspricht: 

# 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)

habe Spaß

9
marmaduke

Dies ist eine Version der Antwort von @Hamish Grubijan, die auch für mehrere Punkte in jedem der Eingabeargumenten funktioniert, d. H. a1, a2, b1, b2 kann Nx2-Zeilenarrays von 2D-Punkten sein. Die perp-Funktion wird durch ein Punktprodukt ersetzt.

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
3
user1248490

Hier ist ein (etwas gezwungener) Einzeiler:

import numpy as np
from scipy.interpolate import interp1d

interp1d(segment1-segment2,np.arange(segment1.shape[0]))(0)

Interpolieren Sie die Differenz (Standardeinstellung ist linear) und suchen Sie eine 0 des Inversen.

Prost!

1
Andy Reagan
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


'''
finding intersect point of line AB and CD 
where A is the first point of line AB
and B is the second point of line AB
and C is the first point of line CD
and D is the second point of line CD
'''



def get_intersect(A, B, C, D):
    # a1x + b1y = c1
    a1 = B.y - A.y
    b1 = A.x - B.x
    c1 = a1 * (A.x) + b1 * (A.y)

    # a2x + b2y = c2
    a2 = D.y - C.y
    b2 = C.x - D.x
    c2 = a2 * (C.x) + b2 * (C.y)

    # determinant
    det = a1 * b2 - a2 * b1

    # parallel line
    if det == 0:
        return (float('inf'), float('inf'))

    # intersect point(x,y)
    x = ((b2 * c1) - (b1 * c2)) / det
    y = ((a1 * c2) - (a2 * c1)) / det
    return (x, y)
0
Sadekujjaman

Dies ist, was ich benutze, um einen Linienschnittpunkt zu finden. Er funktioniert entweder mit 2 Punkten jeder Linie oder nur mit einem Punkt und seiner Steigung. Ich löse grundsätzlich das System der linearen Gleichungen.

def line_intersect(p0, p1, m0=None, m1=None, q0=None, q1=None):
    ''' intersect 2 lines given 2 points and (either associated slopes or one extra point)
    Inputs:
        p0 - first point of first line [x,y]
        p1 - fist point of second line [x,y]
        m0 - slope of first line
        m1 - slope of second line
        q0 - second point of first line [x,y]
        q1 - second point of second line [x,y]
    '''
    if m0 is  None:
        if q0 is None:
            raise ValueError('either m0 or q0 is needed')
        dy = q0[1] - p0[1]
        dx = q0[0] - p0[0]
        lhs0 = [-dy, dx]
        rhs0 = p0[1] * dx - dy * p0[0]
    else:
        lhs0 = [-m0, 1]
        rhs0 = p0[1] - m0 * p0[0]

    if m1 is  None:
        if q1 is None:
            raise ValueError('either m1 or q1 is needed')
        dy = q1[1] - p1[1]
        dx = q1[0] - p1[0]
        lhs1 = [-dy, dx]
        rhs1 = p1[1] * dx - dy * p1[0]
    else:
        lhs1 = [-m1, 1]
        rhs1 = p1[1] - m1 * p1[0]

    a = np.array([lhs0, 
                  lhs1])

    b = np.array([rhs0, 
                  rhs1])
    try:
        px = np.linalg.solve(a, b)
    except:
        px = np.array([np.nan, np.nan])

    return px
0
dashesy