User Tools

Site Tools


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