Bagaimana cara menentukan apakah dua garis berpotongan atau tidak, dan jika ada, pada titik x, y apa?
geometry
line-intersection
KingNestor
sumber
sumber
Jawaban:
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 garis berpotongan jika kita dapat menemukan t dan u sedemikian rupa sehingga:
Seberangi kedua sisi dengan s , dapatkan
Dan karena s × s = 0, ini berarti
Dan karena itu, penyelesaian untuk t :
Dengan cara yang sama, kita bisa menyelesaikannya untuk Anda :
Untuk mengurangi jumlah langkah perhitungan, lebih mudah untuk menulis ulang ini sebagai berikut (mengingat bahwa s × r = - r × s ):
Sekarang ada empat kasus:
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 ):
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 ].
Jika r × s = 0 dan ( q - p ) × r ≠ 0, maka kedua garis itu paralel dan tidak berpotongan.
Jika r × s ≠ 0 dan 0 ≤ t ≤ 1 dan 0 ≤ u ≤ 1, dua segmen garis bertemu pada titik p + t r = q + u s .
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.
sumber
/ (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)|
?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.
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:
Itu membingungkan saya selama berjam - jam . :(
sumber
s
dant
secara langsung, uji hubungan antara dua pembilang dan penyebut. Hanya jika garis dikonfirmasi untuk memotong apakah Anda benar-benar perlu menghitung nilait
(tetapi tidaks
).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" danCy
"koordinat y" C. Dan "*
" berarti produk titik, jadi misA*B = Ax*Bx + Ay*By
.h
Nomor ini adalah kuncinya. Jikah
berada di antara0
dan1
, garis-garis berpotongan, jika tidak, maka garis tersebut tidak. JikaF*P
nol, 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
h
adalah persis0
atau1
garis menyentuh pada titik akhir. Anda dapat menganggap ini "persimpangan" atau tidak sesuai keinginan Anda.Secara khusus,
h
adalah 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 jikah>1
garis 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
g
danh
sedemikian rupa sehingga persamaan ini berlaku: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
x
dany
.)Kami harus menghilangkan salah satu dari variabel-variabel ini. Cara mudah adalah membuat
E
istilah nol. Untuk melakukan itu, ambil titik-produk dari kedua sisi persamaan menggunakan vektor yang akan dot ke nol dengan E. Vektor yang saya sebut diP
atas, dan saya melakukan transformasi yang jelas dari E.Anda sekarang memiliki:
sumber
A + E*g = C + F*h
Dua garis berpotongan jika dan hanya jika solusi untuk persamaan itu (dengan asumsi mereka tidak paralel) memiliki keduanya,g
danh
antara 0 dan 1 (eksklusif atau eksklusif, tergantung pada apakah Anda menghitung menyentuh pada titik akhir).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
sumber
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:
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.
sumber
s32_y
bukan sesuatu yang menggambarkan seperti apa itupoint2YDifference
?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:
Apa itu kotak pembatas? Berikut adalah dua kotak pembatas dari dua segmen garis:
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)
, titikB = (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).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.
sumber
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
sumber
Jawaban iMalc versi python:
sumber
denom = float(...)
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:
Segmen tidak berpotongan
Ada titik persimpangan unik
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
Berikut ini adalah contoh penggunaan sederhana:
sumber
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:
sumber
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
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.
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
sumber
CCW
tes didefinisikan? Dengan tanda produk luar?C dan Objective-C
Berdasarkan jawaban Gareth Rees
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/
sumber
Ini bekerja dengan baik untuk saya. Diambil dari sini .
sumber
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.
sumber
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.
sumber
t = dx2 * dy3 - dx3 * dy2;
...t/d
masuk.crossProduct = (line1XDifference * line2YDifference) - (line2XDifference * line1YDifference)
danscaledResult = crossProduct / dotProduct
?p1x, p1y
dll dimaksudkan untuk menggambarkan poin dengan nilai x dan y mereka, jadip1x
singkatan untukpoint1x
, jugad1x
, dalam pikiran saya adalah singkatan untuk huruf yunanideltaX
atau bisa Anda katakandifferenceInX
. (selengkapnya)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)
datang dari
dan ini adalah kelas BoundingBox (disederhanakan untuk tujuan jawabannya):
sumber
Solusi ini dapat membantu
sumber
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.
sumber
Saya mencoba banyak cara dan kemudian saya memutuskan untuk menulis sendiri. Jadi begini:
Berdasarkan dua rumus ini: (Saya menyederhanakannya dari persamaan garis dan rumus lainnya)
sumber
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.
sumber
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 menggantinyafloat
dengandouble
yang sesuai dengan kebutuhan Anda.Kode ini digunakan di perpustakaan fisika .NET saya, Boing .
sumber
Program C ++ untuk memeriksa apakah dua segmen garis yang diberikan berpotongan
sumber
Berdasarkan jawaban @Gareth Rees, versi untuk Python:
sumber
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.
sumber
Berdasarkan jawaban t3chb0t:
sumber
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.
sumber
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/
sumber