Алгоритми/Апроксимација раздаљине

Израчунавање растојања заједничко за просторне и остале алгоритме претраживања, као што је и за комјутерску игру физичка машина. Међутим, заједничко Еуклидово растојање захтева издрачунавање кватратног корена , која је често релативно тешка операција у CPU-у.

За упоређивање растојања није потребан квадратни корен

Дати су уређени парови (x1, y1) и (x2, y2), који је ближи координатном почетку по Еуклидовом растојању? Можда ћете доћи у искушење да израчунате та два Еуклидова растојања и упоредити их:

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

Али су ти квадратни корени често тешки за израчунавање, али чак шта више, не морате све да их израчунате. Уместо тога, урадите ово:

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

Резултат је тотално исти (зато што је позитиван квадратни корен стриктно монотона функција). Ово ради само за упоређивање растојања, али не за израчунавање индивидуалних вредности, које су понекад оно што вам треба. Погледајмо апроксимације.

Апроксимација Еуклидовог растојања

Такси/Менхетн/Л1

w:taxicab distance је једна од једноставнијих за израчунавање, тако да се користи када има мало ресурса:

Дате су координате двеју тачака (x1, y1) и (x2, y2).

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

$dy=|y1-y2|$

$d=dx+dy$ (такси дистанца)

Приметити да ово такође можете користити као "први пролаз", с'озиром да је никад ниже од Еуклидовог растојања. Можете проверити ако су тачке са посебном граничном кутијом, као првипролаз за проверавање ако су са граничном сфером за коју сте заиста заинтересовани. Уосталом, ако проширимо ову идеју, завршићемо са ефикасном просторном структуром као што је w:Kd-tree.

Међутим, будите на опрезу да такси дистанца није w:isotropic - ако сте у Еуклидовом простору, такси дистанце доста тога мењају у зависности од тога на који је начин ваша "мрежа" поравнана. Ово може довести до великих одступања ако га користите као замену за Еуклидово растојање. Апроксимације осмоугаоног растојања помажу да скинемо неке од проблематичних углова, давајући бољу изотропију:

Осмоугао

Брза апроксимација 2D раздаљине основана на осмоугаоној граници се може израчунати на следећи начин.

Дате су две тачке $(p_{x},p_{y})$ и $(q_{x},q_{y})$, Нека $dx=|p_{x}-q_{x}|$ (w:absolute value) и $dy=|p_{y}-q_{y}|$. Ако $dy>dx$, апроксимирана раздањина је $0.41dx+0.941246dy$.

Пре неколико година, пронашао сам сличан алгоритам апроксимације раздаљине користећи три услова, уместо само 2, што је тачније и пошто користи степен 2 од имениоца за коефицијенте, може бити имплементиран без коришћена хардвера за дељење. Формула је: 1007/1024 max(|x|,|y|) + 441/1024 min(|x|,|y|) - if ( max(|x|.|y|)<16min(|x|,|y|), 40/1024 max(|x|,|y|), 0 ). Такође, могуће је имплементирати апроксимацију раздаљине без коришћења множења и дељења када имате ограничен хардвер: ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) + ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 ). Ово је баш као min max алгоритам са 2 коефицијента који је показан раније, али са коефицијентима 123/128 и 51/128. Имам чланак о томе наhttp://web.oroboro.com:90/rafael/docserv.php/index/programming/article/distance --Rafael

(Наводно, тај чланак је пребачен овде: http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml ?)

(Извор за ово поглавље)

---