Menemukan Titik Perpotongan Dua Garis (dan Ruas Garis)

pengantar

Cukup sering, ketika mengembangkan permainan, menjadi perlu untuk menemukan titik perpotongan garis, ruas, sinar, dll. Cara menerapkan ini dengan cara yang sesederhana mungkin, dalam artikel ini.

Metode populer dan kritik mereka

Mungkin banyak yang akan mengingat cara dari aljabar sekolah - untuk membuat persamaan dua garis lurus, menyamakan sisi kanannya, mencari x, dan menggantinya dengan persamaan garis lurus untuk mencari y ( Lebih lengkapnya di sini ).



Namun, metode ini menjadi cukup rumit saat menulis kode (mungkin inilah mengapa Anda membaca artikel ini sekarang), terlebih lagi, ini tidak universal: jika salah satu garis lurus sejajar dengan sumbu Y, kita akan mendapatkan kesalahan pembagian dengan nol saat menghitung kemiringan, dan kita harus daftarkan kode untuk kasus ini; jika dua garis sejajar, Anda perlu mengotak-atik pemrosesan kasus ini juga. Kode ini menjadi panjang dan jelek.



Dalam mencari solusi yang lebih elegan untuk masalah ini, saya menemukan beberapa cara yang sangat menarik berdasarkan perkalian vektor (habr.com/ru/post/267037 ) dan pengecoran sinar ( ru.wikipedia.org/wiki/Ray_casting#Concept ). Tapi menurut saya, mereka sangat kompleks secara komputasi. Oleh karena itu, saya sampaikan perhatian (dan kritik) metode saya.

Jalanku

Tugas

Koordinat dari dua segmen diberikan. Anda perlu mencari tahu apakah segmennya berpotongan, dan jika ya, pada titik mana. Untuk tujuan ini, kami akan menulis sebuah fungsi.

Keputusan

Legenda untuk menghindari kesalahpahaman: a - vektor a, a (y) - proyeksi vektor a ke sumbu Y, a {x1, y1} - vektor a, ditentukan oleh koordinat x1, y1.



Mari kita gambarkan segmen kita dalam bentuk dua vektor: a {x2-x1; y2-y1} dan b {x3-x4; y3-x4}. Perhatikan bahwa vektor b berlawanan arah dari yang diharapkan. Mari kita perkenalkan vektor c {x3-x1; y3-y1}. Perhatikan bahwa a * k + b * n = c, di mana k, n adalah beberapa koefisien. Jadi, kita mendapatkan sistem persamaan:



a (x) * k + b (x) * n = c (x)

a (y) * k + b (y) * n = c (y)

Tugas kita direduksi untuk mencari koefisien ini (memang, cukup menemukan hanya satu dari mereka).



Saya mengusulkan untuk mengalikan kedua sisi persamaan yang lebih rendah dengan q = -a (x) / a (y). Jadi setelah menambahkan dua persamaan, kita segera menyingkirkan k. Menemukan n direduksi untuk menyelesaikan persamaan linier biasa. Penting untuk dicatat bahwa n mungkin tidak memiliki solusi.



Pembaca yang perhatian akan memperhatikan bahwa ketika a (y) = 0, kita mendapatkan kesalahan. Mari tulis percabangan pada tahap pencarian a (y). Kasus ini bahkan lebih sederhana, karena kita segera mendapatkan persamaan dengan yang tidak diketahui.



Saya sarankan mencoba mencetak sendiri, jadi akan lebih jelas apa yang berasal dari kode di bawah ini.



Mengetahui n, Anda dapat menemukan titik perpotongan, untuk ini kita kurangi vektor b * n dari koordinat titik (x3, y3)

Menyatukannya

float dot[2];  //  

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

Fungsi ini mengambil koordinat dari simpul dan mengembalikan nilai 1 jika garis lurus dari segmen (yaitu, garis lurus) berpotongan, jika tidak 0. Jika Anda membutuhkan koordinat dari simpul, Anda dapat mengambilnya dari larik titik [].



Penting: saat memperkenalkan dua garis yang bertepatan, algoritme tidak menampilkan persimpangan. Algoritme menemukan titik perpotongan dari garis-garis tempat segmen garis itu berada, sehingga titik tersebut mungkin berada di luar segmen tersebut (yang harus Anda periksa dalam kode Anda).



Mari terapkan fungsinya:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

Kata Penutup

Meskipun saya tidak menemukan metode ini dalam proses mencari masalah di Google dan mengembangkan algoritme sendiri, saya tidak berpura-pura menjadi sepenuhnya asli (dan benar). Selamat datang di komentar!