Bagaimana cara memeriksa apakah dua segmen berpotongan?

Bagaimana cara memeriksa apakah 2 segmen berpotongan?

Saya memiliki data berikut:

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

Saya perlu menulis algoritma kecil dengan Python untuk mendeteksi jika 2 baris berpotongan.

Persamaan garis adalah:

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

Untuk segmen, itu persis sama, kecuali bahwa x disertakan pada interval I.

Jika Anda memiliki dua segmen, tentukan sebagai berikut:

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

Abcisse Xa dari titik potensial perpotongan (Xa, Ya) harus terdapat pada interval I1 dan I2, yang didefinisikan sebagai berikut:

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

Dan dapat dikatakan bahwa Xa termasuk dalam:

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

Sekarang, kita perlu memeriksa apakah interval ini ada:

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

Jadi, kami memiliki rumus dua garis, dan interval timbal balik. Rumus garis Anda adalah:

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

Karena kami mendapat dua poin berdasarkan segmen, kami dapat menentukan A1, A2, b1 dan b2:

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

Jika segmennya sejajar, maka A1 == A2:

if (A1 == A2):
    return False  # Parallel segments

Titik (Xa, Ya) yang berdiri di kedua garis harus memverifikasi kedua rumus f1 dan f2:

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

Hal terakhir yang harus dilakukan adalah memeriksa apakah Xa dimasukkan ke dalam Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

Selain itu, Anda dapat memeriksa saat startup bahwa dua dari empat poin yang disediakan tidak sama untuk menghindari semua pengujian itu.

Pengguna @ i_4_got menunjuk ke halaman ini dengan solusi yang sangat efisien dengan Python. Saya mereproduksinya di sini untuk kenyamanan (karena akan membuat saya senang memilikinya di sini):

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)

Anda tidak harus menghitung persis di mana segmen berpotongan, tetapi hanya memahami apakah segmen tersebut berpotongan sama sekali. Ini akan menyederhanakan solusinya.

Idenya adalah untuk memperlakukan satu segmen sebagai "jangkar" dan memisahkan segmen kedua menjadi 2 poin.
Sekarang, Anda harus menemukan posisi relatif setiap titik ke segmen "berlabuh" (OnLeft, OnRight, atau Collinear).
Setelah melakukannya untuk kedua titik, periksa apakah salah satu titik adalah OnLeft dan yang lainnya adalah OnRight (atau mungkin menyertakan posisi Collinear, jika Anda juga ingin menyertakan persimpangan yang tidak tepat ).

Anda kemudian harus mengulangi proses dengan peran jangkar dan segmen terpisah.

Persimpangan terjadi jika, dan hanya jika, salah satu titik adalah OnLeft dan yang lainnya adalah OnRight. Lihat tautan ini untuk penjelasan lebih detail dengan contoh gambar untuk setiap kemungkinan kasus.

Menerapkan metode seperti itu akan jauh lebih mudah daripada benar-benar menerapkan metode yang menemukan titik persimpangan (mengingat banyak kasus sudut yang harus Anda tangani juga).

Memperbarui

Fungsi berikut harus menggambarkan ide (sumber: Geometri Komputasi di C ).
Catatan: Contoh ini mengasumsikan penggunaan bilangan bulat. Jika Anda menggunakan representasi floating-point sebagai gantinya (yang jelas dapat memperumit masalah), maka Anda harus menentukan beberapa nilai epsilon untuk menunjukkan "kesetaraan" (kebanyakan untuk IsCollinearevaluasi).

// 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);
}

Tentu saja, saat menggunakan fungsi-fungsi ini, kita harus ingat untuk memeriksa bahwa setiap segmen terletak "di antara" segmen lainnya (karena ini adalah segmen berhingga, dan bukan garis tak hingga).

Selain itu, dengan menggunakan fungsi ini Anda dapat memahami apakah Anda memiliki persimpangan yang tepat atau tidak tepat .

