diff options
Diffstat (limited to 'algorithm.mod/algorithm.bmx')
| -rw-r--r-- | algorithm.mod/algorithm.bmx | 645 |
1 files changed, 322 insertions, 323 deletions
diff --git a/algorithm.mod/algorithm.bmx b/algorithm.mod/algorithm.bmx index 065a254..c449f5f 100644 --- a/algorithm.mod/algorithm.bmx +++ b/algorithm.mod/algorithm.bmx @@ -1,323 +1,322 @@ -' Copyright (c) 2006 Ian Cowburn -' -' Permission is hereby granted, free of charge, to any person obtaining a copy of -' this software and associated documentation files (the "Software"), to deal in -' the Software without restriction, including without limitation the rights to -' use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies -' of the Software, and to permit persons to whom the Software is furnished to do -' so, subject to the following conditions: -' -' The above copyright notice and this permission notice shall be included in all -' copies or substantial portions of the Software. -' -' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -' IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -' FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -' AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -' LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -' OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -' SOFTWARE. -' -' $Id$ -' -Rem -bbdoc: noddybox.algorithm -EndRem -Module noddybox.algorithm - -ModuleInfo "Framework: Various algorithm routines" -ModuleInfo "Copyright: Ian Cowburn -- released under the MIT License" -ModuleInfo "Author: Ian Cowburn" -ModuleInfo "Version: $Revision$" - -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 double points from algorithms. -EndRem -Type TAlgoPointD - 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: Create a point. - returns: Newly created point. - about: @x and @y are initialised with the passed parameters. - EndRem - Function Create:TAlgoPointD(x:Double, y:Double) - Local o:TAlgoPointD=New TAlgoPointD - 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: Rotates a point. -returns: The rotated point. -about: @x, @y are rotated around 0,0 by @angle, which is the value in degrees multiplied by ten. -about: To speed things up a simple 3600 element lookup table is used, so @angle <u>must</u> be 0 to 3599 inclusive, or a runtime error will result. -EndRem -Function DoRotate:TAlgoPoint(x:Int, y:Int, angle:Int) - AlgoStatic.Init() - - Local dx:Double=x - Local dy:Double=y - Local dco:Double=AlgoStatic.co[angle] - Local dsi:Double=algoStatic.si[angle] - - Return TAlgoPoint.Create(dco*dx+(-dsi)*dy,dsi*dx+dco*dy) -End Function - -Rem -bbdoc: Rotates a point (double version) -returns: The rotated point. -about: @x, @y are rotated around 0,0 by @angle, which is the value in degrees multiplied by ten. -about: To speed things up a simple 3600 element lookup table is used, so @angle <u>must</u> be 0 to 3599 inclusive, or a runtime error will result. -EndRem -Function DoRotateD:TAlgoPointD(x:Double, y:Double, angle:Int) - AlgoStatic.Init() - - Local dco:Double=AlgoStatic.co[angle] - Local dsi:Double=algoStatic.si[angle] - - Return TAlgoPointD.Create(dco*x+(-dsi)*y,dsi*x+dco*y) -End Function - -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*10],y+r*AlgoStatic.co[f*10]) - 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[3600] - co=New Double[3600] - - For Local f:Int=0 To 3599 - si[f]=Sin(Double(f)/10) - co[f]=Cos(Double(f)/10) - Next - - done=True - EndIf - End Function -End Type - -Function Square:Double(x:Double) - Return x*x -End Function +' Copyright (c) 2006 Ian Cowburn
+'
+' Permission is hereby granted, free of charge, to any person obtaining a copy of
+' this software and associated documentation files (the "Software"), to deal in
+' the Software without restriction, including without limitation the rights to
+' use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+' of the Software, and to permit persons to whom the Software is furnished to do
+' so, subject to the following conditions:
+'
+' The above copyright notice and this permission notice shall be included in all
+' copies or substantial portions of the Software.
+'
+' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+' IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+' FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+' AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+' LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+' OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+' SOFTWARE.
+'
+' $Id$
+'
+Rem
+bbdoc: noddybox.algorithm
+EndRem
+Module noddybox.algorithm
+
+ModuleInfo "Framework: Various algorithm routines"
+ModuleInfo "Copyright: Ian Cowburn -- released under the MIT License"
+ModuleInfo "Author: Ian Cowburn"
+ModuleInfo "Version: $Revision$"
+
+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 double points from algorithms.
+EndRem
+Type TAlgoPointD
+ 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: Create a point.
+ returns: Newly created point.
+ about: @x and @y are initialised with the passed parameters.
+ EndRem
+ Function Create:TAlgoPointD(x:Double, y:Double)
+ Local o:TAlgoPointD=New TAlgoPointD
+ 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: Rotates a point.
+returns: The rotated point.
+about: @x, @y are rotated around 0,0 by @angle, which is the value in degrees multiplied by ten.
+about: To speed things up a simple 3600 element lookup table is used, so @angle <u>must</u> be 0 to 3599 inclusive, or a runtime error will result.
+EndRem
+Function DoRotate:TAlgoPoint(x:Int, y:Int, angle:Int)
+ AlgoStatic.Init()
+
+ Local dx:Double=x
+ Local dy:Double=y
+ Local dco:Double=AlgoStatic.co[angle]
+ Local dsi:Double=algoStatic.si[angle]
+
+ Return TAlgoPoint.Create(dco*dx+(-dsi)*dy,dsi*dx+dco*dy)
+End Function
+
+Rem
+bbdoc: Rotates a point (double version)
+returns: The rotated point.
+about: @x, @y are rotated around 0,0 by @angle, which is the value in degrees multiplied by ten.
+about: To speed things up a simple 3600 element lookup table is used, so @angle <u>must</u> be 0 to 3599 inclusive, or a runtime error will result.
+EndRem
+Function DoRotateD:TAlgoPointD(x:Double, y:Double, angle:Int)
+ AlgoStatic.Init()
+
+ Local dco:Double=AlgoStatic.co[angle]
+ Local dsi:Double=algoStatic.si[angle]
+
+ Return TAlgoPointD.Create(dco*x+(-dsi)*y,dsi*x+dco*y)
+End Function
+
+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*10],y+r*AlgoStatic.co[f*10])
+ 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[3600]
+ co=New Double[3600]
+
+ For Local f:Int=0 To 3599
+ si[f]=Sin(Double(f)/10)
+ co[f]=Cos(Double(f)/10)
+ Next
+
+ done=True
+ EndIf
+ End Function
+End Type
+
+Function Square:Double(x:Double)
+ Return x*x
+End Function
|