webentwicklung-frage-antwort-db.com.de

Wie kann ich überprüfen, ob sich zwei Segmente schneiden?

Wie kann ich überprüfen, ob sich zwei Segmente schneiden?

Ich habe folgende Daten:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

Ich muss einen kleinen Algorithmus in Python schreiben, um zu erkennen, ob sich die zwei Linien schneiden.

Aktualisieren:
alt text

63
aneuryzm

Die Gleichung einer Linie lautet:

f(x) = A*x + b = y

Für ein Segment ist es genau dasselbe, außer dass x in einem Intervall I enthalten ist.

Wenn Sie zwei Segmente haben, wie folgt definiert:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Die Abcisse Xa des potentiellen Schnittpunkts (Xa, Ya) muss in beiden Intervallen I1 und I2 enthalten sein, die wie folgt definiert sind:

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

Und wir könnten sagen, dass Xa enthalten ist in:

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Nun müssen wir überprüfen, ob dieses Intervall Ia existiert:

if (max(X1,X2) < min(X3,X4))
    return false; // There is no mutual abcisses

Wir haben also eine zweizeilige Formel und ein gegenseitiges Intervall. Ihre Linienformeln sind:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

Da wir zwei Punkte pro Segment erhalten haben, können wir A1, A2, b1 und b2 bestimmen:

A1 = (Y1-Y2)/(X1-X2) // Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4) // Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

Wenn die Segmente parallel sind, gilt A1 == A2:

if (A1 == A2)
    return false; // Parallel segments

Ein Punkt (Xa, Ya), der auf beiden Linien steht, muss beide Formeln f1 und f2 überprüfen:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2) // Once again, pay attention to not dividing by zero

Als letztes müssen Sie überprüfen, ob Xa in Ia enthalten ist:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) ||
     (Xa > min( max(X1,X2), max(X3,X4) )) )
    return false; // intersection is out of bound
else
    return true;

Darüber hinaus können Sie beim Start überprüfen, dass zwei der vier angegebenen Punkte nicht gleich sind, um alle Tests zu vermeiden.

39
OMG_peanuts

Benutzer @ i_4_got zeigt auf diese Seite mit einer sehr effizienten Lösung in Python. Ich reproduziere es hier der Einfachheit halber (da es mich glücklich gemacht hätte, es hier zu haben):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
58
Grumdrig

Sie müssen nicht genau wo berechnen, die sich die Segmente schneiden, sondern nur ob verstehen, die sie überhaupt schneiden. Dies vereinfacht die Lösung.

Die Idee ist, ein Segment als "Anker" zu behandeln und das zweite Segment in 2 Punkte zu unterteilen.
Nun müssen Sie die relative Position jedes Punktes zum "verankerten" Segment (OnLeft, OnRight oder Collinear) ermitteln.
Nachdem Sie dies für beide Punkte getan haben, prüfen Sie, ob einer der Punkte OnLeft und der andere OnRight ist (oder möglicherweise eine kollineare Position, wenn Sie auch unsachgemäße Kreuzungen einschließen möchten).

Sie müssen dann den Vorgang mit den Rollen Anker und getrennte Segmente wiederholen.

Eine Kreuzung ist nur dann vorhanden, wenn einer der Punkte OnLeft und der andere OnRight ist. Siehe diesen Link für eine ausführlichere Erklärung mit Beispielbildern für jeden möglichen Fall.

Das Implementieren einer solchen Methode ist viel einfacher als das Implementieren einer Methode, die den Schnittpunkt ermittelt (angesichts der vielen Eckfälle, die Sie ebenfalls behandeln müssen).

Update

