Saya mencoba menggabungkan dua hal. Saya sedang menulis permainan dan saya perlu menentukan kotak kisi yang terletak pada garis dengan titik akhir floating-point.
Selain itu saya membutuhkannya untuk memasukkan semua kotak kotak yang disentuhnya (yaitu bukan hanya garis Bresenham tetapi yang biru):
Adakah yang bisa memberi saya wawasan tentang cara melakukannya? Solusi yang jelas adalah dengan menggunakan algoritma garis naif, tetapi apakah ada sesuatu yang lebih dioptimalkan (lebih cepat)?
c#
algorithm
grid
interpolation
floating-point
SmartK8
sumber
sumber
Jawaban:
Anda mencari algoritme lintasan traversal. Makalah ini memberikan implementasi yang baik;
Inilah implementasi dasar dalam 2D yang ditemukan di kertas:
Ada juga versi ray-casting 3D di atas kertas.
Jika tautannya membusuk , Anda dapat menemukan banyak mirror dengan namanya: Algoritma traversal voxel yang lebih cepat untuk raytracing .
sumber
Ide Blue bagus, tetapi implementasinya agak canggung. Bahkan, Anda dapat dengan mudah melakukannya tanpa sqrt. Mari kita asumsikan untuk saat ini bahwa Anda mengecualikan kasus degenerasi (
BeginX==EndX || BeginY==EndY
) dan fokus hanya pada arah garis di kuadran pertama, jadiBeginX < EndX && BeginY < EndY
. Anda harus mengimplementasikan versi untuk setidaknya satu kuadran lain juga, tetapi itu sangat mirip dengan versi untuk kuadran pertama - Anda hanya memeriksa tepi lainnya. Dalam kode semu C'ish:Sekarang untuk kuadran lain, Anda cukup mengubah
++cx
atau++cy
dan kondisi loop. Jika Anda menggunakan ini untuk tabrakan, Anda mungkin harus menerapkan semua 4 versi, jika tidak, Anda bisa mendapatkan dua versi dengan menukar titik awal dan titik akhir dengan tepat.sumber
Asumsi Anda tidak harus menemukan sel tetapi garis-garis yang dilintasi pada kotak ini.
Misalnya mengambil gambar Anda, kami tidak dapat menyorot sel, tetapi garis-garis kisi yang dilintasi:
Ini kemudian menunjukkan bahwa jika melintasi garis kisi, sel-sel di kedua sisi garis ini adalah sel-sel yang terisi.
Anda dapat menggunakan algoritma persimpangan untuk menemukan apakah garis titik apung Anda akan melewatinya dengan menskalakan poin Anda ke piksel. Jika Anda memiliki rasio koordinat mengambang: piksel 1,0: 1 maka Anda disortir dan Anda bisa langsung menerjemahkannya. Dengan menggunakan algoritma persimpangan segmen garis, Anda dapat memeriksa apakah garis kiri bawah Anda (1,7) (2,7) berpotongan dengan garis Anda (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/
Beberapa terjemahan dari c ke C # akan dibutuhkan tetapi Anda bisa mendapatkan ide dari makalah itu. Saya akan meletakkan kode di bawah jika tautannya terputus.
Jika Anda hanya perlu mengetahui kapan (dan di mana) segmen garis berpotongan, Anda dapat memodifikasi fungsi sebagai berikut:
sumber
Demo JS:
Tampilkan cuplikan kode
sumber
Saya mengalami masalah yang sama hari ini dan membuat gunung spageti yang cukup besar keluar dari bukit mol tetapi berakhir dengan sesuatu yang berfungsi: https://github.com/SnpM/Pan-Line-Algorithm .
Dari ReadMe:
ReadMe menjelaskan solusinya jauh lebih baik daripada kode. Saya berencana merevisinya menjadi lebih sedikit sakit kepala.
Saya tahu saya terlambat sekitar satu tahun untuk pertanyaan ini, tetapi saya berharap ini dapat diterima oleh orang lain yang mencari solusi untuk masalah ini.
sumber