• Benar : Tidak ada titik collinear. Segmen tersebut saling silang "dari sisi ke sisi".
• Tidak tepat : Satu segmen hanya "menyentuh" ​​yang lain (setidaknya satu titik bertabrakan dengan segmen yang ditambatkan).

Misalkan kedua segmen memiliki titik akhir A, B dan C, D. Cara yang tepat secara numerik untuk menentukan persimpangan adalah dengan memeriksa tanda dari empat faktor penentu:

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

Untuk perpotongan, setiap determinan di sebelah kiri harus memiliki tanda kebalikan dari yang satu ke kanan, tetapi tidak perlu ada hubungan antara kedua garis tersebut. Anda pada dasarnya memeriksa setiap titik dari suatu segmen terhadap segmen lainnya untuk memastikannya terletak pada sisi berlawanan dari garis yang ditentukan oleh segmen lainnya.

Lihat di sini: http://www.cs.cmu.edu/~quake/robust.html

Memeriksa apakah segmen garis berpotongan sangat mudah dengan pustaka Shapely menggunakan intersectsmetode:

from shapely.geometry import LineString

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

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

Berdasarkan jawaban luar biasa Liran dan Grumdrig, berikut adalah kode Python lengkap untuk memverifikasi apakah segmen tertutup memang berpotongan. Berfungsi untuk segmen collinear, segmen sejajar dengan sumbu Y, segmen degenerasi (lebih detail). Mengasumsikan koordinat integer. Koordinat titik apung memerlukan modifikasi pada uji kesetaraan titik.

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

Berikut solusi menggunakan produk titik:

# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
    dx0 = s0[1][0]-s0[0][0]
    dx1 = s1[1][0]-s1[0][0]
    dy0 = s0[1][1]-s0[0][1]
    dy1 = s1[1][1]-s1[0][1]
    p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
    p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
    p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
    p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
    return (p0*p1<=0) & (p2*p3<=0)

Berikut adalah visualisasi di Desmos: Persimpangan Segmen Garis

Anda memiliki dua segmen garis. Tentukan satu segmen dengan titik akhir A & B dan segmen kedua dengan titik akhir C & D. Ada trik bagus untuk menunjukkan bahwa mereka harus berpotongan, DALAM batas-batas segmen tersebut. (Perhatikan bahwa garis itu sendiri mungkin berpotongan di luar batas segmen, jadi Anda harus berhati-hati. Kode yang baik juga akan memperhatikan garis paralel.)

Triknya adalah dengan menguji bahwa titik A dan B harus berbaris pada sisi berlawanan dari garis CD, AND bahwa titik C dan D harus terletak pada sisi berlawanan dari garis AB.

Karena ini pekerjaan rumah, saya tidak akan memberi Anda solusi eksplisit. Tetapi tes sederhana untuk melihat sisi garis mana sebuah titik berada, adalah dengan menggunakan perkalian titik. Jadi, untuk CD baris tertentu, hitung vektor normal ke baris itu (saya akan menyebutnya N_C.) Sekarang, cukup uji tanda dari dua hasil ini:

dot(A-C,N_C)

dan

dot(B-C,N_C)

Jika hasil tersebut memiliki tanda yang berlawanan, maka A dan B adalah sisi berlawanan dari garis CD. Sekarang lakukan tes yang sama untuk jalur lainnya, AB. Ini memiliki vektor normal N_A. Bandingkan tanda-tanda

dot(C-A,N_A)

dan

dot(D-A,N_A)

Saya serahkan kepada Anda untuk mencari cara menghitung vektor normal. (Dalam 2-d, itu sepele, tetapi apakah kode Anda akan mengkhawatirkan apakah A dan B adalah titik yang berbeda? Begitu juga, apakah C dan D berbeda?)

Anda masih perlu mengkhawatirkan ruas garis yang berada di sepanjang garis tak hingga yang sama, atau jika satu titik benar-benar jatuh di ruas garis lainnya. Kode yang baik akan memenuhi setiap kemungkinan masalah.

Berikut adalah kode C untuk memeriksa apakah dua titik berada di sisi berlawanan dari ruas garis. Dengan menggunakan kode ini Anda dapat memeriksa apakah dua segmen juga berpotongan.

