November 28, 2020, 10:54:32 AM

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

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] 2d distance calculation and approximation by Shagwana [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
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.
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