Bagaimana Anda mendeteksi di mana dua segmen garis berpotongan? [Tutup]

518

Bagaimana cara menentukan apakah dua garis berpotongan atau tidak, dan jika ada, pada titik x, y apa?

KingNestor
sumber
Mungkin membantu untuk memikirkan tepi-tepi persegi panjang sebagai garis-garis yang terpisah daripada poligon lengkap.
Ryan Graham
Catatan Moderator : diskusi apakah posting ini tentang topik termasuk pada Meta Stack Overflow Komentar lebih lanjut tentang ini di sini akan dihapus.
Martijn Pieters

Jawaban:

659

Ada pendekatan yang bagus untuk masalah ini yang menggunakan produk lintas vektor. Tentukan vektor lintas produk 2-dimensi v  ×  w menjadi v x  w y  -  v y  w x .

Misalkan dua segmen garis dijalankan dari p ke p  +  r dan dari q ke q  +  s . Kemudian setiap titik pada baris pertama direpresentasikan sebagai p  +  t  r (untuk parameter skalar  t ) dan setiap titik pada baris kedua sebagai q  +  u  s (untuk parameter skalar  u ).

Dua segmen garis berpotongan

Dua garis berpotongan jika kita dapat menemukan t dan u sedemikian rupa sehingga:

p + t  r = q + u  s

Rumus untuk titik persimpangan

Seberangi kedua sisi dengan s , dapatkan

( p + t  r ) × s = ( q + u  s ) × s

Dan karena s  ×  s = 0, ini berarti

t  ( r × s ) = ( q - p ) × s

Dan karena itu, penyelesaian untuk t :

t = ( q - p ) × s / ( r × s )

Dengan cara yang sama, kita bisa menyelesaikannya untuk Anda :

( p + t  r ) × r = ( q + u  s ) × r

u  ( s × r ) = ( p - q ) × r

u = ( p - q ) × r / ( s × r )

Untuk mengurangi jumlah langkah perhitungan, lebih mudah untuk menulis ulang ini sebagai berikut (mengingat bahwa s  ×  r = -  r  ×  s ):

kamu = ( q - p ) × r / ( r × s )

Sekarang ada empat kasus:

  1. Jika r  ×  s  = 0 dan ( q  -  p ) ×  r  = 0, maka kedua garis tersebut adalah collinear.

    Dalam hal ini, ungkapkan titik akhir segmen kedua ( q dan q  +  s ) dalam hal persamaan segmen baris pertama ( p + t r ):

    t 0 = ( q - p ) ·  r / ( r  ·  r )

    t 1 = ( q + s - p ) ·  r / ( r  ·  r ) = t 0 + s  ·  r / ( r  ·  r )

    Jika interval antara t 0 dan t 1 memotong interval [0, 1] maka segmen garisnya adalah linier dan tumpang tindih; kalau tidak mereka collinear dan terputus-putus.

    Perhatikan bahwa jika s dan r menunjuk ke arah yang berlawanan, maka s  ·  r <0 sehingga interval yang akan diperiksa adalah [ t 1 , t 0 ] daripada [ t 0 , t 1 ].

  2. Jika r  ×  s  = 0 dan ( q  -  p ) ×  r  ≠ 0, maka kedua garis itu paralel dan tidak berpotongan.

  3. Jika r  ×  s  ≠ 0 dan 0 ≤  t  ≤ 1 dan 0 ≤  u  ≤ 1, dua segmen garis bertemu pada titik p + t  r = q + u  s .

  4. Jika tidak, dua segmen garis tidak paralel tetapi tidak berpotongan.

Kredit: metode ini adalah spesialisasi 2 dimensi dari algoritma persimpangan garis 3D dari artikel "Persimpangan dua garis dalam tiga ruang" oleh Ronald Goldman, diterbitkan dalam Graphics Gems , halaman 304. Dalam tiga dimensi, kasus yang umum adalah bahwa garis-garisnya miring (tidak paralel atau berpotongan) dalam hal ini metode ini memberikan titik-titik pendekatan terdekat dari dua garis.

Gareth Rees
sumber
5
@ myrkos: Tidak. Segmen baris pertama berjalan "dari p ke p + r" jadi ketika direpresentasikan dalam istilah parametrik sebagai "p + tr" maka segmen tersebut bersesuaian dengan 0 ≤ t ≤ 1. Demikian pula untuk segmen lainnya.
Gareth Rees
7
Gareth, saya merasa seperti saya harus kehilangan sesuatu, tetapi bagaimana Anda membagi (vektor) dengan vektor? Solusi Anda untuk t dan u diakhiri dengan / (r × s), tetapi (r × s)merupakan vektor, kan? Sebuah vektor (0, 0, rx * sy - ry * sx). Dan sisi kiri juga mirip dengan vektor sejajar dengan sumbu z. Jadi ... apakah saya hanya membagi komponen z dengan komponen z lainnya? Apakah rumus untuk t sebenarnya |(q − p) × s| / |(r × s)|?
LarsH
7
@ LarsH: lihat paragraf pertama.
Gareth Rees
35
Bagi mereka yang tertarik, berikut ini adalah implementasi C # sederhana, mengambil titik awal dan akhir koordinat untuk garis, yang tampaknya bekerja: ideone.com/PnPJgb
Matt
24
Saya mengumpulkan implementasi JavaScript berikut @Matt. Saya membuat koreksi untuk kesalahan yang ditunjukkan oleh Tekito.
pgkelley
230

FWIW, fungsi berikut (dalam C) mendeteksi garis persimpangan dan menentukan titik persimpangan. Ini didasarkan pada suatu algoritma dalam Andre LeMothe's " Tricks of the Windows Game Programming Gurus ". Ini tidak berbeda dengan beberapa algoritma dalam jawaban lain (misalnya Gareth). LeMothe kemudian menggunakan Aturan Cramer (jangan tanya saya) untuk menyelesaikan persamaan sendiri.

Saya bisa membuktikan bahwa itu bekerja di klon asteroid saya yang lemah, dan tampaknya menangani dengan benar kasus tepi yang dijelaskan dalam jawaban lain oleh Elemental, Dan dan Wodzu. Ini juga mungkin lebih cepat daripada kode yang diposting oleh KingNestor karena semuanya perkalian dan pembagian, tidak ada akar kuadrat!

Saya kira ada beberapa potensi untuk membagi dengan nol di sana, meskipun itu tidak menjadi masalah dalam kasus saya. Cukup mudah untuk memodifikasi untuk menghindari crash.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

BTW, saya harus mengatakan bahwa dalam buku LeMothe, meskipun ia tampaknya mendapatkan algoritme yang benar, contoh konkret ia menunjukkan colokan angka yang salah dan melakukan perhitungan yang salah. Sebagai contoh:

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

= 844 / 0,88

= 0,44