// 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));

}

Berikut adalah kode python lain untuk memeriksa apakah segmen tertutup berpotongan. Ini adalah versi kode C ++ yang ditulis ulang di http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ . Implementasi ini mencakup semua kasus khusus (mis. Semua poin berkolini).

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

Di bawah ini adalah fungsi uji untuk memverifikasi bahwa itu berfungsi.

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

untuk segmen AB dan CD, carilah kemiringan CD

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

perpanjang CD di atas A dan B, dan ambil jarak ke CD lurus ke atas

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

periksa apakah mereka berada di sisi yang berlawanan

return dist1*dist2<0

Karena Anda tidak menyebutkan bahwa Anda ingin mencari titik potong dari garis tersebut, masalahnya menjadi lebih sederhana untuk diselesaikan. Jika Anda membutuhkan titik potong, maka jawaban OMG_peanuts adalah pendekatan yang lebih cepat. Namun, jika Anda hanya ingin mencari apakah garis tersebut berpotongan atau tidak, Anda dapat melakukannya dengan menggunakan persamaan garis (ax + by + c = 0). Pendekatannya adalah sebagai berikut:

1. Mari kita mulai dengan dua segmen garis: segmen 1 dan segmen 2.

   segment1 = [[x1,y1], [x2,y2]]
   segment2 = [[x3,y3], [x4,y4]]
   

2. Periksa apakah dua segmen garis adalah garis panjang bukan nol dan segmen berbeda.

3. Dari sini, saya berasumsi bahwa kedua segmen itu panjangnya bukan nol dan berbeda. Untuk setiap ruas garis, hitung kemiringan garisnya lalu dapatkan persamaan garis berupa ax + by + c = 0. Sekarang, hitung nilai f = ax + by + c untuk dua titik dari ruas garis lainnya (ulangi ini untuk ruas garis lainnya juga).

   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. Sekarang yang tersisa hanyalah kasus yang berbeda. Jika f = 0 untuk suatu titik, maka kedua garis tersebut akan bersentuhan. Jika f1_1 dan f1_2 sama atau f2_1 dan f2_2 sama, maka garis tidak berpotongan. Jika f1_1 dan f1_2 tidak sama dan f2_1 dan f2_2 tidak sama, maka segmen garis berpotongan. Bergantung pada apakah Anda ingin mempertimbangkan garis yang bersentuhan sebagai "berpotongan" atau tidak, Anda dapat menyesuaikan kondisi Anda.

Kita juga bisa menyelesaikan ini dengan memanfaatkan vektor.

Mari definisikan segmen sebagai [start, end]. Diberikan dua segmen seperti itu [A, B]dan [C, D]keduanya memiliki panjang bukan nol, kita dapat memilih salah satu titik ujung untuk digunakan sebagai titik referensi sehingga kita mendapatkan tiga vektor:

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

Dari sana, kita bisa mencari persimpangan dengan menghitung t dan u in p + t*r = u*q. Setelah bermain-main dengan persamaan sedikit, kita mendapatkan:

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]

Jadi, fungsinya adalah:

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

Ini adalah cara saya memeriksa perlintasan garis dan di mana persimpangan itu terjadi. Mari kita gunakan x1 sampai x4 dan y1 sampai y4

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

Kemudian kita membutuhkan beberapa vektor untuk mewakilinya

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

Sekarang kita lihat determinannya

det = dx1 * dy2 - dx2 * dy1

Jika determinannya 0,0, maka segmen garisnya sejajar. Ini bisa berarti mereka tumpang tindih. Jika mereka tumpang tindih hanya di titik akhir, maka ada satu solusi persimpangan. Jika tidak, akan ada solusi tak terbatas. Dengan solusi yang tak terhingga banyaknya, apa yang dikatakan titik persimpangan Anda? Jadi ini kasus khusus yang menarik. Jika Anda mengetahui sebelumnya bahwa garis tidak boleh tumpang tindih maka Anda dapat memeriksa apakah det == 0.0dan jika demikian, katakan saja garis tersebut tidak berpotongan dan selesai. Jika tidak, mari lanjutkan