Die folgenden Funktionen sollen die Idee veranschaulichen (Quelle: Computational Geometry in C ).
Anmerkung: In diesem Beispiel wird die Verwendung von ganzen Zahlen angenommen. Wenn Sie stattdessen eine Fließkommadarstellung verwenden (was die Dinge offensichtlich komplizieren könnte), sollten Sie einen Epsilon-Wert bestimmen, um "Gleichheit" (meistens für die IsCollinear-Bewertung) anzugeben.

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Wenn Sie diese Funktion verwenden, müssen Sie natürlich darauf achten, dass jedes Segment "zwischen" dem anderen Segment liegt (da es sich um endliche Segmente handelt und nicht um unendliche Linien). 

Wenn Sie diese Funktion verwenden, können Sie auch verstehen, ob Sie eine richtige - oder unsachgemäße - Schnittmenge haben.

  • Proper: Es gibt keine kollinearen Punkte. Die Segmente kreuzen sich jeweils "Von Seite zu Seite".
  • Falsch: Ein Segment "berührt" nur das andere (mindestens einer der Punkte von Ist kollinear mit dem Verankerten Segment).
25
Liran

Angenommen, die beiden Segmente haben die Endpunkte A, B und C, D. Die numerisch robuste Methode zur Bestimmung des Schnittpunkts besteht darin, das Vorzeichen der vier Determinanten zu überprüfen:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

Für den Schnittpunkt muss jede Determinante auf der linken Seite das entgegengesetzte Vorzeichen der rechten Seite haben, es muss jedoch keine Beziehung zwischen den beiden Linien bestehen. Sie überprüfen grundsätzlich jeden Punkt eines Segments mit dem anderen Segment, um sicherzustellen, dass sie auf gegenüberliegenden Seiten der durch das andere Segment definierten Linie liegen.

Siehe hier: http://www.cs.cmu.edu/~quake/robust.html

15
Victor Liu

Basierend auf Lirans und Grumdrigs - ausgezeichneten Antworten ist hier ein vollständiger Python-Code, um zu überprüfen, ob closed -Segmente sich schneiden. Funktioniert für kollineare Segmente, Segmente parallel zur Achse Y, entartete Segmente (Teufel ist im Detail). Nimmt ganzzahlige Koordinaten an. Fließkommakoordinaten erfordern eine Änderung des Punktgleichheitstests.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True
6
dmitri

Hier ist ein C-Code, um zu überprüfen, ob zwei Punkte auf den gegenüberliegenden Seiten des Liniensegments liegen. Mit diesem Code können Sie überprüfen, ob sich auch zwei Segmente schneiden.

// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {

//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize

// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;

// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
        cout<<"collinear points"<<endl;

return(SIGN(proj1) != SIGN(proj2));

}

3
Vlad

Hier ist ein weiterer Python-Code, um zu prüfen, ob sich geschlossene Segmente schneiden. Es ist die überarbeitete Version des C++ - Codes in http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ . Diese Implementierung deckt alle Sonderfälle ab (z. B. alle Punkte kolinear).

def on_segment(p, q, r):
    '''Given three colinear points p, q, r, the function checks if 
    point q lies on line segment "pr"
    '''
    if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
        q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
        return True
    return False

def orientation(p, q, r):
    '''Find orientation of ordered triplet (p, q, r).
    The function returns following values
    0 --> p, q and r are colinear
    1 --> Clockwise
    2 --> Counterclockwise
    '''

    val = ((q[1] - p[1]) * (r[0] - q[0]) - 
            (q[0] - p[0]) * (r[1] - q[1]))
    if val == 0:
        return 0  # colinear
    Elif val > 0:
        return 1   # clockwise
    else:
        return 2  # counter-clockwise

def do_intersect(p1, q1, p2, q2):
    '''Main function to check whether the closed line segments p1 - q1 and p2 
       - q2 intersect'''
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2 and o3 != o4):
        return True

    # Special Cases
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 and on_segment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 and on_segment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 and on_segment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 and on_segment(p2, q1, q2)):
        return True

    return False # Doesn't fall in any of the above cases

Nachfolgend finden Sie eine Testfunktion, um zu überprüfen, ob es funktioniert.

import matplotlib.pyplot as plt