Itu membingungkan saya selama berjam - jam . :(

Gavin
sumber
9
fungsi getLineIntersection (p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x, p3_y) {var s1_x, s1_y, s1_y, s2_x, s2_y; s1_x = p1_x - p0_x; s1_y = p1_y - p0_y; s2_x = p3_x - p2_x; s2_y = p3_y - p2_y; var s, t; s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y); t = (s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
cortijon

5
if (s> = 0 && s <= 1 && t> = 0 && t <= 1) {// Tabrakan terdeteksi var intX = p0_x + (t * s1_x); var intY = p0_y + (t * s1_y); return [intX, intY]; } mengembalikan nol; // Tidak ada tabrakan}
cortijon
13
Algoritma yang baik, tetapi karena itu tidak menangani kasus-kasus di mana penentu adalah 0. (-s2_x * s1_y + s1_x * s2_y di atas). Jika 0 (atau mendekati 0) garis-garisnya paralel atau collinear. Jika collinear maka persimpangan mungkin merupakan segmen garis lain.
seand
16
Operasi dua divisi dapat dihindari karena kecepatan (biaya divisi lebih dari multiplikasi); jika garis berpotongan Anda perlu satu divisi, jika mereka tidak memotong Anda perlu nol. Pertama-tama seseorang harus menghitung penyebut dan berhenti lebih awal jika itu nol (mungkin menambahkan kode untuk mendeteksi kolinearitas.) Selanjutnya, alih-alih menghitung sdan tsecara langsung, uji hubungan antara dua pembilang dan penyebut. Hanya jika garis dikonfirmasi untuk memotong apakah Anda benar-benar perlu menghitung nilai t(tetapi tidak s).
Qwertie
18
Saya melakukan pengujian kinerja pada semua algoritma yang diposting di sini, dan yang ini setidaknya dua kali lebih cepat dari yang lain. Terima kasih untuk posting!
lajos
63

Masalahnya berkurang menjadi pertanyaan ini: Apakah dua garis dari A ke B dan dari C ke D berpotongan? Kemudian Anda bisa menanyakannya empat kali (antara garis dan masing-masing dari empat sisi persegi panjang).

Inilah vektor matematika untuk melakukannya. Saya mengasumsikan garis dari A ke B adalah garis yang dimaksud dan garis dari C ke D adalah salah satu garis persegi panjang. Notasi saya adalah Ax"koordinat x A" dan Cy"koordinat y" C. Dan " *" berarti produk titik, jadi mis A*B = Ax*Bx + Ay*By.

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

hNomor ini adalah kuncinya. Jika hberada di antara 0dan 1, garis-garis berpotongan, jika tidak, maka garis tersebut tidak. Jika F*Pnol, tentu saja Anda tidak dapat membuat perhitungan, tetapi dalam kasus ini garisnya paralel dan karena itu hanya berpotongan dalam kasus yang jelas.

Titik perpotongan yang tepat adalah C + F*h.

Lebih menyenangkan:

Jika hadalah persis 0 atau 1garis menyentuh pada titik akhir. Anda dapat menganggap ini "persimpangan" atau tidak sesuai keinginan Anda.

Secara khusus, hadalah berapa banyak Anda harus mengalikan panjang garis agar dapat menyentuh garis lainnya secara tepat.

Oleh karena itu, Jika h<0, itu berarti garis persegi panjang adalah "di belakang" garis yang diberikan (dengan "arah" adalah "dari A ke B"), dan jika h>1garis persegi panjang "di depan" dari garis yang diberikan.

Penurunan:

A dan C adalah vektor yang menunjuk ke awal garis; E dan F adalah vektor dari ujung A dan C yang membentuk garis.

Untuk setiap dua garis non-paralel dalam pesawat, harus ada tepat satu pasang skalar gdan hsedemikian rupa sehingga persamaan ini berlaku:

A + E*g = C + F*h

Mengapa? Karena dua garis non-paralel harus berpotongan, yang berarti Anda dapat menskalakan kedua garis dengan jumlah masing-masing dan saling menyentuh.

( Pada awalnya ini terlihat seperti persamaan tunggal dengan dua yang tidak diketahui! Tetapi tidak ketika Anda menganggap bahwa ini adalah persamaan vektor 2D, yang berarti ini benar-benar pasangan persamaan dalam xdan y.)

Kami harus menghilangkan salah satu dari variabel-variabel ini. Cara mudah adalah membuat Eistilah nol. Untuk melakukan itu, ambil titik-produk dari kedua sisi persamaan menggunakan vektor yang akan dot ke nol dengan E. Vektor yang saya sebut di Patas, dan saya melakukan transformasi yang jelas dari E.

Anda sekarang memiliki:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h
Jason Cohen
sumber
29
Algoritma ini bagus. Tetapi ada lubang di dalamnya seperti yang ditunjukkan oleh Dan @ stackoverflow.com/questions/563198/… & Elemental @ stackoverflow.com/questions/563198/... Akan lebih keren jika Anda akan memperbarui jawaban Anda untuk referensi di masa mendatang. Terima kasih.
Chantz
2
Apakah algoritma ini stabil secara numerik? Saya sudah mencoba pendekatan yang serupa dan ternyata memberikan hasil yang aneh ketika mengerjakan floats.
milosz
3
Tampaknya ada masalah lain dengan algoritma ini. Ketika diberi titik A = {1, 0} B = {2, 0} C = {0, 0} D = {1,0}, meskipun segmen garis dengan jelas menyentuh pada akhirnya, F P (dan juga E Q, sejalan dengan perbaikan pengguna di bawah) keduanya 0, sehingga menyebabkan pembagian dengan 0 untuk menemukan h dan g. Masih bekerja pada solusi untuk yang satu ini, tapi saya pikir masalahnya layak untuk ditunjukkan.
candrews
12
Jawaban ini tidak benar. Coba A = {0,0}, B = {0,1}, C = {0,2} D = {2,0}
Tim Cooper
6
A + E*g = C + F*hDua garis berpotongan jika dan hanya jika solusi untuk persamaan itu (dengan asumsi mereka tidak paralel) memiliki keduanya, gdanh antara 0 dan 1 (eksklusif atau eksklusif, tergantung pada apakah Anda menghitung menyentuh pada titik akhir).
Daniel Fischer
46

Saya telah mencoba mengimplementasikan algoritme yang dijelaskan secara elegan oleh Jason di atas; sayangnya saat bekerja melalui matematika di debugging saya menemukan banyak kasus yang tidak berhasil.

Sebagai contoh, pertimbangkan poin A (10,10) B (20,20) C (10,1) D (1,10) memberikan h = 0,5, namun jelas dengan memeriksa bahwa segmen-segmen ini tidak-berada di dekat masing-masing lain.

Grafik ini memperjelas bahwa 0 <h <1 kriteria hanya menunjukkan bahwa titik potong akan terletak pada CD jika ada tetapi tidak memberi tahu apakah titik itu terletak pada AB. Untuk memastikan bahwa ada titik silang Anda harus melakukan perhitungan simetris untuk variabel g dan persyaratan untuk intersepsi adalah: 0 <g <1 DAN 0 <h <1

Elemental
sumber
2
Saya sudah mencabut rambut saya mencoba mencari tahu mengapa jawaban yang diterima tidak bekerja untuk saya. Terima kasih banyak!
Matt Bridges
1
Juga penting bahwa kondisi batas berfungsi dalam kasus ini (yaitu untuk h = 0 atau h = 1 atau g = 0 atau g = 1 garis 'hanya' sentuh
Elemental
Untuk orang-orang yang mengalami kesulitan dalam memvisualisasikan hasilnya, saya telah mengimplementasikan ini dalam Javascript: jsfiddle.net/ferrybig/eokwL9mp
Ferrybig
45

Inilah peningkatan jawaban Gavin. Solusi marcp juga serupa, tetapi tidak ada yang menunda pembagian.

Ini sebenarnya ternyata menjadi aplikasi praktis dari jawaban Gareth Rees juga, karena padanan produk-silang dalam 2D ​​adalah produk pel-dot, yang mana kode ini menggunakan tiga darinya. Beralih ke 3D dan menggunakan produk silang, menginterpolasi s dan t pada akhirnya, menghasilkan dua titik terdekat di antara garis-garis dalam 3D. Bagaimanapun, solusi 2D:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

Pada dasarnya itu menunda pembagian sampai saat terakhir, dan memindahkan sebagian besar tes sampai sebelum perhitungan tertentu dilakukan, sehingga menambah awal. Akhirnya, ia juga menghindari pembagian dengan case nol yang terjadi ketika garis-garisnya paralel.

Anda juga mungkin ingin mempertimbangkan untuk menggunakan tes epsilon daripada membandingkannya dengan nol. Garis yang sangat dekat dengan paralel dapat menghasilkan hasil yang sedikit tidak aktif. Ini bukan bug, ini adalah batasan dengan matematika floating point.

iMalc
sumber
1
Gagal jika beberapa poin memiliki nilai 0 .. yang seharusnya tidak terjadi kan?
hfossli
1
Saya telah membuat koreksi untuk bug yang diperkenalkan saat menunda pembagian. t bisa positif ketika angka dan denom keduanya negatif.
iMalc
2
Tidak berfungsi jika p0-p1 adalah vertikal dan p2-p3 adalah horisontal dan dua segmen bersilangan. (pengembalian pertama dilakukan)
Fabio Dalla Libera
Case coolinear memiliki dua kemungkinan: non onverlapping dan overlapping. Yang pertama harus mengembalikan false yang kedua benar. Dalam kode Anda ini tidak diuji. selalu menghasilkan false karena sebagian besar jawaban di sini. Sayang sekali tidak ada solusi yang benar-benar berhasil.
AlexWien
3
Bisakah Anda mencerahkan saya mengapa semua ini menggunakan nama-nama variabel yang tidak jelas seperti s32_ybukan sesuatu yang menggambarkan seperti apa itu point2YDifference?
Supuhstar
40

Pertanyaan C: Bagaimana Anda mendeteksi apakah dua segmen garis berpotongan atau tidak?

Saya telah mencari topik yang sama, dan saya tidak senang dengan jawabannya. Jadi saya telah menulis sebuah artikel yang menjelaskan dengan sangat rinci cara memeriksa apakah dua segmen garis bersinggungan dengan banyak gambar. Ada kode Java yang lengkap (dan teruji).

Inilah artikelnya, yang dipangkas ke bagian paling penting:

Algoritma, yang memeriksa apakah segmen garis a bersinggungan dengan segmen garis b, terlihat seperti ini:

Masukkan deskripsi gambar di sini

Apa itu kotak pembatas? Berikut adalah dua kotak pembatas dari dua segmen garis:

masukkan deskripsi gambar di sini

Jika kedua kotak pembatas memiliki persimpangan, Anda memindahkan segmen garis sehingga satu titik berada pada (0 | 0). Sekarang Anda memiliki garis melalui titik asal yang ditentukan oleh a. Sekarang pindahkan ruas garis b dengan cara yang sama dan periksa apakah titik baru ruas garis b berada di sisi garis yang berbeda a. Jika ini masalahnya, periksa sebaliknya. Jika ini juga kasusnya, segmen garis berpotongan. Jika tidak, mereka tidak berpotongan.

Pertanyaan A: Di mana dua segmen garis berpotongan?

Anda tahu bahwa dua segmen garis a dan b berpotongan. Jika Anda tidak tahu itu, periksa dengan alat yang saya berikan di "Pertanyaan C".

Sekarang Anda dapat melewati beberapa kasus dan mendapatkan solusinya dengan matematika kelas 7 (lihat kode dan contoh interaktif ).

Pertanyaan B: Bagaimana Anda mendeteksi apakah dua garis berpotongan atau tidak?

Katakanlah titik A = (x1, y1), titik B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Baris pertama Anda didefinisikan oleh AB (dengan A! = B), dan yang kedua dengan CD (dengan C! = D).

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // Both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;
    }
}

Pertanyaan D: Di mana dua garis berpotongan?

Periksa dengan Pertanyaan B apakah keduanya bersinggungan.

Garis a dan b didefinisikan oleh dua titik untuk setiap garis. Anda pada dasarnya dapat menerapkan logika yang sama dengan yang digunakan pada Pertanyaan A.

Martin Thoma
sumber
15
Agar jelas, Pertanyaan B dalam jawaban ini benar-benar tentang dua garis yang memotong, bukan segmen garis. Saya tidak mengeluh; itu tidak salah. Hanya saja, tidak ingin orang disesatkan.
phord
1
Tidak ada "pertanyaan C". Dan Pertanyaan D hanya memantul kembali ke Pertanyaan A.
Konrad Viltersten
21

Jawaban yang pernah diterima di sini salah (sejak itu tidak dapat diterima, jadi hore!). Itu tidak benar menghilangkan semua non-persimpangan. Sepele mungkin terlihat berfungsi tetapi bisa gagal, terutama dalam hal 0 dan 1 dianggap valid untuk h.

Pertimbangkan kasus berikut:

Baris di (4,1) - (5,1) dan (0,0) - (0,2)

Ini adalah garis tegak lurus yang jelas tidak tumpang tindih.

A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) titik (0,1) / ((0) , -2) titik (0,1)) = 0

