Algoritmi/Aproksimacija razdaljine

Izračunavanje rastojanja zajedničko za prostorne i ostale algoritme pretraživanja, kao što je i za komjutersku igru fizička mašina. Međutim, zajedničko Euklidovo rastojanje zahteva izdračunavanje kvatratnog korena , koja je često relativno teška operacija u CPU-u.

Za upoređivanje rastojanja nije potreban kvadratni koren

Dati su uređeni parovi (x1, y1) i (x2, y2), koji je bliži koordinatnom početku po Euklidovom rastojanju? Možda ćete doći u iskušenje da izračunate ta dva Euklidova rastojanja i uporediti ih:

d1 = sqrt(x1^2 + y1^2)
d2 = sqrt(x2^2 + y2^2)
return d1 > d2

Ali su ti kvadratni koreni često teški za izračunavanje, ali čak šta više, ne morate sve da ih izračunate. Umesto toga, uradite ovo:

dd1 = x1^2 + y1^2
dd2 = x2^2 + y2^2
return dd1 > dd2

Rezultat je totalno isti (zato što je pozitivan kvadratni koren striktno monotona funkcija). Ovo radi samo za upoređivanje rastojanja, ali ne za izračunavanje individualnih vrednosti, koje su ponekad ono što vam treba. Pogledajmo aproksimacije.

Aproksimacija Euklidovog rastojanja

Taksi/Menhetn/L1

w:taxicab distance je jedna od jednostavnijih za izračunavanje, tako da se koristi kada ima malo resursa:

Date su koordinate dveju tačaka (x1, y1) i (x2, y2).

$dx=|x1-x2|$ (w:absolute value)

$dy=|y1-y2|$

$d=dx+dy$ (taksi distanca)

Primetiti da ovo takođe možete koristiti kao "prvi prolaz", s'ozirom da je nikad niže od Euklidovog rastojanja. Možete proveriti ako su tačke sa posebnom graničnom kutijom, kao prviprolaz za proveravanje ako su sa graničnom sferom za koju ste zaista zainteresovani. Uostalom, ako proširimo ovu ideju, završićemo sa efikasnom prostornom strukturom kao što je w:Kd-tree.

Međutim, budite na oprezu da taksi distanca nije w:isotropic - ako ste u Euklidovom prostoru, taksi distance dosta toga menjaju u zavisnosti od toga na koji je način vaša "mreža" poravnana. Ovo može dovesti do velikih odstupanja ako ga koristite kao zamenu za Euklidovo rastojanje. Aproksimacije osmougaonog rastojanja pomažu da skinemo neke od problematičnih uglova, davajući bolju izotropiju:

Osmougao

Brza aproksimacija 2D razdaljine osnovana na osmougaonoj granici se može izračunati na sledeći način.

Date su dve tačke $(p_{x},p_{y})$ i $(q_{x},q_{y})$, Neka $dx=|p_{x}-q_{x}|$ (w:absolute value) i $dy=|p_{y}-q_{y}|$. Ako $dy>dx$, aproksimirana razdanjina je $0.41dx+0.941246dy$.

Pre nekoliko godina, pronašao sam sličan algoritam aproksimacije razdaljine koristeći tri uslova, umesto samo 2, što je tačnije i pošto koristi stepen 2 od imenioca za koeficijente, može biti implementiran bez korišćena hardvera za deljenje. Formula je: 1007/1024 max(|x|,|y|) + 441/1024 min(|x|,|y|) - if ( max(|x|.|y|)<16min(|x|,|y|), 40/1024 max(|x|,|y|), 0 ). Takođe, moguće je implementirati aproksimaciju razdaljine bez korišćenja množenja i deljenja kada imate ograničen hardver: ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) + ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 ). Ovo je baš kao min max algoritam sa 2 koeficijenta koji je pokazan ranije, ali sa koeficijentima 123/128 i 51/128. Imam članak o tome nahttp://web.oroboro.com:90/rafael/docserv.php/index/programming/article/distance --Rafael

(Navodno, taj članak je prebačen ovde: http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml ?)

(Izvor za ovo poglavlje)

---