def test_intersect_func():
    p1 = (1, 1)
    q1 = (10, 1)
    p2 = (1, 2)
    q2 = (10, 2)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (10, 0)
    q1 = (0, 10)
    p2 = (0, 0)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (-5, -5)
    q1 = (0, 0)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (0, 0)
    q1 = (1, 1)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))
3
Fabian Ying

Sie haben zwei Liniensegmente. Definieren Sie ein Segment mit den Endpunkten A und B und das zweite Segment mit den Endpunkten C und D. Ein Trick von Nizza zeigt an, dass sie sich innerhalb der Grenzen der Segmente schneiden müssen. (Beachten Sie, dass sich die Linien selbst über die Grenzen der Segmente hinaus schneiden können. Sie müssen also vorsichtig sein. Guter Code wird auch auf parallele Linien achten.)

Der Trick besteht darin, zu testen, dass die Punkte A und B auf den gegenüberliegenden Seiten der Linie CD liegen müssen UND die Punkte C und D auf den gegenüberliegenden Seiten der Linie AB liegen müssen.

Da dies Hausaufgaben sind, gebe ich Ihnen keine explizite Lösung. Ein einfacher Test, um zu sehen, auf welche Seite einer Linie ein Punkt fällt, ist die Verwendung eines Punktprodukts. Berechnen Sie also für eine gegebene Zeile CD den Normalenvektor zu dieser Zeile (ich werde es N_C nennen.) Testen Sie nun einfach die Vorzeichen dieser beiden Ergebnisse:

dot(A-C,N_C)

und

dot(B-C,N_C)

Wenn diese Ergebnisse entgegengesetzte Vorzeichen haben, sind A und B entgegengesetzte Seiten der Zeile CD. Führen Sie jetzt den gleichen Test für die andere Linie AB durch. Es hat einen normalen Vektor N_A. Vergleichen Sie die Zeichen von

dot(C-A,N_A)

und

dot(D-A,N_A)

Ich überlasse es Ihnen, herauszufinden, wie man einen normalen Vektor berechnet. (In 2-d ist das trivial, aber wird sich Ihr Code darüber sorgen, ob A und B unterschiedliche Punkte sind? Sind C und D gleichfalls verschieden?)

Sie müssen sich immer noch Gedanken darüber machen, ob Liniensegmente auf derselben unendlichen Linie liegen oder ob ein Punkt tatsächlich auf das andere Liniensegment selbst fällt. Guter Code wird auf jedes mögliche Problem eingehen.

3
user85109

Mit der Formschönen Bibliothek können Sie sehr einfach überprüfen, ob sich Liniensegmente schneiden. Verwenden Sie dazu die intersectsNAME _ Methode :

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

enter image description here

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

enter image description here

1
Georgy

Wir können dies auch mit Vektoren lösen. 

Definieren wir die Segmente als [start, end]. Wenn zwei solcher Segmente [A, B] und [C, D] angegeben sind, die beide eine Länge ungleich Null haben, können wir einen der Endpunkte auswählen, der als Bezugspunkt verwendet werden soll, sodass wir drei Vektoren erhalten:

x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]

Von dort aus können wir nach einem Schnittpunkt suchen, indem wir in p + t*r = u*q t und u berechnen. Nachdem wir ein wenig mit der Gleichung herumgespielt haben, erhalten wir:

t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]

Die Funktion ist also:

def intersects(a, b):
    p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
    q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
    r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]

    t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
        if (q[0]*r[1] - q[1]*r[0]) != 0 \
        else (q[1]*p[0] - q[0]*p[1])
    u = (p[0] + t*r[0])/q[0] \
        if q[0] != 0 \
        else (p[1] + t*r[1])/q[1]

    return t >= 0 and t <= 1 and u >= 0 and u <= 1
1
Rogem