Menurut jawaban di atas, dua segmen garis ini bertemu pada titik akhir (nilai 0 dan 1). Titik akhir itu adalah:

(0,0) + (0, -2) * 0 = (0,0)

Jadi, tampaknya dua segmen garis bertemu pada (0,0), yang ada di CD line, tetapi tidak pada baris AB. Jadi apa yang salah? Jawabannya adalah bahwa nilai 0 dan 1 tidak valid dan hanya terkadang TERJADI untuk memprediksi persimpangan titik akhir dengan benar. Ketika ekstensi satu baris (tetapi tidak yang lain) akan memenuhi segmen garis, algoritme memprediksi persimpangan segmen garis, tetapi ini tidak benar. Saya membayangkan bahwa dengan pengujian dimulai dengan AB vs CD dan kemudian juga pengujian dengan CD vs AB, masalah ini akan dihilangkan. Hanya jika keduanya jatuh antara 0 dan 1 secara inklusif mereka dapat dikatakan berpotongan.

Saya sarankan menggunakan metode lintas produk vektor jika Anda harus memprediksi titik akhir.

-Dan

Dan
sumber
4
Jawaban "diterima" dapat berubah, jadi Anda harus menyebutnya sesuatu yang lain. (Sebenarnya, saya pikir itu sudah berubah sejak komentar Anda)
Johannes Hoff
14

