2d distance calculation and approximation

This code has been declared by its author to be Public Domain code.

2d distance calculation and approximation by Shagwana

2003

Full credit to the code under is given to an artical on www.flipcode.com. For a full understanding of what is going on in the code please read this.

Some work is still required in order to handle negative delta's. By Delta, I mean the distance in the X and Y of the line, for example.

Typical use of these functions goes a bit like ...

;you have a line from ...x1,y1... to ...x2,y2...
;...
xDelta=abs(x2-x1)
yDelta=abs(y2-y1)
Distance=Calc_Distance(xDelta,yDelta)
;...

;
; Distance algos (2d) and some approximation methods
;
; Full credit for algo to this artical on flipcode - http://www.flipcode.com/articles/article_fastdistance.shtml
;


;Usefull functions follow ....


;True distance formular
Function Calc_Distance(XDelta%,YDelta%)
  Return Sqr((XDelta*XDelta)+(YDelta*YDelta))
  End Function 


;Approximation calculation, faster then sqr method of calculation
Function Approx_Distance(XDelta%,YDelta%)
  Local max,min,approx
  XDelta=Abs(XDelta)
  YDelta=Abs(YDelta)
  If XDelta>YDelta
    max=XDelta
    min=YDelta
    Else
    max=YDelta
    min=XDelta
    EndIf
  approx=(max*1007)+(min*441)
  If (max<(min Shl 2))
    approx=approx-(max*111)
    Else
    approx=approx-(min*441)
    EndIf
  Return ((approx+512) Shr 10)
  End Function 


;Integer shift only method of the above function, should be faster
Function FasterApprox_Distance(XDelta%,YDelta%)
  Local max,min
  If XDelta>YDelta
    max=XDelta
    min=YDelta
    Else
    max=YDelta
    min=XDelta
    EndIf
  Return (((max Shl 8)+(max Shl 3)-(max Shl 4)-(max Shl 1)+(min Shl 7)-(min Shl 5)+(min Shl 3)-(min Shl 1)) Shr 8)
  End Function 


;Example code follows ....



Const DRAW_DISTANCE_LINE=200

;Example code
Graphics 800,600,16,1
SetBuffer FrontBuffer()
Cls


;First, render the 3 distance quarters.
Text 0,0,"Plotting distance images, please wait"

;Create and plot the image
pImage1=CreateImage(400,400)
SetBuffer ImageBuffer(pImage1)
For x=0 To 399
  For y=0 To 399
    dist=Calc_Distance(x,y)
    If dist>255
      Color 255,dist-255,255
      Else
      Color dist,dist,dist
      EndIf
    If dist=DRAW_DISTANCE_LINE
      Color 0,0,255
      EndIf
    Plot x,y
    Next
  Next

;Create and plot the image
pImage2=CreateImage(400,400)
SetBuffer ImageBuffer(pImage2)
For x=0 To 399
  For y=0 To 399
    dist=Approx_Distance(x,y)
    If dist>255
      Color 255,dist-255,255
      Else
      Color dist,dist,dist
      EndIf
    If dist=DRAW_DISTANCE_LINE
      Color 0,0,255
      EndIf
    Plot x,y
    Next
  Next


;Create and plot the image
pImage3=CreateImage(400,400)
SetBuffer ImageBuffer(pImage3)
For x=0 To 399
  For y=0 To 399
    dist=FasterApprox_Distance(x,y)
    If dist>255
      Color 255,dist-255,255
      Else
      Color dist,dist,dist
      EndIf
    If dist=DRAW_DISTANCE_LINE
      Color 0,0,255
      EndIf
    Plot x,y
    Next
  Next




ShowImage=pImage1
msg$=""
Repeat


  SetBuffer BackBuffer() 
  Flip
  Cls

  Color 255,255,255
  Text 0,0,"keys: [1] show sqr()     [2] show approx      [3] show faster approx     [esc] quit"

  ;When key is pressed, swap the image being displayed...  
  If KeyDown(2)=True Then ShowImage=pImage1    ;key presses = show different image
  If KeyDown(3)=True Then ShowImage=pImage2
  If KeyDown(4)=True Then ShowImage=pImage3

  DrawBlock ShowImage,100,100

  Select ShowImage
    Case pImage1
    Text 0,24,"showing Calc_Distance()"
    Case pImage2
    Text 0,24,"showing Approx_Distance()" 
    Case pImage3
    Text 0,24,"showing FasterApprox_Distance()" 
    End Select

  Until KeyDown(1)=True
End

Comments

None.

Code Archives Forum