dx3 = X3 - X1
dy3 = Y3 - Y1

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

Sekarang, jika det, det1 dan det2 semuanya nol, maka garis Anda co-linear dan bisa tumpang tindih. Jika det nol tetapi det1 atau det2 tidak, maka keduanya bukan co-linear, tetapi sejajar, jadi tidak ada perpotongan. Jadi apa yang tersisa sekarang jika det nol adalah masalah 1D, bukan 2D. Kita perlu memeriksa salah satu dari dua cara, tergantung apakah dx1 adalah nol atau tidak (sehingga kita dapat menghindari pembagian dengan nol). Jika dx1 adalah nol maka lakukan logika yang sama dengan nilai y daripada x di bawah.

s = X3 / dx1
t = X4 / dx1

Ini menghitung dua skala, sehingga jika kita menskalakan vektor (dx1, dy1) dengan s kita mendapatkan titik (x3, y3), dan dengan t kita mendapatkan (x4, y4). Jadi jika s atau t antara 0,0 dan 1,0, maka titik 3 atau 4 terletak di baris pertama kita. Negatif berarti titik berada di belakang awal vektor kita, sedangkan> 1,0 berarti lebih jauh di depan akhir vektor kita. 0,0 berarti berada pada (x1, y1) dan 1,0 berarti pada (x2, y2). Jika s dan t keduanya <0.0 atau keduanya> 1.0, maka keduanya tidak berpotongan. Dan itu menangani kasus khusus garis paralel.

Sekarang, jika det != 0.0kemudian

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

Ini mirip dengan apa yang kami lakukan di atas sebenarnya. Sekarang jika kita lulus tes di atas, maka ruas garis kita berpotongan, dan kita bisa menghitung perpotongan dengan mudah seperti ini:

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

Jika Anda ingin menggali lebih dalam tentang apa yang dilakukan matematika, lihat Aturan Cramer.

Sejauh ini, jawaban Georgy adalah yang terbersih untuk diterapkan. Harus mengejar ini, karena contoh brycboe, meskipun sederhana juga, memiliki masalah dengan colinearity.

Kode untuk pengujian:

#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# /programming/3838329/how-can-i-check-if-two-segments-intersect

from shapely.geometry import LineString

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

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

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)


def ShapelyIntersect(A,B,C,D):
    return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))


a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)

'''
Test points:

b(0,1)   c(1,1)




a(0,0)   d(1,0)
'''

# F
print(intersect(a,b,c,d))

# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))

# F
print(intersect(a,d,b,c))

# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))

print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))

jika data Anda menentukan garis, Anda hanya perlu membuktikan bahwa garis tersebut tidak sejajar. Untuk melakukan ini, Anda dapat menghitung

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

Jika koefisien ini sama untuk Garis1 dan Garis2, itu berarti garis tersebut sejajar. Jika tidak, berarti mereka akan berpotongan.

Jika mereka sejajar maka Anda harus membuktikan bahwa mereka tidak sama. Untuk itu, Anda menghitung

beta = y1 - alpha*x1

Jika beta sama untuk Garis1 dan Garis2, itu berarti garis Anda berpotongan karena sama

Jika mereka segment, Anda masih harus menghitung alpha dan beta seperti yang dijelaskan di atas untuk setiap Line. Maka Anda harus memeriksa bahwa (beta1 - beta2) / (alpha1 - alpha2) lebih besar dari Min (x1_line1, x2_line1) dan kurang dari Max (x1_line1, x2_line1)

Hitung titik potong dari garis-garis yang berada di segmen Anda (pada dasarnya berarti menyelesaikan sistem persamaan linier), lalu periksa apakah itu berada di antara titik awal dan akhir segmen Anda.

Inilah yang saya dapatkan untuk AS3, tidak tahu banyak tentang python tetapi konsepnya ada

    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();
    }

