Bagaimana mendeteksi garis 2D pada tabrakan garis?

13

Saya adalah pengembang game actionScript flash yang agak terbelakang dengan matematika, meskipun saya menemukan fisika menarik dan keren.

Untuk referensi, ini adalah game yang mirip dengan yang saya buat: Flash game Untangled

Saya telah membuat game yang tidak terurai ini hampir sepenuhnya melengkapi logika. Tetapi, ketika dua garis berpotongan, saya membutuhkan garis berpotongan atau 'kusut' untuk menunjukkan warna yang berbeda; merah.

Anda akan sangat baik jika Anda dapat menyarankan algoritme untuk mendeteksi tabrakan segmen garis . Saya pada dasarnya adalah orang yang suka berpikir 'visual' daripada 'aritmatika' :)

Sunting: Saya ingin menambahkan beberapa diagram untuk membuat menyampaikan gagasan lebih jelas

tidak ada persimpangan tidak ada persimpangan persimpangan tidak ada persimpangan

PS Saya mencoba membuat fungsi sebagai

private function isIntersecting(A:Point, B:Point, C:Point, D:Point):Boolean

Terima kasih sebelumnya.

Wisnu
sumber
6
Ini adalah penjelasan non-visual yang mengecewakan dari masalah ini, tetapi ini adalah algoritme dan masuk akal jika Anda bisa membaca matematika mereka: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d Mungkin menjadi berat jika matematika vektor Anda lemah. Saya mengerti - Saya juga lebih suka penjelasan visual. Saya akan mencoba mencari waktu nanti untuk mencoret-coret ini, tetapi jika seseorang yang cenderung artistik melihat tautan ini dan punya waktu sebelum saya melakukannya, lakukanlah!
Anko

Jawaban:

18

Saya menggunakan metode berikut yang cukup banyak hanya merupakan implementasi dari algoritma ini . Itu dalam C # tetapi menerjemahkannya ke ActionScript harus sepele.

bool IsIntersecting(Point a, Point b, Point c, Point d)
{
    float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));
    float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));
    float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

    // Detect coincident lines (has a problem, read below)
    if (denominator == 0) return numerator1 == 0 && numerator2 == 0;

    float r = numerator1 / denominator;
    float s = numerator2 / denominator;

    return (r >= 0 && r <= 1) && (s >= 0 && s <= 1);
}

Ada masalah yang halus dengan algoritma, yaitu kasus di mana dua garis bertepatan tetapi tidak tumpang tindih. Algoritme masih mengembalikan intersectioin dalam kasus itu. Jika Anda peduli tentang kasus itu, saya yakin jawaban ini di stackoverflow memiliki versi yang lebih kompleks yang mengatasinya.

Edit

Saya tidak mendapatkan hasil dari algoritma ini, maaf!

Aneh, saya sudah mengujinya dan itu bekerja untuk saya kecuali untuk satu kasus yang saya jelaskan di atas. Menggunakan versi yang persis sama yang saya posting di atas, saya mendapatkan hasil ini ketika saya mengambilnya untuk test drive:

masukkan deskripsi gambar di sini

David Gouveia
sumber
Saya tidak mendapatkan hasil dari algoritma ini, maaf!
Wisnu
4
@Vish Masalah apa yang Anda miliki? Saya menguji salinan tepat dari algoritma ini sebelum memposting dan bekerja dengan sempurna kecuali untuk satu kasus yang dijelaskan
David Gouveia
Lalu, izinkan saya mencoba lagi, saya mungkin telah mencampuradukkan beberapa matematika di dalamnya. Saya akan segera memberi tahu Anda. Terima kasih banyak, nyway :)
Wisnu
1
Saya mendapatkan hasil yang diinginkan dari algoritma Anda, terima kasih @ DavidVouveia.
Wisnu
1
Yah, tapi sekarang saya punya masalah lain :)! Saya perlu membuat garis berpotongan dengan warna merah dan hijau. Persimpangan berfungsi dengan baik. Tapi seperti yang saya mengerti sekarang, (tidak secara matematis) bahwa sederhana jika-tidak akan berfungsi untuk meletakkan garis merah dan hijau untuk garis berpotongan dan non-berpotongan. Node yang saya seret memiliki garis kiri dan kanan. Jadi, ada yang salah di suatu tempat sambil mengubah warna garis yang tidak berpotongan kembali menjadi hijau. Saya kira saya perlu kondisi lain juga. Hmmm, terima kasih banyak, saya menandai ini sebagai jawaban yang benar.
Wisnu
4

Tanpa Divisi! Jadi tidak ada masalah dengan presisi atau pembagian dengan nol.

Segmen baris 1 adalah A ke B Segmen baris 2 adalah C ke D

Garis adalah garis yang tidak pernah berakhir, segmen garis adalah bagian yang ditentukan dari garis itu.

Periksa apakah dua kotak pembatas berpotongan: jika tidak ada persimpangan -> Tanpa Salib! (perhitungan dilakukan, return false)

