From 6c0b11a6bb632a5c7cd29ad8a92ce31fe929c194 Mon Sep 17 00:00:00 2001 From: Ian C Date: Wed, 8 Apr 2020 21:23:22 +0000 Subject: Removed Strict -- doesn't seem to like it anymore. --- algorithm.mod/algorithm.bmx | 645 ++++++++++++++++++++++---------------------- 1 file changed, 322 insertions(+), 323 deletions(-) (limited to 'algorithm.mod') 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 must 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 must 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 must 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 must 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 -- cgit v1.2.3