path: root/algorithm.mod/algorithm.bmx

' 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