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