Jawaban iMalc versi python:

def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision


    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]


    return intersection_point
Keris
sumber
Ingatlah bahwa Anda perlu membuat angka Anda mengapung atau mengubah baris 8 untuk digunakandenom = float(...)
Jonno_FTW
11

Menemukan persimpangan dua segmen garis yang benar adalah tugas yang tidak sepele dengan banyak kasing tepi. Berikut adalah solusi yang terdokumentasi, berfungsi dan teruji di Jawa.

Intinya, ada tiga hal yang bisa terjadi ketika menemukan persimpangan dua segmen garis:

  1. Segmen tidak berpotongan

  2. Ada titik persimpangan unik

  3. Persimpangan adalah segmen lain

CATATAN : Dalam kode, saya berasumsi bahwa segmen garis (x1, y1), (x2, y2) dengan x1 = x2 dan y1 = y2 adalah segmen garis yang valid. Secara matematis, segmen garis terdiri dari poin yang berbeda, tetapi saya mengizinkan segmen menjadi poin dalam implementasi ini untuk kelengkapan.

Kode diambil dari repo github saya

/**
 * This snippet finds the intersection of two line segments.
 * The intersection may either be empty, a single point or the
 * intersection is a subsegment there's an overlap.
 */

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.ArrayList;
import java.util.List;

public class LineSegmentLineSegmentIntersection {

  // Small epsilon used for double value comparison.
  private static final double EPS = 1e-5;

  // 2D Point class.
  public static class Pt {
    double x, y;
    public Pt(double x, double y) {
      this.x = x; 
      this.y = y;
    }
    public boolean equals(Pt pt) {
      return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
    }
  }

  // Finds the orientation of point 'c' relative to the line segment (a, b)
  // Returns  0 if all three points are collinear.
  // Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
  // Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
  // formed by the segment.
  public static int orientation(Pt a, Pt b, Pt c) {
    double value = (b.y - a.y) * (c.x - b.x) - 
                   (b.x - a.x) * (c.y - b.y);
    if (abs(value) < EPS) return 0;
    return (value > 0) ? -1 : +1;
  }

  // Tests whether point 'c' is on the line segment (a, b).
  // Ensure first that point c is collinear to segment (a, b) and
  // then check whether c is within the rectangle formed by (a, b)
  public static boolean pointOnLine(Pt a, Pt b, Pt c) {
    return orientation(a, b, c) == 0 && 
           min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && 
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
  }

  // Determines whether two segments intersect.
  public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {

    // Get the orientation of points p3 and p4 in relation
    // to the line segment (p1, p2)
    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // If the points p1, p2 are on opposite sides of the infinite
    // line formed by (p3, p4) and conversly p3, p4 are on opposite
    // sides of the infinite line formed by (p1, p2) then there is
    // an intersection.
    if (o1 != o2 && o3 != o4) return true;

    // Collinear special cases (perhaps these if checks can be simplified?)
    if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
    if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
    if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
    if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;

    return false;
  }

  public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {

    List<Pt> points = new ArrayList<>();

    if (p1.equals(p3)) {
      points.add(p1);
      if (p2.equals(p4)) points.add(p2);

    } else if (p1.equals(p4)) {
      points.add(p1);
      if (p2.equals(p3)) points.add(p2);

    } else if (p2.equals(p3)) {
      points.add(p2);
      if (p1.equals(p4)) points.add(p1);

    } else if (p2.equals(p4)) {
      points.add(p2);
      if (p1.equals(p3)) points.add(p1);
    }

    return points;
  }

  // Finds the intersection point(s) of two line segments. Unlike regular line 
  // segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
  public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {

    // No intersection.
    if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};

    // Both segments are a single point.
    if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
      return new Pt[]{p1};

    List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
    int n = endpoints.size();

    // One of the line segments is an intersecting single point.
    // NOTE: checking only n == 1 is insufficient to return early
    // because the solution might be a sub segment.
    boolean singleton = p1.equals(p2) || p3.equals(p4);
    if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};

    // Segments are equal.
    if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};

    boolean collinearSegments = (orientation(p1, p2, p3) == 0) && 
                                (orientation(p1, p2, p4) == 0);

    // The intersection will be a sub-segment of the two
    // segments since they overlap each other.
    if (collinearSegments) {

      // Segment #2 is enclosed in segment #1
      if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
        return new Pt[]{p3, p4};

      // Segment #1 is enclosed in segment #2
      if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
        return new Pt[]{p1, p2};

      // The subsegment is part of segment #1 and part of segment #2.
      // Find the middle points which correspond to this segment.
      Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
      Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;

      // There is actually only one middle point!
      if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};

      return new Pt[]{midPoint1, midPoint2};
    }

    /* Beyond this point there is a unique intersection point. */

    // Segment #1 is a vertical line.
    if (abs(p1.x - p2.x) < EPS) {
      double m = (p4.y - p3.y) / (p4.x - p3.x);
      double b = p3.y - m * p3.x;
      return new Pt[]{new Pt(p1.x, m * p1.x + b)};
    }

    // Segment #2 is a vertical line.
    if (abs(p3.x - p4.x) < EPS) {
      double m = (p2.y - p1.y) / (p2.x - p1.x);
      double b = p1.y - m * p1.x;
      return new Pt[]{new Pt(p3.x, m * p3.x + b)};
    }

    double m1 = (p2.y - p1.y) / (p2.x - p1.x);
    double m2 = (p4.y - p3.y) / (p4.x - p3.x);
    double b1 = p1.y - m1 * p1.x;
    double b2 = p3.y - m2 * p3.x;
    double x = (b2 - b1) / (m1 - m2);
    double y = (m1 * b2 - m2 * b1) / (m1 - m2);

    return new Pt[]{new Pt(x, y)};
  }

}

Berikut ini adalah contoh penggunaan sederhana:

  public static void main(String[] args) {

    // Segment #1 is (p1, p2), segment #2 is (p3, p4)
    Pt p1, p2, p3, p4;

    p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
    p3 = new Pt(0, 0);  p4 = new Pt(2, 4);
    Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point = points[0];

    // Prints: (1.636, 3.273)
    System.out.printf("(%.3f, %.3f)\n", point.x, point.y);

    p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
    p3 = new Pt(-5, 0);  p4 = new Pt(+5, 0);
    points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point1 = points[0], point2 = points[1];

    // Prints: (-5.000, 0.000) (5.000, 0.000)
    System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
  }