Periksa apakah garis seg 1 mengangkang garis seg 2 dan apakah garis seg 2 mengangkang garis seg 1 (mis., Segmen Segmen 1 ada di kedua sisi Garis yang ditentukan oleh Segmen garis 2).

Ini dapat dilakukan dengan menerjemahkan semua titik dengan -A (mis. Anda memindahkan 2 baris sehingga A berada di dalam (0,0))

Kemudian Anda memeriksa apakah titik C dan D berada di sisi yang berbeda dari garis yang didefinisikan oleh 0,0 ke B

//Cross Product (hope I got it right here)
float fC= (B.x*C.y) - (B.y*C.x); //<0 == to the left, >0 == to the right
float fD= (B.x*D.y) - (B.y*D.x);

if( (fc<0) && (fd<0)) //both to the left  -> No Cross!
if( (fc>0) && (fd>0)) //both to the right -> No Cross!

Jika Anda belum mendapatkan "No Cross" maka lanjutkan menggunakan bukan A, B versus C, D tetapi C, D versus A, B (kalori yang sama, cukup tukar A dan C, B dan D), jika tidak ada "Tidak ada Salib!" maka Anda memiliki persimpangan!

Saya mencari perhitungan yang tepat untuk produk silang dan menemukan posting blog ini yang menjelaskan metode juga.

Valmond
sumber
1
Saya minta maaf tapi saya tidak cukup baik dengan matematika vektor, saya menerapkan algoritma ini seperti itu, tetapi tidak mendapat hasil, maaf!
Wisnu
1
Itu harus bekerja jadi mungkin jika Anda dapat menunjukkan kode Anda, kami dapat membantu Anda di luar sana?
Valmond
Bagus! namun tautannya rusak
clabe45
Apakah ada sesuatu yang dapat Anda tambahkan ke ini untuk mendapatkan titik persimpangan?
SeanRamey
1

Saya hanya ingin mengatakan, saya membutuhkannya untuk game Gamemaker Studio saya dan ini bekerja dengan baik:

///scr_line_collision(x1,y1,x2,y2,x3,y3,x4,y4)

var denominator= ((argument2 - argument0) * (argument7 - argument5)) - ((argument3 - argument1) * (argument6 - argument4));
var numerator1 = ((argument1 - argument5) * (argument6 - argument4)) - ((argument0 - argument4) * (argument7 - argument5));
var numerator2 = ((argument1 - argument5) * (argument2 - argument0)) - ((argument0 - argument4) * (argument3 - argument1));

// Detect coincident lines
if (denominator == 0) {return (numerator1 == 0 && numerator2 == 0)}

var r = numerator1 / denominator;
var s = numerator2 / denominator;

return ((r >= 0 && r <= 1) && (s >= 0 && s <= 1));
Lukáš Čulen
sumber
Saya pikir jawaban ini benar-benar dapat ditingkatkan jika Anda menjelaskan apa yang dilakukan kode.
TomTsagk
1

Jawaban yang diterima memberikan jawaban yang salah dalam hal ini:

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 10;

x3 = 10.1;
y3 = 10.1;
x4 = 15;
y4 = 15;

Garis-garis ini jelas tidak berpotongan, tetapi menurut fungsi dalam "jawaban yang benar", garis-garis itu berpotongan.

Inilah yang saya gunakan:

function do_lines_intersect(px1,py1,px2,py2,px3,py3,px4,py4) {
  var ua = 0.0;
  var ub = 0.0;
  var ud = (py4 - py3) * (px2 - px1) - (px4 - px3) * (py2 - py1);


  if (ud != 0) {
    ua = ((px4 - px3) * (py1 - py3) - (py4 - py3) * (px1 - px3)) / ud;
    ub = ((px2 - px1) * (py1 - py3) - (py2 - py1) * (px1 - px3)) / ud;
        if (ua < 0.0 || ua > 1.0 || ub < 0.0 || ub > 1.0) ua = 0.0;
  }

  return ua;
}

mengembalikan 0 = garis tidak berpotongan

kembali> 0 = garis berpotongan


Perbarui untuk menjawab pertanyaan:

Saya tidak membuat kode ini sendiri. Sudah lebih dari 5 tahun dan saya tidak tahu apa sumber aslinya. Tapi..

Saya pikir nilai kembali adalah posisi relatif dari baris pertama di mana mereka menyeberang (untuk menjelaskannya dengan buruk). Untuk menghitung titik persimpangan Anda mungkin bisa menggunakan lerp seperti ini:

l = do_lines_intersect(...)
if (l > 0) {
    intersect_pos_x = l * (px2-px1);
    intersect_pos_y = l * (py2-py1);
} else {
    // lines do not cross
}

(SAYA TIDAK MENGUJI INI)

Jorammer
sumber
Apakah ada versi ini yang mengembalikan titik persimpangan?
SeanRamey