1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
|
Rem
bbdoc: noddybox.algorithm
EndRem
Module noddybox.algorithm
ModuleInfo "Framework: Various algorithm routines"
ModuleInfo "Copyright: Public Domain"
ModuleInfo "Author: Ian Cowburn"
ModuleInfo "Version: $Revision$"
' $Id$
Strict
Import brl.math
Import brl.linkedlist
Rem
bbdoc: Used to return integer points from algorithms.
EndRem
Type TAlgoPoint
Rem
bbdoc: The X co-ordinate of the point
EndRem
Field x:Int
Rem
bbdoc: The Y co-ordinate of the point
EndRem
Field y:Int
Rem
bbdoc: Create a point.
returns: Newly created point.
about: @x and @y are initialised with the passed parameters.
EndRem
Function Create:TAlgoPoint(x:Int, y:Int)
Local o:TAlgoPoint=New TAlgoPoint
o.x=x
o.y=y
Return o
End Function
End Type
Rem
bbdoc: Used to return 3D points from algorithms.
EndRem
Type TAlgoPoint3D
Rem
bbdoc: The X co-ordinate of the point
EndRem
Field x:Double
Rem
bbdoc: The Y co-ordinate of the point
EndRem
Field y:Double
Rem
bbdoc: The Z co-ordinate of the point
EndRem
Field z:Double
Rem
bbdoc: Create a point.
returns: Newly created point.
about: @x, @y and @z are initialised with the passed parameters.
EndRem
Function Create:TAlgoPoint3D(x:Double, y:Double, z:Double)
Local o:TAlgoPoint3D=New TAlgoPoint3D
o.x=x
o.y=y
o.z=z
Return o
End Function
End Type
Rem
bbdoc: Implements a Bresenham style line.
returns: A list of points making up the line.
about: @px1, @py1, @px2 and @py2 are the end points of the line.
EndRem
Function DoLine:TList(p1x:Int, p1y:Int, p2x:Int, p2y:Int)
Local list:TList=CreateList()
Local f:Int
Local dx:Int
Local dy:Int
Local ix:Int
Local iy:Int
Local incrE:Int
Local incrNE:Int
Local d:Int
Local x:Int
Local y:Int
Local ymode:Int
dx=p2x-p1x
dy=p2y-p1y
ix=Sgn(dx)
iy=Sgn(dy)
dx=Abs(dx)
dy=Abs(dy)
If dy>dx
ymode=True
d=dx*2-dy
incrE=dx*2
incrNE=(dx-dy)*2
Else
ymode=False
d=dy*2-dx
incrE=dy*2
incrNE=(dy-dx)*2
EndIf
x=p1x
y=p1y
list.AddLast(TAlgoPoint.Create(x,y))
If ymode
While y<>p2y
If d<=0
d:+incrE
y:+iy
Else
d:+incrNE
y:+iy
x:+ix
EndIf
list.AddLast(TAlgoPoint.Create(x,y))
Wend
Else
While x<>p2x
If d<=0
d:+incrE
x:+ix
Else
d:+incrNE
y:+iy
x:+ix
EndIf
list.AddLast(TAlgoPoint.Create(x,y))
Wend
EndIf
Return list
End Function
Rem
bbdoc: Returns the points for degrees 0-359 on the described circle.
returns: A list of points making up the circle.
about: @x, @y is the centre of the circle, @r it's radius.
EndRem
Function DoCircle:TAlgoPoint[](x:Int, y:Int, r:Int)
Local p:TAlgoPoint[]=New TAlgoPoint[360]
Local f:Int
AlgoStatic.Init()
For f=0 To 359
p[f]=TAlgoPoint.Create(x+r*AlgoStatic.si[f],y+r*AlgoStatic.co[f])
Next
Return p
End Function
Rem
bbdoc: Returns the points where a sphere intersects a 3D line.
returns: null if they don't intersect, one point if it intersects as a tangent, two points otherwise.
about: @x1, @y1, @z1, @x2, @y2 and @z2 describe the line. @cx, @cy, @cz and @rad describe the sphere.
about: Leave the Z co-ords as zero to do a 2D check.
EndRem
Function CircleIntersects:TAlgoPoint3D[](x1:Double, y1:Double, z1:Double, x2:Double, y2:Double, z2:Double, cx:Double, cy:Double, cz:Double, rad:Double)
Local a:Double = Square(x2-x1) + Square(y2-y1) + Square(z2-z1)
Local b:Double = 2 * ( (x2-x1)*(x1-cx) + (y2-y1)*(y1-cy) + (z2-z1)*(z1-cz) )
Local c:Double = Square(x1) + Square(y1) + Square(z1) + Square(cx) + Square(cy) + Square(cz) - 2 * ( cx*x1 + cy*y1 + cz*z1 ) - Square(rad)
Local i:Double = b*b-4*a*c
If i<0
Return Null
ElseIf i=1.0
Local m:Double = -b/(2*a)
If m<0.0 Or m>1.0
Return Null
EndIf
Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
p[0]=TAlgoPoint3D.Create( x1+m*(x2-x1), y1+m*(y2-y1), z1 + m*(z2-z1))
Return p
Else
Local e:Double = Sqr(Square(b) - 4*a*c)
Local m1:Double = (-b + e) / (2*a)
Local m2:Double = (-b - e) / (2*a)
If (m2<0.0 Or m2>1.0) And (m1<0.0 Or m1>1.0)
Return Null
ElseIf (m1<0.0 Or m1>1.0)
Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
p[0]=TAlgoPoint3D.Create( x1+m2*(x2-x1), y1+m2*(y2-y1), z1+m2*(z2-z1))
Return p
ElseIf m2<0.0 Or m2>1.0
Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
p[0]=TAlgoPoint3D.Create( x1+m1*(x2-x1), y1+m1*(y2-y1), z1+m1*(z2-z1))
Return p
Else
Local p:TAlgoPoint3D[]=New TAlgoPoint3D[2]
p[0]=TAlgoPoint3D.Create( x1+m1*(x2-x1), y1+m1*(y2-y1), z1+m1*(z2-z1))
p[1]=TAlgoPoint3D.Create( x1+m2*(x2-x1), y1+m2*(y2-y1), z1+m2*(z2-z1))
Return p
EndIf
EndIf
End Function
Private
Type AlgoStatic
Global done:Int=False
Global si:Double[]
Global co:Double[]
Function Init()
If Not done
si=New Double[360]
co=New Double[360]
For Local f:Int=0 To 359
si[f]=Sin(f)
co[f]=Cos(f)
Next
done=True
EndIf
End Function
End Type
Function Square:Double(x:Double)
Return x*x
End Function
|
