base:approximation_to_distance
This is an old revision of the document!
Classic distance formula is d= SQR( (x2-x1)^2 + (y2-y1)^2)) and it is well known that if you are comparing the magnitude of two distances you can avoid doing the square root operation as the square of the distances sort in the same order. However, to avoid the square root and the multiplication is the intent of this approximation.
The following approximation is based on a combination of linear components of the min and max functions.
The formula is d = max(|xd|, |yd|) + 1/2 × min(|xd|, |yd|) where xd = (x1-x2) and yd = (y1-y2)
Note that for 6502 we will use a shift right to calculate the multiply by 1/2.
; gives approximate distance from (x1,y1) to (x2,y2) ; with only overestimations, and then never by more ; than (9/8) + one bit uncertainty. lda x1 ; x1 - x2 sec sbc x2 sta xd bpl .posxdiff ; abs() lda #00 ; sec sbc xd .posxdiff: sta xd lda y1 ; y1 - y2 sec sbc y2 sta yd bpl .posydiff ; abs() lda #00 sec sbc yd .posydiff: cmp xd bcs .ygreater lsr ; ydelta / 2 adc xd ; + xdelta rts .ygreater: sta yd lda xd lsr ; xdelta / 2 cls adc yd ; + ydelta rts
derivation: A FAST APPROXIMATION TO THE HYPOTENUSE page 427 of Graphics Gems 1
base/approximation_to_distance.1581255826.txt.gz · Last modified: 2020-02-09 14:43 by djmips