Bisakah saya menyederhanakan ketimpangan "jarak (p1, p2) <jarak (p1, p3)?"

14

Saya sedang mengerjakan beberapa logika vektor, jadi saya bertanya: dapatkah saya menghemat waktu prosesor dengan menyederhanakan ketimpangan ini:

distance(vector1, vector2) < distance(vector1, vector3)

Saya melihat itu vector1diulang dalam kedua kasus.

vector Filip Dimitrovski
sumber
10
Hanya catatan singkat: metode Anda saat ini sangat mudah dibaca dan fungsinya dapat langsung dipahami. Beberapa jawaban ini dapat menyelesaikan tugas yang Anda minta, tetapi jauh lebih tidak jelas. Ini bagus jika kinerja adalah esensi, tetapi pastikan untuk berkomentar dengan benar untuk menjelaskan hilangnya kejelasan.
MikeS
3
Untuk melanjutkan komentar @ MikeS, kinerja seharusnya hanya menjadi esensi dalam kasus-kasus seperti ini jika Anda telah melakukan analisis atau pembuatan profil dan telah mengidentifikasi panggilan ini sebagai hambatan. Maintainability mengalahkan kinerja mentah jika kita berbicara perbedaan antara 305fps dan 303fps.
Phoshi

Jawaban:

24

Ya , Anda dapat menyederhanakan ini. Pertama, berhentilah menyebut mereka vektor. Mereka adalah poin. Sebut saja mereka A, Bdan C.

Jadi, Anda menginginkan ini:

dist(A, B) < dist(A, C)

Ganti jarak dengan jarak kuadrat, lalu dengan produk titik (dari definisi panjang Euclidean . Ganti ACdengan AB + BC(sekarang ini adalah vektor nyata). Perluas, sederhanakan, faktor:

dist(A, B)² < dist(A, C)²
dot(AB, AB) < dot(AC, AC)
dot(AB, AB) < dot(AB + BC, AB + BC)
dot(AB, AB) < dot(AB, AB) + dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC + 2 AB, BC)

Anda disana:

dot(AB + AC, BC) > 0

Dengan notasi vektor Anda:

dot(v2 - v1 + v3 - v1, v3 - v2) > 0

Itu adalah beberapa tambahan dan satu titik produk daripada dua produk titik sebelumnya.

sam hocevar
sumber
Bisakah Anda menjelaskan bagaimana Anda bisa mengganti a + b b = a + c c dengan versi produk titik?
TravisG
2
@ TravisG Saya tidak yakin dengan apa yang Anda minta. Jika pertanyaan Anda adalah mengapa dist(A, B)²sama dot(AB, AB), pertanyaan itu berasal dari definisi panjang Euclidean .
sam hocevar
2
Jelas ini memang (agak) menyederhanakan persamaan secara matematis, tetapi tidak harus "menghemat waktu prosesor" untuk OP. Ini menghasilkan lebih banyak kerumitan dan lebih banyak perhitungan daripada hanya menghapus akar kuadrat dari persamaan jarak asli.
MichaelHouse
1
Koreksi saya jika saya salah tetapi dua produk titik adalah 5 operasi per produk titik ditambah dua substraksi vec3 yang merupakan total 16 operasi, cara Anda memiliki 3 substraksi vec3 ditambah Penambahan yang membuat 12 operasi ditambah produk dot membuat 17.
Luis W
2
Cukup menarik, hasilnya adalah produk titik dari dua diagonal yang berlawanan dari jajar genjang. Tapi itu tidak relevan. Yang ingin saya katakan adalah bahwa tidak ada jumlah luar biasa yang bisa diperoleh dari penyederhanaan penuh ini ; seperti yang disebutkan orang lain, jumlah yang layak untuk mengaburkan atau menyulitkan apa yang sebenarnya Anda coba hitung. Namun, Anda pasti ingin menggunakan langkah pertama. Menghindari akar kuadrat yang tidak perlu selalu sepadan. Hanya membandingkan Kuadrat jarak adalah sama, karena jarak pasti positif, bahkan di bidang kompleks.
TASagent
16

Iya. Dengan asumsi distancefungsi Anda menggunakan akar kuadrat, Anda dapat menyederhanakan ini dengan menghapus akar kuadrat.

Ketika mencoba menemukan yang lebih besar (atau lebih kecil) dari jarak, x^2 > y^2masih berlaku untuk x > y.

Namun, upaya lebih lanjut untuk menyederhanakan persamaan secara matematis sepertinya tidak ada gunanya. Jarak antara vector1dan vector2tidak sama dengan jarak antara vector1dan vector3. Sementara persamaan dapat disederhanakan secara matematis seperti yang ditunjukkan oleh jawaban Sam , bentuknya saat ini mungkin sesederhana yang akan Anda dapatkan dari perspektif penggunaan prosesor.

MichaelHouse
sumber
Saya tidak memiliki cukup perwakilan, tetapi saya akan karena secara fundamental tidak benar, saya percaya: "dapatkah saya menghemat waktu prosesor dengan menyederhanakan ketidaksetaraan ini?" Jawabannya iya.
sangat bingung
Jawabannya hanya ya jika persamaan jarak menggunakan akar kuadrat. Yang saya sebutkan.
MichaelHouse
Poin yang benar, saya akan menarik kembali pernyataan saya. Namun, itu adalah 99% dijamin bahwa pengguna berarti jarak euclidean sqrt (jumlah (perbedaan dimensi kuadrat))
sangat bingung
@ tidak terselesaikan Cukup adil, saya telah mengubah urutan jawaban saya untuk menyatakan skenario yang paling mungkin (99%) pertama.
MichaelHouse
2
Ya, pengalaman saya adalah ketika Anda berurusan dengan hal-hal semacam ini fungsi DistanceSquared sangat berguna. Sama jelas dan menghindari operasi sqrt yang mahal.
Loren Pechtel
0

Beberapa matematika bisa membantu.

Apa yang Anda coba lakukan adalah:

<v1, v2> < <v1, v3> =>
sqrt((y2-y1)^2+(x2-x1)^2) < sqrt((y3-y1)^2+(x3-x1)^2) =>
y2^2 - 2*y2y1 + y1^2 + x2^2 - 2*x2x1 + x1^2 < y3^2 - 2*y3y1 + y1^2 + x3^2 - 2*x3x1 + x1^2

Dari apa yang dapat Anda hapus variabel berulang dan kelompok beberapa orang lain. Operasi yang harus Anda periksa adalah:

y3^2 - y2^2 - 2*y1(y3-y2) + x3^2 - x2^2 - 2*x1(x3-x2) > 0

Semoga ini bisa membantu.

j4nSolo
sumber
-1

Pertanyaan sebenarnya adalah bagaimana cara mengurangi perhitungan untuk menentukan objek terdekat?

Mengoptimalkan ini sering dilakukan dalam permainan, meskipun dengan semua optimisasi itu harus dipandu profil dan, seringkali, tidak menyederhanakan banyak hal.

Cara untuk menghindari perhitungan jarak yang tidak perlu untuk menentukan hal yang terdekat - atau semua hal dalam rentang tertentu - adalah dengan menggunakan indeks spasial, misalnya, sebuah octree .

Ini hanya bermanfaat jika ada sejumlah besar objek. Untuk hanya tiga objek, tidak mungkin untuk membayar dan tentu saja tidak menyederhanakan kode.

Akan
sumber
4
Saya pikir pertanyaan sebenarnya cukup mudah, dan jawaban ini tidak membahasnya. Jika Anda ingin berspekulasi tentang pertanyaan OP yang lebih dalam, tidak dinyatakan yang harus benar-benar dilakukan sebagai komentar jika Anda tidak akan benar-benar menjawab pertanyaan yang diajukan.
Saya downvoting ini karena memohon kemungkinan optimasi prematur bukanlah jawaban untuk masalah di mana optimasi eksplisit tidak merugikan keterbacaan, pemeliharaan kode, juga tidak mendorong praktik yang tidak jelas. Ketika Anda benar-benar dapat menulis kode sederhana dan optimal, mengapa tidak melakukannya? Tentu saja tidak ada salahnya untuk melakukannya, bahkan jika Anda memiliki rencana tingkat yang lebih tinggi (tidak ada pengembang game yang akan menolak beberapa mikrodetik tambahan per frame, terutama pada konsol).
teodron
@teodron: "Ketika Anda benar-benar dapat menulis kode sederhana dan dioptimalkan, mengapa tidak melakukannya?" - Karena OP (dan sekarang, kami) sekarang telah menghabiskan waktu yang tidak dapat diabaikan untuk mengoptimalkan sesuatu yang mungkin tidak memberinya manfaat apa pun.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft Saya setuju dengan ini sebagai minor (maka optimasi tidak signifikan jika digunakan untuk beberapa ratus panggilan per frame, tetapi jika faktor besarnya meningkat hingga ribuan, semuanya pasti berubah). Namun, kita semua bebas untuk tidak membuang waktu mencoba menjawab / mengoptimalkan sesuatu yang kita anggap tidak layak. OP meminta satu hal, orang berasumsi OP tidak mengetahui strategi tingkat tinggi dan praktik pembuatan profil. Saya pribadi lebih suka membuat komentar seperti itu dalam komentar, bukan dalam jawaban. Maaf karena begitu verbose :(.
teodron
-3

itu tergantung pada apa output jarak (v1, v2)

jika itu adalah desimal (float atau double) pada suatu vektor, kemungkinan distancequared akan jauh lebih cepat

RoughPlace
sumber
5
Saya tidak melihat apa floathubungannya dengan apa pun.
MichaelHouse
saya maksud melayang di atas vektor lain hanya tidak dijelaskan dengan baik (dan saya pikir Anda tahu itu)
RoughPlace
5
Saya tidak sengaja salah paham. Saya masih tidak yakin apa yang Anda maksud. Saya tidak tahu mengapa fungsi jarak akan mengembalikan vektor.
MichaelHouse