will.fiset
sumber
itu bekerja untuk sistem koordinat geografis saya! Terima kasih! Tapi itu untuk persimpangan garis yang tak terbatas, dan saya lebih mencari persimpangan garis hingga.
M. Usman Khan
8

Hanya ingin menyebutkan bahwa penjelasan yang baik dan solusi eksplisit dapat ditemukan dalam seri Numeric Recipes. Saya mendapatkan edisi ke-3 dan jawabannya ada di halaman 1117, bagian 21.4. Solusi lain dengan nomenklatur berbeda dapat ditemukan dalam sebuah makalah oleh Marina Gavrilova Pengujian Interseksi Bagian Garis yang Andal . Solusi saya, bagi saya, sedikit lebih sederhana.

Implementasi saya di bawah:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}
marcp
sumber
Tidak bekerja untuk p1 = (0,0), p2 = (10,0), p3 = (9,0), p4 = (20,0)
padmalcom
Tergantung pada definisi Anda tentang "tidak berhasil", saya kira. Denom adalah 0 sehingga akan mengembalikan false yang tampaknya benar bagi saya karena mereka tidak berpotongan. Colinear tidak sama dengan berpotongan.
marcp
8

Banyak solusi yang tersedia di atas, tetapi saya pikir solusi di bawah ini cukup sederhana dan mudah dimengerti.

Dua segmen Vector AB dan CD Vector berpotongan jika dan hanya jika

  1. Titik akhir a dan b berada di sisi berlawanan dari segmen CD.
  2. Titik akhir c dan d berada di sisi yang berlawanan dari segmen AB.

Lebih khusus a dan b berada di sisi berlawanan dari segmen CD jika dan hanya jika tepat salah satu dari dua kali lipat a, c, d dan b, c, d berada dalam urutan berlawanan arah jarum jam.

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

Di sini CCW mewakili berlawanan arah jarum jam yang mengembalikan nilai true / false berdasarkan orientasi titik.

Sumber: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Halaman 2

zstring
sumber
2
Saya pikir Anda harus sedikit lebih spesifik: bagaimana CCWtes didefinisikan? Dengan tanda produk luar?
ocramz
Terima kasih; pseudo-code ini memungkinkan implementasi yang sangat mudah di Scratch; lihat proyek ini: scratch.mit.edu/projects/129319027
Ruud Helderman
8

C dan Objective-C

Berdasarkan jawaban Gareth Rees

const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};

AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
    return (AGKLine){start, end};
}

double AGKLineLength(AGKLine l)
{
    return CGPointLengthBetween_AGK(l.start, l.end);
}

BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    CGPoint p = l1.start;
    CGPoint q = l2.start;
    CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
    CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);

    double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
    double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
    double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = CGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}

CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
    return (CGPoint){p1.x * factor, p1.y * factor};
}

Banyak fungsi dan struct bersifat pribadi, tetapi Anda seharusnya cukup mudah untuk mengetahui apa yang terjadi. Ini publik untuk repo ini https://github.com/hfossli/AGGeometryKit/

hfossli
sumber
Di mana AGPointZero berasal dari dalam kode ini?
seanicus
1
@seanicus memperbarui contoh untuk menggunakan CGPoint saja
hfossli
6

Ini bekerja dengan baik untuk saya. Diambil dari sini .

 // calculates intersection and checks for parallel lines.  
 // also checks that the intersection point is actually on  
 // the line segment p1-p2  
 Point findIntersection(Point p1,Point p2,  
   Point p3,Point p4) {  
   float xD1,yD1,xD2,yD2,xD3,yD3;  
   float dot,deg,len1,len2;  
   float segmentLen1,segmentLen2;  
   float ua,ub,div;  

   // calculate differences  
   xD1=p2.x-p1.x;  
   xD2=p4.x-p3.x;  
   yD1=p2.y-p1.y;  
   yD2=p4.y-p3.y;  
   xD3=p1.x-p3.x;  
   yD3=p1.y-p3.y;    

   // calculate the lengths of the two lines  
   len1=sqrt(xD1*xD1+yD1*yD1);  
   len2=sqrt(xD2*xD2+yD2*yD2);  

   // calculate angle between the two lines.  
   dot=(xD1*xD2+yD1*yD2); // dot product  
   deg=dot/(len1*len2);  

   // if abs(angle)==1 then the lines are parallell,  
   // so no intersection is possible  
   if(abs(deg)==1) return null;  

   // find intersection Pt between two lines  
   Point pt=new Point(0,0);  
   div=yD2*xD1-xD2*yD1;  
   ua=(xD2*yD3-yD2*xD3)/div;  
   ub=(xD1*yD3-yD1*xD3)/div;  
   pt.x=p1.x+ua*xD1;  
   pt.y=p1.y+ua*yD1;  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  
   xD1=pt.x-p1.x;  
   xD2=pt.x-p2.x;  
   yD1=pt.y-p1.y;  
   yD2=pt.y-p2.y;  
   segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  
   xD1=pt.x-p3.x;  
   xD2=pt.x-p4.x;  
   yD1=pt.y-p3.y;  
   yD2=pt.y-p4.y;  
   segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // if the lengths of both sets of segments are the same as  
   // the lenghts of the two lines the point is actually  
   // on the line segment.  

   // if the point isn’t on the line, return null  
   if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)  
     return null;  

   // return the valid intersection  
   return pt;  
 }  

 class Point{  
   float x,y;  
   Point(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  

   void set(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  
 }  
KingNestor
sumber
8
Ada beberapa masalah dengan kode ini. Itu dapat meningkatkan pengecualian karena pembagian dengan nol; lambat karena membutuhkan akar kuadrat; dan kadang-kadang mengembalikan positif palsu karena menggunakan faktor fudge. Anda bisa melakukan yang lebih baik dari ini!
Gareth Rees
Oke sebagai solusi tetapi yang diberikan oleh Jason pasti komputasi lebih cepat dan menghindari banyak masalah dengan solusi ini
Elemental
6

Saya mencoba beberapa jawaban ini, tetapi mereka tidak berhasil untuk saya (maaf guys); setelah beberapa pencarian bersih saya menemukan ini .

Dengan sedikit modifikasi pada kodenya saya sekarang memiliki fungsi ini yang akan mengembalikan titik persimpangan atau jika tidak ada persimpangan ditemukan akan mengembalikan -1, -1.

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function
Robert
sumber
6

Tampaknya ada beberapa minat pada jawaban Gavin yang cortijon mengusulkan versi javascript di komentar dan iMalc memberikan versi dengan perhitungan yang sedikit lebih sedikit . Beberapa telah menunjukkan kekurangan dengan berbagai proposal kode dan yang lain berkomentar tentang efisiensi beberapa proposal kode.

Algoritma yang disediakan oleh iMalc melalui jawaban Gavin adalah salah satu yang saya gunakan saat ini dalam proyek javascript dan saya hanya ingin memberikan versi yang dibersihkan di sini jika dapat membantu siapa saja.

// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
    p0y, p1y, p2y, p3y, iy,
    collisionDetected;

// do stuff, call other functions, set endpoints...

// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary

var lineSegmentIntersection = function(){
    var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;

    dx1 = p1x - p0x;      dy1 = p1y - p0y;
    dx2 = p3x - p2x;      dy2 = p3y - p2y;
    dx3 = p0x - p2x;      dy3 = p0y - p2y;

    collisionDetected = 0;

    d = dx1 * dy2 - dx2 * dy1;

    if(d !== 0){
        s = dx1 * dy3 - dx3 * dy1;
        if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
            t = dx2 * dy3 - dx3 * dy2;
            if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
                t = t / d;
                collisionDetected = 1;
                ix = p0x + t * dx1;
                iy = p0y + t * dy1;
            }
        }
    }
};
Nolo
sumber
Saya tidak mengerti bagaimana Anda bisa mengerti apa yang terjadi dengan garis-garis seperti t = dx2 * dy3 - dx3 * dy2;...
Supuhstar
@Supuhstar Ini ada hubungannya dengan matematika vektor dan definisi produk titik dan produk silang. Sebagai contoh, kode yang Anda posting mewakili operasi produk silang. Ini adalah cara memproyeksikan satu segmen garis ke yang lain untuk menentukan di mana segmen itu jatuh pada segmen garis lainnya, sebelum titik awal di suatu tempat di tengah atau setelah garis. Jadi t adalah nilai yang dinormalisasi. Jika antara 0 dan 1 maka kedua segmen bersilangan. Jika kurang dari 0 atau lebih besar dari satu maka mereka tidak.
Nolo
@Supuhstar Juga perhatikan bahwa agar proyeksi menemukan titik aktual, hasilnya harus diskalakan. Di situlah t/dmasuk.
Nolo
1
Maksud saya, bagaimana Anda memahami apa yang terjadi dalam sekejap dengan nama variabel seperti itu? Mengapa bukan sesuatu seperti crossProduct = (line1XDifference * line2YDifference) - (line2XDifference * line1YDifference)dan scaledResult = crossProduct / dotProduct?
Supuhstar
1
@Supuhstar Ah, saya mengerti maksud Anda. Erm, well saya kira tidak ada alasan yang tepat untuk berbicara di luar terobsesi efisiensi, tapi itu bukan alasan yang sangat baik karena kompiler melakukan pekerjaan yang cukup baik untuk mengambil sebagian besar kode yang Anda berikan kepada mereka dan menjadikannya seefisien mungkin sambil tidak mengubah apa yang harus dihitung. Di sisi lain, nama-nama p1x, p1ydll dimaksudkan untuk menggambarkan poin dengan nilai x dan y mereka, jadi p1xsingkatan untuk point1x, juga d1x, dalam pikiran saya adalah singkatan untuk huruf yunani deltaXatau bisa Anda katakan differenceInX. (selengkapnya)
Nolo
5

