Ooops
November 28, 2020, 10:54:32 AM

Author Topic: [bb] 2d distance calculation and approximation by Shagwana [ 1+ years ago ]  (Read 579 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : 2d distance calculation and approximation
Author : Shagwana
Posted : 1+ years ago

Description : Full credit to the code under is given to an artical on <a href="http://www.flipcode.com/" target="_blank">www.flipcode.com[/url]. For a full understanding of what is going on in the code please read <a href="http://www.flipcode.com/articles/article_fastdistance.shtml" target="_blank">this[/url].

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 ...
Code: [Select]
;you have a line from ...x1,y1... to ...x2,y2...
;...
xDelta=abs(x2-x1)
yDelta=abs(y2-y1)
Distance=Calc_Distance(xDelta,yDelta)
;...


Code :
Code: BlitzBasic
  1. ;
  2. ; Distance algos (2d) and some approximation methods
  3. ;
  4. ; Full credit for algo to this artical on flipcode - http://www.flipcode.com/articles/article_fastdistance.shtml
  5. ;
  6.  
  7.  
  8. ;Usefull functions follow ....
  9.  
  10.  
  11. ;True distance formular
  12. Function Calc_Distance(XDelta%,YDelta%)
  13.   Return Sqr((XDelta*XDelta)+(YDelta*YDelta))
  14.   End Function
  15.  
  16.  
  17. ;Approximation calculation, faster then sqr method of calculation
  18. Function Approx_Distance(XDelta%,YDelta%)
  19.   Local max,min,approx
  20.   XDelta=Abs(XDelta)
  21.   YDelta=Abs(YDelta)
  22.   If XDelta>YDelta
  23.     max=XDelta
  24.     min=YDelta
  25.     Else
  26.     max=YDelta
  27.     min=XDelta
  28.     EndIf
  29.   approx=(max*1007)+(min*441)
  30.   If (max<(min Shl 2))
  31.     approx=approx-(max*111)
  32.     Else
  33.     approx=approx-(min*441)
  34.     EndIf
  35.   Return ((approx+512) Shr 10)
  36.   End Function
  37.  
  38.  
  39. ;Integer shift only method of the above function, should be faster
  40. Function FasterApprox_Distance(XDelta%,YDelta%)
  41.   Local max,min
  42.   If XDelta>YDelta
  43.     max=XDelta
  44.     min=YDelta
  45.     Else
  46.     max=YDelta
  47.     min=XDelta
  48.     EndIf
  49.   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)
  50.   End Function
  51.  
  52.  
  53. ;Example code follows ....
  54.  
  55.  
  56.  
  57. Const DRAW_DISTANCE_LINE=200
  58.  
  59. ;Example code
  60. Graphics 800,600,16,1
  61. SetBuffer FrontBuffer()
  62. Cls
  63.  
  64.  
  65. ;First, render the 3 distance quarters.
  66. Text 0,0,"Plotting distance images, please wait"
  67.  
  68. ;Create and plot the image
  69. pImage1=CreateImage(400,400)
  70. SetBuffer ImageBuffer(pImage1)
  71. For x=0 To 399
  72.   For y=0 To 399
  73.     dist=Calc_Distance(x,y)
  74.     If dist>255
  75.       Color 255,dist-255,255
  76.       Else
  77.       Color dist,dist,dist
  78.       EndIf
  79.     If dist=DRAW_DISTANCE_LINE
  80.       Color 0,0,255
  81.       EndIf
  82.     Plot x,y
  83.     Next
  84.   Next
  85.  
  86. ;Create and plot the image
  87. pImage2=CreateImage(400,400)
  88. SetBuffer ImageBuffer(pImage2)
  89. For x=0 To 399
  90.   For y=0 To 399
  91.     dist=Approx_Distance(x,y)
  92.     If dist>255
  93.       Color 255,dist-255,255
  94.       Else
  95.       Color dist,dist,dist
  96.       EndIf
  97.     If dist=DRAW_DISTANCE_LINE
  98.       Color 0,0,255
  99.       EndIf
  100.     Plot x,y
  101.     Next
  102.   Next
  103.  
  104.  
  105. ;Create and plot the image
  106. pImage3=CreateImage(400,400)
  107. SetBuffer ImageBuffer(pImage3)
  108. For x=0 To 399
  109.   For y=0 To 399
  110.     dist=FasterApprox_Distance(x,y)
  111.     If dist>255
  112.       Color 255,dist-255,255
  113.       Else
  114.       Color dist,dist,dist
  115.       EndIf
  116.     If dist=DRAW_DISTANCE_LINE
  117.       Color 0,0,255
  118.       EndIf
  119.     Plot x,y
  120.     Next
  121.   Next
  122.  
  123.  
  124.  
  125.  
  126. ShowImage=pImage1
  127. msg$=""
  128. Repeat
  129.  
  130.  
  131.   SetBuffer BackBuffer()
  132.   Flip
  133.   Cls
  134.  
  135.   Color 255,255,255
  136.   Text 0,0,"keys: [1] show sqr()     [2] show approx      [3] show faster approx     [esc] quit"
  137.  
  138.   ;When key is pressed, swap the image being displayed...  
  139.   If KeyDown(2)=True Then ShowImage=pImage1    ;key presses = show different image
  140.   If KeyDown(3)=True Then ShowImage=pImage2
  141.   If KeyDown(4)=True Then ShowImage=pImage3
  142.  
  143.   DrawBlock ShowImage,100,100
  144.  
  145.   Select ShowImage
  146.     Case pImage1
  147.     Text 0,24,"showing Calc_Distance()"
  148.     Case pImage2
  149.     Text 0,24,"showing Approx_Distance()"
  150.     Case pImage3
  151.     Text 0,24,"showing FasterApprox_Distance()"
  152.     End Select
  153.  
  154.   Until KeyDown(1)=True
  155. End


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal