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 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: 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

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