Diterapkan di JAVA. Namun tampaknya itu tidak berfungsi untuk garis co-linear (alias segmen garis yang ada di dalam satu sama lain L1 (0,0) (10,10) L2 (1,1) (2,2)

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;
  }
}

Output sejauh ini

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

Saya pikir saya akan menyumbangkan solusi Swift yang bagus:

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

}

Salah satu solusi di atas bekerja dengan sangat baik sehingga saya memutuskan untuk menulis program demonstrasi lengkap menggunakan wxPython. Anda harus dapat menjalankan program ini seperti ini: python " nama file Anda "

# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.

import wx

class Point:
    def __init__(self, newX, newY):
        self.x = newX
        self.y = newY

app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0


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)

def is_intersection(p1, p2, p3, p4):
    return intersect(p1, p2, p3, p4)

def drawIntersection(pc):
    mp2 = Point(highestX, mp.y)
    if is_intersection(p1, p2, mp, mp2):
        pc.DrawText("intersection", 10, 10)
    else:
        pc.DrawText("no intersection", 10, 10)

def do_paint(evt):
    pc = wx.PaintDC(frame)
    pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
    pc.DrawLine(mp.x, mp.y, highestX, mp.y)
    drawIntersection(pc)

def do_left_mouse(evt):
    global mp, highestX
    point = evt.GetPosition()
    mp = Point(point[0], point[1])
    highestX = frame.Size[0]
    frame.Refresh()

frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()

Menggunakan solusi OMG_Peanuts , saya menerjemahkan ke SQL. (Fungsi Skalar HANA)

Terima kasih OMG_Peanuts, hasilnya bagus. Saya menggunakan bumi bulat, tetapi jaraknya kecil, jadi menurut saya tidak masalah.

FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
         IN LONG_A1 DOUBLE,
         IN LAT_A2 DOUBLE,
         IN LONG_A2 DOUBLE,
         IN LAT_B1 DOUBLE,
         IN LONG_B1 DOUBLE,
         IN LAT_B2 DOUBLE,
         IN LONG_B2 DOUBLE) 
    
RETURNS RET_DOESINTERSECT DOUBLE
    LANGUAGE SQLSCRIPT
    SQL SECURITY INVOKER AS
BEGIN

    DECLARE MA DOUBLE;
    DECLARE MB DOUBLE;
    DECLARE BA DOUBLE;
    DECLARE BB DOUBLE;
    DECLARE XA DOUBLE;
    DECLARE MAX_MIN_X DOUBLE;
    DECLARE MIN_MAX_X DOUBLE;
    DECLARE DOESINTERSECT INTEGER;
    
    SELECT 1 INTO DOESINTERSECT FROM DUMMY;
    
    IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
        SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY; 
        SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
        IF MA = MB THEN
            SELECT 0 INTO DOESINTERSECT FROM DUMMY;
        END IF;
    END IF;
    
    SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
    SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
    SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
    
    -- Max of Mins
    IF LAT_A1 < LAT_A2 THEN         -- MIN(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 > LAT_B1 THEN       -- MAX(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 > LAT_B2 THEN       -- MAX(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 < LAT_A1 THEN     -- MIN(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 > LAT_B1 THEN       -- MAX(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 > LAT_B2 THEN       -- MAX(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
    
    -- Min of Max
    IF LAT_A1 > LAT_A2 THEN         -- MAX(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 < LAT_B1 THEN       -- MIN(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 < LAT_B2 THEN       -- MIN(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 > LAT_A1 THEN     -- MAX(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 < LAT_B1 THEN       -- MIN(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 < LAT_B2 THEN       -- MIN(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
        
    
    IF XA < MAX_MIN_X OR
       XA > MIN_MAX_X THEN  
       SELECT 0 INTO DOESINTERSECT FROM DUMMY;
    END IF;
    
    RET_DOESINTERSECT := :DOESINTERSECT;
END;

Terselesaikan tetapi mengapa tidak dengan python ... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

Ini:

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

Keluaran:

True

Dan ini:

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

Keluaran:

False