Isi artikel ini sangat mendasar, terutama untuk pemula seperti saya, jadi tolong minta semua kaisar algoritma untuk melihat sekilas
Mengutip
Diketahui bahwa segmen garis 1 (a, b) dan segmen garis 2 (c, d), di mana ABCD adalah titik akhir, temukan titik persimpangan p dari segmen garis. (Paralel atau collinear dianggap terputus -putus)
Algoritma 1: Temukan titik persimpangan garis lurus di mana dua segmen garis berada, dan kemudian tentukan apakah titik persimpangan ada pada dua segmen garis.
Ketika menemukan titik persimpangan garis lurus, kita dapat menemukannya melalui persamaan umum AX+oleh+C = 0 dari garis lurus (ABC dalam persamaan adalah koefisien, bukan titik akhir yang disebutkan di atas. Selain itu, persamaan titik miring dan persamaan intersep miring juga dapat digunakan, bukan di sini untuk saat ini).
Kemudian, berdasarkan hubungan posisional antara titik persimpangan dan titik akhir segmen garis, kita dapat menilai apakah titik persimpangan ada pada segmen garis.
Formulanya adalah sebagai berikut:
<code> function SegmentsIntr (a, b, c, d) { /** 1 Selesaikan sistem persamaan linier dan temukan persimpangan segmen garis. **/ // Jika denominator adalah 0, itu paralel atau collinear, dan tidak memotong var denominator = (oleh - ay)*(dx - cx) - (kapak - bx)*(cy - dy); if (denominator == 0) {return false; } // Koordinat persimpangan dari garis lurus di mana segmen garis berada (x, y) var x = ((bx - ax) * (dx - cx) * (cy - ay) + (oleh - ay) * (dx - cx) * kapak - (dy - cy) * (bx - ax) * cx) / denominator; var y = - ((oleh - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (oleh - ay) * cy) / penyebut; / ** 2 Tentukan apakah persimpangan ada pada dua segmen **/ if (// persimpangan Segmen On Line 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - oleh) <= 0 // dan persimpangan juga pada segmen garis 2 && (x - cx) * (x - dx) <= // Kembali ke persimpangan p return {x: x, y: y}} // Sebaliknya, disjoint return false} </code>Algoritma pertama memiliki ide yang jelas dan mudah dipahami, tetapi kinerjanya tidak tinggi. Karena menghitung persimpangan sebelum tidak pasti apakah persimpangan valid (pada segmen online), yang membutuhkan banyak waktu.
Jika titik persimpangan akhirnya ditemukan tidak valid, maka perhitungan sebelumnya akan sia -sia. Selain itu, seluruh proses perhitungan juga sangat rumit.
Jadi apakah ada cara untuk mengetahui apakah ada titik persimpangan yang efektif terlebih dahulu dan kemudian menghitungnya?
Jelas jawabannya adalah ya. Jadi beberapa algoritma ditemukan.
Algoritma 2: Tentukan apakah dua titik akhir dari setiap segmen garis berada di kedua sisi segmen garis lainnya. Kemudian temukan persimpangan garis lurus di mana dua segmen garis berada, jika tidak mereka tidak berpotongan.
Langkah pertama adalah menentukan apakah dua titik berada di kedua sisi segmen garis tertentu. Metode proyeksi biasanya dapat digunakan:
Temukan vektor normal dari segmen garis, kemudian proyeksikan titik ke garis normal, dan akhirnya menilai hubungan antara titik dan segmen garis berdasarkan posisi yang diproyeksikan.
Lihat gambar di bawah ini
Proyeksi pada CD segmen garis normal titik A dan titik B ditunjukkan pada gambar. Pada saat ini, kita juga perlu memproyeksikan CD segmen garis pada garis normal kita (cukup pilih salah satu titik C atau titik D).
Terutama digunakan untuk referensi.
Pada gambar, proyeksi titik A dan titik B diproyeksikan pada kedua sisi proyeksi titik C, menunjukkan kedua sisi CD segmen garis segmen garis AB.
Demikian pula, cukup menilai apakah CD ada di kedua sisi segmen garis AB lagi.
Menemukan normals, proyeksi, dan hal -hal lain terdengar sangat rumit, tetapi sebenarnya itu memang cukup rumit bagi saya. Saya tidak tahu banyak tentang pengetahuan geometri beberapa bulan yang lalu (saya lupa semua pengetahuan geometri ketika saya sedang belajar: '()'
Untungnya, pembelajaran dan implementasi tidak rumit, dan ada formula untuk diikuti.
Temukan normal segmen garis AB:
var nx = oleh - ay, NY = ax - bx; var normalline = {x: nx, y: ny}; Catatan: Di mana makna geometris normalLine.x dan normalLine.y mewakili arah garis normal, bukan koordinat.
Temukan posisi proyeksi titik C pada garis normal:
var dist = normalline.x*cx + normalline.y*cy;
Catatan: "Posisi proyeksi" di sini adalah skalar, yang mewakili jarak ke asal normal, bukan koordinat titik proyeksi.
Biasanya cukup untuk mengetahui jarak ini.
Setelah kami menghitung proyeksi titik A (dista), titik B (distb), dan titik C (distc) pada gambar, kami dapat dengan mudah menilai posisi relatif berdasarkan ukuran masing -masing.
Saat dista == distb == Distc, kedua segmen tersebut adalah collinear
Saat dista == distb! = Distc, dua segmen garis paralel
Ketika dista dan distb berada di sisi yang sama dari Distc, dua segmen garis tidak berpotongan.
Ketika dista dan distb berada di sisi yang berlawanan dari Distc, apakah dua segmen garis berpotongan perlu dinilai lagi apakah hubungan antara titik C dan segmen garis AB.
Langkah -langkah sebelumnya hanya menerapkan "menilai apakah segmen garis berpotongan". Ketika hasilnya benar, kita perlu lebih menemukan titik persimpangan.
Mari kita bicara tentang proses menemukan titik persimpangan nanti. Pertama -tama mari kita lihat implementasi lengkap dari algoritma ini:
function SegmentsIntr (a, b, c, d) {// normal n1 var nx1 = (oleh - ay), ny1 = (ax - bx); // normal n2 var nx2 = (dy - cy), ny2 = (cx - dx); // Dua normal dikalikan, jika hasilnya adalah 0, itu berarti bahwa segmen garis AB dan segmen CD paralel atau collinear, dan jangan memotong var denominator = nx1*NY2 - NY1*NX2; if (denominator == 0) {return false; } // Proyeksi pada N2 N2 var var distc_n2 = nx2 * cx + ny2 * cy; var dista_n2 = nx2 * ax + ny2 * ay-disc_n2; var disb_n2 = nx2 * bx + ny2 * by-disc_n2; // Proyeksi titik A dan titik B berada di sisi yang sama dari proyeksi titik C (untuk kasus pada segmen garis, contoh ini diperlakukan sebagai terpisah); if (dista_n2*distb_n2> = 0) {return false; } // // menilai hubungan antara titik C titik D dan segmen garis AB, prinsipnya sama dengan di atas // // proyeksi pada n1 var var normal_n1 = nx1 * ax + ny1 * ay; var distc_n1 = nx1 * cx + ny1 * cy-disha_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if (distc_n1*distd_n1> = 0) {return false; } // Hitung koordinat persimpangan var fraksi = dista_n2 / penyebut; var dx = fraksi * ny1, dy = -fraction * nx1; return {x: ax + dx, y: ay + dy}; }Metode yang digunakan untuk menemukan koordinat titik persimpangan pada akhirnya terlihat agak aneh, dan rasanya tidak mencolok.
Faktanya, ini mirip dengan algoritma dalam algoritma 1, kecuali bahwa banyak istilah perhitungan di dalamnya telah dihitung sebelumnya.
Dengan kata lain, bagian dari algoritma untuk menemukan koordinat titik persimpangan dalam dua mil sebenarnya terbuat dari persamaan linier garis lurus.
Sekarang mari kita bandingkan algoritma satu dan algoritma dua dengan cara yang sederhana dan kasar dan tidak ilmiah:
1. Dalam kasus terbaik, kompleksitas kedua algoritma adalah sama
2. Dalam kasus terburuk, jumlah perhitungan algoritma 1 dan algoritma 2 hampir sama
3. Namun, algoritma 2 memberikan lebih banyak "kondisi akhir awal", jadi rata -rata, algoritma 2 harus lebih baik.
Setelah pengujian yang sebenarnya, situasi yang sebenarnya memang terjadi.
Dua algoritma sebelumnya pada dasarnya umum dan dapat mengatasi sebagian besar situasi. Namun pada kenyataannya, ada algoritma yang lebih baik.
Inilah yang baru saja saya pelajari baru -baru ini (saya mempelajarinya sekarang dan menjualnya sekarang, jangan keberatan ...)
Algoritma 3: Tentukan apakah dua titik akhir dari setiap segmen garis berada di kedua sisi segmen garis lainnya. Jika Anda menemukan persimpangan garis lurus di mana dua segmen garis berada, jika tidak mereka tidak akan berpotongan.
(Huh? Mengapa rasanya sama dengan algoritma 2? Jangan ragu itu memang sama ...)
Algoritma 3 yang disebut sebenarnya hanyalah peningkatan algoritma 2. Perbaikan utamanya adalah:
Hubungan posisi antara titik dan segmen garis tidak dinilai dengan proyeksi normal, tetapi oleh area segitiga yang terdiri dari poin dan segmen garis.
Pertama -tama mari kita tinjau formula area segitiga: diketahui bahwa tiga titik A (x, y) B (x, y) C (x, y) dari area segitiga adalah:
<code> var triarea = ((ax - cx) * (oleh - cy) - (ay - cy) * (bx - cx)) /2; </code>
Karena area jajaran genjang (dua vektor adalah sisi yang berdekatan) yang terdiri dari dua vektor forking == Dua vektor, formula di atas tidak sulit untuk dipahami.
Selain itu, karena vektor memiliki arahan, area tersebut juga memiliki arahan. Biasanya, kami menggunakan berlawanan arah jarum jam sebagai positif dan searah jarum jam negatif.
Poin -poin penting dari algoritma yang ditingkatkan adalah:
Jika tanda -tanda positif dan negatif dari area segitiga yang dibentuk oleh "segmen garis AB dan titik C" berbeda dari area segitiga yang dibentuk oleh "segmen garis AB dan titik D",
Kemudian titik C dan titik D terletak di kedua sisi segmen garis AB.
Seperti yang ditunjukkan pada gambar di bawah ini:
Segitiga yang ditunjukkan oleh garis putus -putus pada gambar memiliki arah belitan yang berbeda (urutan definisi ketiga sisi), sehingga simbol positif dan negatif dari area tersebut berbeda.
Mari kita lihat kode terlebih dahulu:
Karena kita hanya perlu menilai simbol, kita tidak perlu membagi yang berikut dengan 2 dalam formula Area Segitiga sebelumnya.
function SegmentsIntr (a, b, c, d) {// 2 kali luas segitiga abc var area_abc = (ax - cx) * (oleh - cy) - (ay - cy) * (bx - cx); // 2 kali luas segitiga abd var area_abd = (ax - dx) * (oleh - dy) - (ay - dy) * (bx - dx); // Jika simbol area sama, kedua titik tidak berpotongan di sisi yang sama (dalam kasus titik pada segmen garis, contoh ini diperlakukan sebagai terputus -putus); if (Area_abc*Area_Abd> = 0) {return false; } // 2 kali luas segitiga CDA var Area_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax); // 2 kali luas segitiga CDB // Catatan: Ada optimasi kecil di sini. Tidak perlu menghitung area dengan formula, tetapi diturunkan dengan menambahkan dan mengurangi tiga area yang diketahui. var Area_CDB = Area_CDA + Area_Abc - Area_Abd; if (Area_cda * Area_CDB> = 0) {return false; } // Hitung koordinat persimpangan var t = Area_cda / (Area_Abd- Area_Abc); var dx = t*(bx - ax), dy = t*(oleh - ay); return {x: ax + dx, y: ay + dy}; }Akhirnya, bagian yang menghitung koordinat persimpangan sama dengan algoritma.
Berdasarkan algoritma 2, algoritma 3 sangat menyederhanakan langkah -langkah perhitungan dan kode lebih ramping. Dapat dikatakan bahwa itu adalah yang terbaik di antara tiga algoritma. Hal yang sama berlaku untuk hasil tes yang sebenarnya.
Tentu saja, kita harus jujur, dalam JavaScript, kompleksitas waktu dari tiga algoritma sebenarnya serupa untuk perhitungan biasa (terutama di bawah mesin V8).
Dalam kasus pengujian saya, saya juga melakukan tes persimpangan segmen garis-jutaan tingkat normal untuk memperluas kesenjangan antara tiga algoritma.
Meringkaskan
Namun, dengan sikap berjuang untuk keunggulan dan belajar, mengejar algoritma yang lebih baik selalu memiliki signifikansi positif. Di atas adalah beberapa algoritma yang menggunakan JS untuk mencapai titik persimpangan segmen garis. Kontennya tidak terlalu mendalam. Saya harap ini akan membantu semua orang untuk belajar JS.