Da Sie nicht erwähnen, dass Sie den Schnittpunkt der Linie suchen möchten, wird das Problem einfacher zu lösen. Wenn Sie den Schnittpunkt benötigen, ist die Antwort von OMG_peanuts ein schnellerer Ansatz. Wenn Sie jedoch nur herausfinden möchten, ob sich die Linien schneiden oder nicht, können Sie dies mit der Liniengleichung (ax + by + c = 0) tun. Der Ansatz ist wie folgt:

  1. Beginnen wir mit zwei Liniensegmenten: Segment 1 und Segment 2. 

    segment1 = [[x1,y1], [x2,y2]]
    segment2 = [[x3,y3], [x4,y4]]
    
  2. Prüfen Sie, ob es sich bei den beiden Liniensegmenten um Linien mit unterschiedlichen Längen und Längen handelt. 

  3. Von nun an gehe ich davon aus, dass die beiden Segmente nicht null sind und unterschiedlich sind. Berechnen Sie für jedes Liniensegment die Steigung der Linie und erhalten Sie dann die Gleichung einer Linie in der Form von ax + durch + c = 0. Berechnen Sie nun den Wert von f = ax + von + c für die zwei Punkte der anderes Liniensegment (wiederholen Sie dies auch für das andere Liniensegment).

    a2 = (y3-y4)/(x3-x4);
    b1 = -1;
    b2 = -1;
    c1 = y1 - a1*x1;
    c2 = y3 - a2*x3;
    // using the sign function from numpy
    f1_1 = sign(a1*x3 + b1*y3 + c1);
    f1_2 = sign(a1*x4 + b1*y4 + c1);
    f2_1 = sign(a2*x1 + b2*y1 + c2);
    f2_2 = sign(a2*x2 + b2*y2 + c2);
    
  4. Jetzt sind nur noch die verschiedenen Fälle übrig. Ist f = 0 für einen Punkt, berühren sich die beiden Linien an einem Punkt. Wenn f1_1 und f1_2 gleich sind oder f2_1 und f2_2 gleich sind, schneiden sich die Linien nicht. Wenn f1_1 und f1_2 ungleich sind und f2_1 und f2_2 ungleich sind, schneiden sich die Liniensegmente. Je nachdem, ob Sie die Linien, die sich berühren, als "sich überschneidend" betrachten möchten oder nicht, können Sie Ihre Bedingungen anpassen. 

1
achyuthan_jr

suchen Sie für die Segmente AB und CD die Steigung der CD

slope=(Dy-Cy)/(Dx-Cx)

cD über A und B ausdehnen und den Abstand zur CD nehmen, die gerade nach oben geht

dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

prüfen Sie, ob sie auf gegenüberliegenden Seiten liegen

return dist1*dist2<0
1
Anonymous

Berechnen Sie den Schnittpunkt der Linien, die auf Ihren Segmenten liegen (dh es geht im Wesentlichen um das Lösen eines linearen Gleichungssystems), und prüfen Sie, ob es sich zwischen dem Anfangs- und Endpunkt Ihrer Segmente befindet.

0
kosii

Ich dachte, ich würde eine Nice-Swift-Lösung beitragen:

struct Pt {
    var x: Double
    var y: Double
}

struct LineSegment {
    var p1: Pt
    var p2: Pt
}

func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {

    if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
        if (ls2.p2.x-ls2.p1.x == 0) {
            //both lines are vertical and parallel
            return false
        }

        let x = ls1.p1.x

        let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
        let c2 = ls2.p1.y-slope2*ls2.p1.x

        let y = x*slope2+c2 // y intersection point

        return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
    }

    if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2

        let x = ls2.p1.x

        let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
        let c1 = ls1.p1.y-slope1*ls1.p1.x

        let y = x*slope1+c1 // y intersection point

        return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2

    }

    let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
    let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)

    if (slope1 == slope2) { //segments are parallel
        return false
    }

    let c1 = ls1.p1.y-slope1*ls1.p1.x
    let c2 = ls2.p1.y-slope2*ls2.p1.x

    let x = (c2-c1)/(slope1-slope2)

    return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
        ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
    //validate that x is between x1,x2 in both segments

}
0
Matej Ukmar