Saya pikir ada solusi yang jauh lebih sederhana untuk masalah ini. Saya datang dengan ide lain hari ini dan tampaknya berfungsi dengan baik (setidaknya dalam 2D ​​untuk saat ini). Yang harus Anda lakukan adalah menghitung persimpangan antara dua garis, lalu memeriksa apakah titik persimpangan yang dihitung berada dalam kotak terikat dari kedua segmen garis. Jika ya, segmen garis berpotongan. Itu dia.

EDIT:

Ini adalah cara saya menghitung persimpangan (Saya tidak tahu lagi di mana saya menemukan potongan kode ini)

Point3D

datang dari

System.Windows.Media.Media3D

public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {

        double a1 = end1.Y - start1.Y;
        double b1 = start1.X - end1.X;
        double c1 = a1 * start1.X + b1 * start1.Y;

        double a2 = end2.Y - start2.Y;
        double b2 = start2.X - end2.X;
        double c2 = a2 * start2.X + b2 * start2.Y;

        double det = a1 * b2 - a2 * b1;
        if (det == 0) { // lines are parallel
            return null;
        }

        double x = (b2 * c1 - b1 * c2) / det;
        double y = (a1 * c2 - a2 * c1) / det;

        return new Point3D(x, y, 0.0);
    }

dan ini adalah kelas BoundingBox (disederhanakan untuk tujuan jawabannya):

public class BoundingBox {
    private Point3D min = new Point3D();
    private Point3D max = new Point3D();

    public BoundingBox(Point3D point) {
        min = point;
        max = point;
    }

    public Point3D Min {
        get { return min; }
        set { min = value; }
    }

    public Point3D Max {
        get { return max; }
        set { max = value; }
    }

    public bool Contains(BoundingBox box) {
        bool contains =
            min.X <= box.min.X && max.X >= box.max.X &&
            min.Y <= box.min.Y && max.Y >= box.max.Y &&
            min.Z <= box.min.Z && max.Z >= box.max.Z;
        return contains;
    }

    public bool Contains(Point3D point) {
        return Contains(new BoundingBox(point));
    }

}
t3chb0t
sumber
3

Solusi ini dapat membantu

public static float GetLineYIntesept(PointF p, float slope)
    {
        return p.Y - slope * p.X;
    }

    public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
    {

        float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
        float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);

        float yinter1 = GetLineYIntesept(line1Start, slope1);
        float yinter2 = GetLineYIntesept(line2Start, slope2);

        if (slope1 == slope2 && yinter1 != yinter2)
            return PointF.Empty;

        float x = (yinter2 - yinter1) / (slope1 - slope2);

        float y = slope1 * x + yinter1;

        return new PointF(x, y);
    }
yazan
sumber
3

Saya mengirim jawaban Kris di atas ke JavaScript. Setelah mencoba berbagai jawaban berbeda, jawabannya memberikan poin yang benar. Saya pikir saya akan menjadi gila karena saya tidak mendapatkan poin yang saya butuhkan.

function getLineLineCollision(p0, p1, p2, p3) {
    var s1, s2;
    s1 = {x: p1.x - p0.x, y: p1.y - p0.y};
    s2 = {x: p3.x - p2.x, y: p3.y - p2.y};

    var s10_x = p1.x - p0.x;
    var s10_y = p1.y - p0.y;
    var s32_x = p3.x - p2.x;
    var s32_y = p3.y - p2.y;

    var denom = s10_x * s32_y - s32_x * s10_y;

    if(denom == 0) {
        return false;
    }

    var denom_positive = denom > 0;

    var s02_x = p0.x - p2.x;
    var s02_y = p0.y - p2.y;

    var s_numer = s10_x * s02_y - s10_y * s02_x;

    if((s_numer < 0) == denom_positive) {
        return false;
    }

    var t_numer = s32_x * s02_y - s32_y * s02_x;

    if((t_numer < 0) == denom_positive) {
        return false;
    }

    if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) {
        return false;
    }

    var t = t_numer / denom;

    var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)};
    return p;
}
Kode monyet
sumber
2

