Bagaimana Anda menghitung titik terdekat pada 2 kurva?
15
Mengingat titik-titik garis dan kurva bezier kuadrat, bagaimana Anda menghitung titik terdekat mereka? .... Demikian pula, mengingat poin 2 kurva, bagaimana Anda mendapatkan poin terdekat?
Ini usahaku. Algoritme berikut jauh dari sempurna , tetapi sederhana dan saya yakin Anda harus mulai dengan ini, memeriksa apakah mereka bekerja dalam situasi Anda, dan beralih ke sesuatu yang lebih cepat dan / atau lebih akurat nanti.
Idenya adalah sebagai berikut:
Cicipi kurva Bézier, temukan titik terdekat pada sampel itu
Cicipi lingkungan di sekitar titik yang ditemukan, temukan titik terdekat yang baru
Terus sampai titik tidak lagi banyak berubah
Algoritma untuk jarak dari kurva Bézier ke garis
Kurva Bézier ditentukan oleh fungsi F(t)menggunakan satu set titik kontrol dan parameter yang bervariasi t. Jumlah poin pembangkit tidak penting.
Garis ditentukan oleh dua poin Adan B.
Biarkan SAMPLES = 10misalnya
Mulai dengan t0 = 0dant1 = 1
Membiarkan dt = (t1 - t0) / SAMPLES
Jika dt < 1e-10(atau kondisi akurasi lainnya yang Anda inginkan), algoritma telah selesai dan jawabannya sudahF(t0) .
Hitung daftar SAMPLES + 1poin pada kurva Bézier:
L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
...
L[SAMPLES] = F(t0 + SAMPLES * dt)
Cari titik mana Ldengan indeks ipaling dekat dengan garis. Gunakan metode jarak titik / garis apa pun yang Anda tahu, misalnya jarak kuadrat di ||AB^L[i]A||² / ||AB||²mana ^menunjukkan produk silang dan ||…||jarak.
Jika i == 0, atur i = 1; jika i == SAMPLES, aturi = SAMPLES - 1
Biarkan t1 = t0 + (i + 1) * dtdant0 = t0 + (i - 1) * dt
Kembali ke langkah 3.
Algoritma untuk jarak dari kurva Bézier ke kurva Bézier
Kali ini kami memiliki dua kurva Bézier, parametris oleh F(t)dan G(t).
Biarkan SAMPLES = 10misalnya
Mulailah dengan t0 = 0, t1 = 1, s0 = 0dans1 = 1
Membiarkan dt = (t1 - t0) / SAMPLES
Membiarkan ds = (s1 - s0) / SAMPLES
Jika dt < 1e-10(atau kondisi akurasi lainnya yang Anda inginkan), algoritma telah selesai dan jawabannya sudahF(t0) .
JIKA ini menjalankan pertama dari loop:
6.1. Hitung daftar SAMPLES + 1poin pada F( lihat di atas ).
6.2. Hitung daftar SAMPLES + 1poin aktif G.
6.3. Temukan pasangan poin mana yang paling dekat satu sama lain.
6.4. Update t0, t1, s0, s1seperti yang terlihat di atas.
LAIN : sebagai alternatif, hitung daftar poin pada FATAU daftar poin aktif G, kemudian cari titik mana yang Fpaling dekat G(s0)dan perbarui t0dan t1, ATAU titik mana yang Gpaling dekat dengan F(t0)dan perbarui s0dan s1.
Kembali ke langkah 3.
Masalah
Secara desain, algoritma ini akan selalu konvergen ke minimum lokal. Namun, tidak ada jaminan bahwa mereka akan bertemu dengan solusi terbaik. Secara khusus, algoritma kurva Bézier tidak terlalu bagus sama sekali, dan dalam kasus dua kurva yang berdekatan satu sama lain di banyak tempat, sayangnya Anda mungkin melewatkan solusi dengan tembakan panjang.
Tetapi seperti yang saya katakan, sebelum Anda mulai memikirkan solusi yang lebih kuat, Anda harus terlebih dahulu bereksperimen dengan yang sederhana.
1) Terjemahkan semuanya ke satu sumbu, jadi alih-alih perlu menghitung panjang satu titik ke, 'garis', 'garis' adalah, katakanlah, sumbu-Y.
Lalu, eh, diberi kurva bezier saya akan mengatakan itu sampai dengan jumlah titik kontrol.
Jika ada tiga, (awal, 'kontrol' dan akhir) saya akan melakukan semacam pemindaian (katakan masing-masing beberapa persen dan kemudian perbaiki antara yang terdekat (dengan katakanlah pendekatan 'biner').
Lebih banyak poin saya akan mencoba pasangan yang paling dekat dengan (diterjemahkan Y-Axis).
Saya yakin seorang pria matematika dapat memberikan Anda solusi yang tepat (dalam matematika) tetapi jika Anda ingin menemukan / solusi dalam permainan video Anda mungkin lebih baik dengan solusi yang sedikit ok karena solusi sebenarnya mungkin berisi beberapa jawaban ( Saya bahkan tidak berbicara tentang kekuatan pemrosesan).
ps. 2 kurva, bahkan jangan berpikir tentang hal itu (Anda mungkin mendapatkan apa pun (setidaknya sebanyak mungkin ..) sesuai dengan jumlah titik kontrol)
Valmond
0
Beberapa jawaban dari halaman blog Algoritma , yang dengan benar menemukan titik terdekat pada kurva bezier kuadratik yang diberikan.
Untuk kurva Bezier - garis lurus, cara paling akurat untuk menemukan jawabannya adalah dengan melakukan hal berikut:
Transformasikan masalah sehingga garis lurus selalu horizontal pada Y = 0. Ini dilakukan dengan mengalikan semua titik kontrol dengan matriks affine yang sesuai. (Saya berasumsi Anda sudah familiar dengan mewakili transformasi affine dari pesawat dengan matriks 3x3 dengan 3 entri tetap.)
Periksa koordinat Y dari titik kontrol. Jika mereka tidak memiliki tanda yang sama, mungkin ada persimpangan dengan garis. Hitung akar bagian Y dari kurva Bezier. Anda dapat menggunakan metode pencarian root apa pun untuk polinomial, ada banyak di antaranya dalam literatur. Misalnya, google "convex hull marching" - ini adalah metode yang cukup baik untuk polinomial yang digunakan dalam kurva Bezier. Setiap root yang Anda temukan adalah nilai waktu dari persimpangan dengan garis, di mana jaraknya nol - pekerjaan Anda selesai.
Jika semua koordinat Y memiliki tanda yang sama, hitung turunan dari bagian Y dari kurva Bezier. Anda dapat mengabaikan koordinat X poin, karena mereka tidak membuat perbedaan - garis target horizontal. Temukan akar dari turunan itu. Ini adalah nilai waktu di mana kurva secara lokal terdekat dengan garis.
Secara eksplisit mengevaluasi kurva Bezier untuk semua root yang Anda temukan pada langkah sebelumnya dan melaporkan root yang memberikan jarak terkecil dari garis. Anda juga perlu memeriksa titik akhir - mereka mungkin memberikan jarak yang lebih kecil daripada root.
Jawaban:
Ini usahaku. Algoritme berikut jauh dari sempurna , tetapi sederhana dan saya yakin Anda harus mulai dengan ini, memeriksa apakah mereka bekerja dalam situasi Anda, dan beralih ke sesuatu yang lebih cepat dan / atau lebih akurat nanti.
Idenya adalah sebagai berikut:
Algoritma untuk jarak dari kurva Bézier ke garis
Kurva Bézier ditentukan oleh fungsi
F(t)
menggunakan satu set titik kontrol dan parameter yang bervariasit
. Jumlah poin pembangkit tidak penting.Garis ditentukan oleh dua poin
A
danB
.Biarkan
SAMPLES = 10
misalnyaMulai dengan
t0 = 0
dant1 = 1
Membiarkan
dt = (t1 - t0) / SAMPLES
Jika
dt < 1e-10
(atau kondisi akurasi lainnya yang Anda inginkan), algoritma telah selesai dan jawabannya sudahF(t0)
.Hitung daftar
SAMPLES + 1
poin pada kurva Bézier:L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
L[SAMPLES] = F(t0 + SAMPLES * dt)
Cari titik mana
L
dengan indeksi
paling dekat dengan garis. Gunakan metode jarak titik / garis apa pun yang Anda tahu, misalnya jarak kuadrat di||AB^L[i]A||² / ||AB||²
mana^
menunjukkan produk silang dan||…||
jarak.Jika
i == 0
, aturi = 1
; jikai == SAMPLES
, aturi = SAMPLES - 1
Biarkan
t1 = t0 + (i + 1) * dt
dant0 = t0 + (i - 1) * dt
Kembali ke langkah 3.
Algoritma untuk jarak dari kurva Bézier ke kurva Bézier
Kali ini kami memiliki dua kurva Bézier, parametris oleh
F(t)
danG(t)
.Biarkan
SAMPLES = 10
misalnyaMulailah dengan
t0 = 0
,t1 = 1
,s0 = 0
dans1 = 1
Membiarkan
dt = (t1 - t0) / SAMPLES
Membiarkan
ds = (s1 - s0) / SAMPLES
Jika
dt < 1e-10
(atau kondisi akurasi lainnya yang Anda inginkan), algoritma telah selesai dan jawabannya sudahF(t0)
.JIKA ini menjalankan pertama dari loop:
6.1. Hitung daftar
SAMPLES + 1
poin padaF
( lihat di atas ).6.2. Hitung daftar
SAMPLES + 1
poin aktifG
.6.3. Temukan pasangan poin mana yang paling dekat satu sama lain.
6.4. Update
t0
,t1
,s0
,s1
seperti yang terlihat di atas.LAIN : sebagai alternatif, hitung daftar poin pada
F
ATAU daftar poin aktifG
, kemudian cari titik mana yangF
paling dekatG(s0)
dan perbaruit0
dant1
, ATAU titik mana yangG
paling dekat denganF(t0)
dan perbaruis0
dans1
.Kembali ke langkah 3.
Masalah
Secara desain, algoritma ini akan selalu konvergen ke minimum lokal. Namun, tidak ada jaminan bahwa mereka akan bertemu dengan solusi terbaik. Secara khusus, algoritma kurva Bézier tidak terlalu bagus sama sekali, dan dalam kasus dua kurva yang berdekatan satu sama lain di banyak tempat, sayangnya Anda mungkin melewatkan solusi dengan tembakan panjang.
Tetapi seperti yang saya katakan, sebelum Anda mulai memikirkan solusi yang lebih kuat, Anda harus terlebih dahulu bereksperimen dengan yang sederhana.
sumber
1) Terjemahkan semuanya ke satu sumbu, jadi alih-alih perlu menghitung panjang satu titik ke, 'garis', 'garis' adalah, katakanlah, sumbu-Y.
Lalu, eh, diberi kurva bezier saya akan mengatakan itu sampai dengan jumlah titik kontrol.
Jika ada tiga, (awal, 'kontrol' dan akhir) saya akan melakukan semacam pemindaian (katakan masing-masing beberapa persen dan kemudian perbaiki antara yang terdekat (dengan katakanlah pendekatan 'biner').
Lebih banyak poin saya akan mencoba pasangan yang paling dekat dengan (diterjemahkan Y-Axis).
Saya yakin seorang pria matematika dapat memberikan Anda solusi yang tepat (dalam matematika) tetapi jika Anda ingin menemukan / solusi dalam permainan video Anda mungkin lebih baik dengan solusi yang sedikit ok karena solusi sebenarnya mungkin berisi beberapa jawaban ( Saya bahkan tidak berbicara tentang kekuatan pemrosesan).
sumber
Beberapa jawaban dari halaman blog Algoritma , yang dengan benar menemukan titik terdekat pada kurva bezier kuadratik yang diberikan.
Demo .
sumber
Untuk kurva Bezier - garis lurus, cara paling akurat untuk menemukan jawabannya adalah dengan melakukan hal berikut:
sumber