Auf diese Weise überprüfe ich, ob sich eine Linie kreuzt und wo die Kreuzung auftritt. Verwenden wir x1 bis x4 und y1 bis y4

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Dann brauchen wir einige Vektoren, um sie darzustellen

dx1 = X2 - X1
dx2 = X4 - X4
dy1 = Y2 - Y1
dy2 = Y4 - Y3

Nun schauen wir uns die Determinante an

det = dx1 * dy2 - dx2 * dy1

Wenn die Determinante 0.0 ist, sind die Liniensegmente parallel. Dies könnte bedeuten, dass sie sich überschneiden. Wenn sie sich nur an Endpunkten überlappen, gibt es eine Schnittpunktlösung. Ansonsten wird es unendlich viele Lösungen geben. Was ist Ihr Schnittpunkt bei unendlich vielen Lösungen? Es ist also ein interessanter Sonderfall. Wenn Sie im Voraus wissen, dass sich die Linien nicht überlappen können, können Sie einfach prüfen, ob sich det == 0.0 und wenn ja, sagen Sie einfach, dass sie sich nicht überschneiden und fertig sind. Ansonsten fahren wir fort

dx3 = X3 - X1
dy3 = Y3 - Y1

det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2

Wenn det, det1 und det2 alle Null sind, sind Ihre Linien kolinear und können sich überlappen. Wenn det Null ist, det1 oder det2 jedoch nicht, sind sie nicht kolinear, sondern parallel, sodass es keine Schnittmenge gibt. Was also jetzt übrig bleibt, wenn det Null ist, ist ein 1D-Problem anstelle von 2D. Wir müssen eine von zwei Möglichkeiten prüfen, abhängig davon, ob dx1 Null ist oder nicht (damit wir eine Division durch Null vermeiden können). Wenn dx1 Null ist, dann mache einfach die gleiche Logik mit y-Werten und nicht mit x darunter.

s = X3 / dx1
t = X4 / dx1

Dies berechnet zwei Skalierer, so dass wir, wenn wir den Vektor (dx1, dy1) um s skalieren, Punkt (x3, y3) und um t (x4, y4) erhalten. Wenn also entweder s oder t zwischen 0,0 und 1,0 liegt, dann liegt Punkt 3 oder 4 in unserer ersten Zeile. Negativ würde bedeuten, dass der Punkt hinter dem Anfang unseres Vektors liegt, während> 1,0 bedeutet, dass er weiter vor dem Ende unseres Vektors liegt. 0.0 bedeutet, dass es sich um (x1, y1) handelt und 1.0 bedeutet, dass es sich um (x2, y2) handelt. Wenn sowohl s als auch t <0.0 sind oder beide> 1.0 sind, überschneiden sie sich nicht. Und das behandelt den Sonderfall der parallelen Linien.

Nun, wenn det != 0.0 dann

s = det1 / det
t = det2 / det
if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0)
    return false  // no intersect

Dies ähnelt dem, was wir oben wirklich gemacht haben. Wenn wir nun den obigen Test bestehen, kreuzen sich unsere Liniensegmente und wir können den Schnitt ganz einfach wie folgt berechnen:

Ix = X1 + t * dx1
Iy = Y1 + t * dy1

Wenn Sie sich eingehender mit dem beschäftigen möchten, was die Mathematik leistet, schauen Sie sich Cramers Regel an.

0
Jason Hoffoss

wenn Ihre Daten eine Zeile definieren, müssen Sie nur nachweisen, dass sie nicht parallel sind. Dazu können Sie berechnen 

alpha = float(y2 - y1) / (x2 - x1).

Wenn dieser Koeffizient sowohl für Line1 als auch für Line2 gleich ist, bedeutet dies, dass die Linie parallel ist. Wenn nicht, bedeutet das, dass sie sich schneiden werden. 