Saya mencoba banyak cara dan kemudian saya memutuskan untuk menulis sendiri. Jadi begini:

bool IsBetween (float x, float b1, float b2)
{
   return ( ((x >= (b1 - 0.1f)) && 
        (x <= (b2 + 0.1f))) || 
        ((x >= (b2 - 0.1f)) &&
        (x <= (b1 + 0.1f))));
}

bool IsSegmentsColliding(   POINTFLOAT lineA,
                POINTFLOAT lineB,
                POINTFLOAT line2A,
                POINTFLOAT line2B)
{
    float deltaX1 = lineB.x - lineA.x;
    float deltaX2 = line2B.x - line2A.x;
    float deltaY1 = lineB.y - lineA.y;
    float deltaY2 = line2B.y - line2A.y;

    if (abs(deltaX1) < 0.01f && 
        abs(deltaX2) < 0.01f) // Both are vertical lines
        return false;
    if (abs((deltaY1 / deltaX1) -
        (deltaY2 / deltaX2)) < 0.001f) // Two parallel line
        return false;

    float xCol = (  (   (deltaX1 * deltaX2) * 
                        (line2A.y - lineA.y)) - 
                    (line2A.x * deltaY2 * deltaX1) + 
                    (lineA.x * deltaY1 * deltaX2)) / 
                 ((deltaY1 * deltaX2) - (deltaY2 * deltaX1));
    float yCol = 0;
    if (deltaX1 < 0.01f) // L1 is a vertical line
        yCol = ((xCol * deltaY2) + 
                (line2A.y * deltaX2) - 
                (line2A.x * deltaY2)) / deltaX2;
    else // L1 is acceptable
        yCol = ((xCol * deltaY1) +
                (lineA.y * deltaX1) -
                (lineA.x * deltaY1)) / deltaX1;

    bool isCol =    IsBetween(xCol, lineA.x, lineB.x) &&
            IsBetween(yCol, lineA.y, lineB.y) &&
            IsBetween(xCol, line2A.x, line2B.x) &&
            IsBetween(yCol, line2A.y, line2B.y);
    return isCol;
}

Berdasarkan dua rumus ini: (Saya menyederhanakannya dari persamaan garis dan rumus lainnya)

rumus untuk x

formula untuk y

Soroush Falahati
sumber
Berfungsi tetapi mencoba untuk memasukkan koordinat ini (jika kolinear / tumpang tindih maka akan mengembalikan hasil yang salah): PointA1 = (0,0) PointA2 = (0,2) dan PointB1 = (0,1) PointB2 = (0,5)
dns
@ dns Nah, itu karena kode mengembalikan false untuk garis paralel. Saya melihat masalah, namun, saya masih tidak tahu apa fungsi yang harus dikembalikan karena ada jumlah jawaban yang tidak terbatas.
Soroush Falahati
2

Ini berdasarkan jawaban Gareth Ree. Itu juga mengembalikan tumpang tindih segmen garis jika mereka melakukannya. Dikodekan dalam C ++, V adalah kelas vektor sederhana. Di mana produk silang dari dua vektor dalam 2D ​​mengembalikan skalar tunggal. Itu diuji dan disahkan oleh sistem pengujian otomatis sekolah saya.

//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
    //If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
    V va = p - l.pa;
    V vb = p - l.pb;
    R ma = va.magnitude();
    R mb = vb.magnitude();
    R ml = (l.pb - l.pa).magnitude();
    R s = ma + mb;
    bool r = s <= ml + epsilon;
    return r;
}

//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
//  Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
    std::vector<V> r;

    //http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    V oa, ob, da, db; //Origin and direction vectors
    R sa, sb; //Scalar values
    oa = la.pa;
    da = la.pb - la.pa;
    ob = lb.pa;
    db = lb.pb - lb.pa;

    if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
    {
        if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
        {
            r.push_back(lb.pa);
            r.push_back(lb.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
        {
            r.push_back(la.pa);
            r.push_back(la.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb))
            r.push_back(la.pa);

        if (on_segment(la.pb, lb))
            r.push_back(la.pb);

        if (on_segment(lb.pa, la))
            r.push_back(lb.pa);

        if (on_segment(lb.pb, la))
            r.push_back(lb.pb);

        if (r.size() == 0)
            dprintf("colinear, non-overlapping\n");
        else
            dprintf("colinear, overlapping\n");

        return r;
    }

    if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
    {
        dprintf("parallel non-intersecting\n");
        return r;
    }

    //Math trick db cross db == 0, which is a single scalar in 2D.
    //Crossing both sides with vector db gives:
    sa = (ob - oa).cross(db) / da.cross(db);

    //Crossing both sides with vector da gives
    sb = (oa - ob).cross(da) / db.cross(da);

    if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
    {
        dprintf("intersecting\n");
        r.push_back(oa + da * sa);
        return r;
    }

    dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
    return r;
}
ColacX
sumber
2

Berikut adalah implementasi dasar segmen garis dalam C #, dengan kode deteksi persimpangan yang sesuai. Ini membutuhkan vektor 2D / titik struct yang disebut Vector2f, meskipun Anda dapat mengganti ini dengan tipe lain yang memiliki properti X / Y. Anda juga bisa menggantinya floatdengan doubleyang sesuai dengan kebutuhan Anda.

Kode ini digunakan di perpustakaan fisika .NET saya, Boing .

public struct LineSegment2f
{
    public Vector2f From { get; }
    public Vector2f To { get; }

    public LineSegment2f(Vector2f @from, Vector2f to)
    {
        From = @from;
        To = to;
    }

    public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);

    /// <summary>
    /// Attempt to intersect two line segments.
    /// </summary>
    /// <remarks>
    /// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
    /// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
    /// </remarks>
    /// <param name="other">The line to attempt intersection of this line with.</param>
    /// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
    /// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
    public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
    {
        var p = From;
        var q = other.From;
        var r = Delta;
        var s = other.Delta;

        // t = (q − p) × s / (r × s)
        // u = (q − p) × r / (r × s)

        var denom = Fake2DCross(r, s);

        if (denom == 0)
        {
            // lines are collinear or parallel
            t = float.NaN;
            u = float.NaN;
            intersectionPoint = default(Vector2f);
            return false;
        }

        var tNumer = Fake2DCross(q - p, s);
        var uNumer = Fake2DCross(q - p, r);

        t = tNumer / denom;
        u = uNumer / denom;

        if (t < 0 || t > 1 || u < 0 || u > 1)
        {
            // line segments do not intersect within their ranges
            intersectionPoint = default(Vector2f);
            return false;
        }

        intersectionPoint = p + r * t;
        return true;
    }

    private static float Fake2DCross(Vector2f a, Vector2f b)
    {
        return a.X * b.Y - a.Y * b.X;
    }
}
Drew Noakes
sumber
1

Program C ++ untuk memeriksa apakah dua segmen garis yang diberikan berpotongan

#include <iostream>
using namespace std;

struct Point
{
    int x;
    int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Driver program to test above functions
int main()
{
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    return 0;
}
Ayush Srivastava
sumber
1

Berdasarkan jawaban @Gareth Rees, versi untuk Python:

import numpy as np

def np_perp( a ) :
    b = np.empty_like(a)
    b[0] = a[1]
    b[1] = -a[0]
    return b

def np_cross_product(a, b):
    return np.dot(a, np_perp(b))

def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
    # /programming/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
    # http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
    r = a[1] - a[0]
    s = b[1] - b[0]
    v = b[0] - a[0]
    num = np_cross_product(v, r)
    denom = np_cross_product(r, s)
    # If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
    if np.isclose(denom, 0) and np.isclose(num, 0):
        # 1. If either  0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
        # then the two lines are overlapping,
        if(considerCollinearOverlapAsIntersect):
            vDotR = np.dot(v, r)
            aDotS = np.dot(-v, s)
            if (0 <= vDotR  and vDotR <= np.dot(r,r)) or (0 <= aDotS  and aDotS <= np.dot(s,s)):
                return True
        # 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
        # then the two lines are collinear but disjoint.
        # No need to implement this expression, as it follows from the expression above.
        return None
    if np.isclose(denom, 0) and not np.isclose(num, 0):
        # Parallel and non intersecting
        return None
    u = num / denom
    t = np_cross_product(v, s) / denom
    if u >= 0 and u <= 1 and t >= 0 and t <= 1:
        res = b[0] + (s*u)
        return res
    # Otherwise, the two line segments are not parallel but do not intersect.
    return None
Ibraim Ganiev
sumber
0

Jika setiap sisi persegi panjang adalah segmen garis, dan bagian yang ditarik pengguna adalah segmen garis, maka Anda hanya perlu memeriksa segmen yang ditarik pengguna untuk persimpangan dengan empat segmen garis samping. Ini harus menjadi latihan yang cukup sederhana mengingat titik awal dan akhir dari setiap segmen.

Harper Shelby
sumber
3
Perhatikan bahwa ini adalah jawaban yang masuk akal untuk pertanyaan yang awalnya dibingkai tetapi sekarang setelah pertanyaan itu banyak diedit, itu tidak masuk akal.
GS - Minta maaf kepada Monica
0

Berdasarkan jawaban t3chb0t:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}
volperossa
sumber
0

Saya membaca algoritma ini dari buku "geometri tampilan berganda"

teks berikut menggunakan

'sebagai tanda transpos

* sebagai produk titik

x sebagai produk silang, bila digunakan sebagai operator

1. definisi garis

sebuah titik x_vec = (x, y) 'terletak pada baris kapak + oleh + c = 0

kami menunjukkan L = (a, b, c) ', titik sebagai (x, y, 1)' sebagai koordinat homogen

persamaan garis dapat ditulis sebagai

(x, y, 1) (a, b, c) '= 0 atau x' * L = 0

2. persimpangan garis

kami memiliki dua baris L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'

anggap x adalah titik, vektor, dan x = L1 x L2 (L1 lintas produk L2).

hati-hati, x selalu merupakan titik 2D, silakan baca koordinat homogen jika Anda bingung tentang (L1xL2) adalah vektor tiga elemen, dan x adalah koordinat 2D.

menurut produk triple, kita tahu itu

L1 * (L1 x L2) = 0, dan L2 * (L1 x L2) = 0, karena L1, L2 co-plane

kita mengganti (L1xL2) dengan vektor x, maka kita memiliki L1 * x = 0, L2 * x = 0, yang berarti x terletak pada L1 dan L2, x adalah titik persimpangan.

hati-hati, di sini x adalah koordinat homogen, jika elemen terakhir x adalah nol, itu berarti L1 dan L2 adalah paralel.

Misa Zhou
sumber
0

Banyak jawaban telah merangkum semua perhitungan menjadi satu fungsi. Jika Anda perlu menghitung kemiringan garis, intersepsi y, atau intersep x untuk digunakan di tempat lain dalam kode Anda, Anda akan membuat perhitungan tersebut secara berlebihan. Saya telah memisahkan fungsi masing-masing, menggunakan nama variabel yang jelas, dan mengomentari kode saya untuk membuatnya lebih mudah diikuti. Saya perlu tahu apakah garis berpotongan tak terbatas di luar titik akhir mereka, jadi dalam JavaScript:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
    point_b = {x:12, y:12},
    point_c = {x:10, y:0},
    point_d = {x:0, y:0},
    slope_ab = slope(point_a, point_b),
    slope_bc = slope(point_b, point_c),
    slope_cd = slope(point_c, point_d),
    slope_da = slope(point_d, point_a),
    yint_ab = y_intercept(point_a, slope_ab),
    yint_bc = y_intercept(point_b, slope_bc),
    yint_cd = y_intercept(point_c, slope_cd),
    yint_da = y_intercept(point_d, slope_da),
    xint_ab = x_intercept(point_a, slope_ab, yint_ab),
    xint_bc = x_intercept(point_b, slope_bc, yint_bc),
    xint_cd = x_intercept(point_c, slope_cd, yint_cd),
    xint_da = x_intercept(point_d, slope_da, yint_da),
    point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
    point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
    point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
    point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);

console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);

function slope(point_a, point_b) {
  var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
  if (i === -Infinity) return Infinity;
  if (i === -0) return 0;
  return i;
}

function y_intercept(point, slope) {
    // Horizontal Line
    if (slope == 0) return point.y;
  // Vertical Line
    if (slope == Infinity)
  {
    // THE Y-Axis
    if (point.x == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return point.y - (slope * point.x);
}

function x_intercept(point, slope, yint) {
    // Vertical Line
    if (slope == Infinity) return point.x;
  // Horizontal Line
    if (slope == 0)
  {
    // THE X-Axis
    if (point.y == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return -yint / slope;
}

// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
  if (slope_a == slope_b)
  {
    // Equal Lines
    if (yint_a == yint_b && xint_a == xint_b) return Infinity;
    // Parallel Lines
    return null;
  }
  // First Line Vertical
    if (slope_a == Infinity)
  {
    return {
        x: xint_a,
      y: (slope_b * xint_a) + yint_b
    };
  }
  // Second Line Vertical
    if (slope_b == Infinity)
  {
    return {
        x: xint_b,
      y: (slope_a * xint_b) + yint_a
    };
  }
  // Not Equal, Not Parallel, Not Vertical
  var i = (yint_b - yint_a) / (slope_a - slope_b);
  return {
    x: i,
    y: (slope_a * i) + yint_a
  };
}
skibulk
sumber