Wenn sie parallel sind, müssen Sie beweisen, dass sie nicht gleich sind. Dafür berechnen Sie 

beta = y1 - alpha*x1

Wenn Beta für Line1 und Line2 gleich ist, bedeutet dies, dass Sie den Schnittpunkt der Linie überschneiden, da sie gleich sind

Wenn es sich um Segmente handelt, müssen Sie noch Alpha und Beta wie oben beschrieben für jede Zeile berechnen. Dann müssen Sie überprüfen, dass (beta1 - beta2)/(alpha1 - alpha2) größer als Min (x1_line1, x2_line1) und kleiner als Max (x1_line1, x2_line1) ist.

0
PierrOz

In Java implementiert. Es scheint jedoch, dass es nicht für ko-lineare Linien funktioniert.

public class TestCode
{

  public class Point
  {
    public double x = 0;
    public double y = 0;
    public Point(){}
  }

  public class Line
  {
    public Point p1, p2;
    public Line( double x1, double y1, double x2, double y2) 
    {
      p1 = new Point();
      p2 = new Point();
      p1.x = x1;
      p1.y = y1;
      p2.x = x2;
      p2.y = y2;
    }
  }

  //line segments
  private static Line s1;
  private static Line s2;

  public TestCode()
  {
    s1 = new Line(0,0,0,10);
    s2 = new Line(-1,0,0,10);
  }

  public TestCode(double x1, double y1, 
    double x2, double y2,
    double x3, double y3,
    double x4, double y4)
  {
    s1 = new Line(x1,y1, x2,y2);
    s2 = new Line(x3,y3, x4,y4);
  }

  public static void main(String args[])
  {
     TestCode code  = null;
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,10);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         5,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         0,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }

////////////////////////////
     code = new TestCode(0,0,10,10,
                         1,1,5,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         -1,-1,0,10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE END: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -10,10,10,-10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -3,-2,50,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         50,-2,-3,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         1,0,1,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,2,10,2,
                         0,10,10,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,10,5,13.75,
                         0,18.75,10,15);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         2,-1,2,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         -1,-10,-5,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); }
  }

  public static boolean intersect( TestCode code )
  {
    return intersect( code.s1, code.s2);
  }

  public static boolean intersect( Line line1, Line line2 )
  {
    double i1min = Math.min(line1.p1.x, line1.p2.x);
    double i1max = Math.max(line1.p1.x, line1.p2.x);
    double i2min = Math.min(line2.p1.x, line2.p2.x);
    double i2max = Math.max(line2.p1.x, line2.p2.x);

    double iamax = Math.max(i1min, i2min);
    double iamin = Math.min(i1max, i2max);

    if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) )
      return false;

    double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x );
    double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x );

    if( m1 == m2 )
        return false;

    //b1 = line1[0][1] - m1 * line1[0][0]
    //b2 = line2[0][1] - m2 * line2[0][0]
    double b1 = line1.p1.y - m1 * line1.p1.x;
    double b2 = line2.p1.y - m2 * line2.p1.x;
    double x1 = (b2 - b1) / (m1 - m2);
    if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) )
        return false;
    return true;
  }
}

Ausgabe ist soweit 

ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
OK SLOPE END: INTERSECTS
OK SLOPE Intersect(0,0): INTERSECTS
OK SLOPE Line2 VERTIAL: INTERSECTS
OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS
OK PARALLEL VERTICAL: DO NOT INTERSECT
OK PARALLEL HORIZONTAL: DO NOT INTERSECT
OK PARALLEL SLOPE=.75: DO NOT INTERSECT
OK SEPERATE SEGMENTS: DO NOT INTERSECT
OK SEPERATE SEGMENTS 2: DO NOT INTERSECT
0
Wanderer

Das ist was ich für AS3 habe, ich weiß nicht viel über Python, aber das Konzept ist da

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }
0
Daniel