QuadTree - drawing a Circle

Monkey Forums/Monkey Code/QuadTree - drawing a Circle

NoOdle

(Posted 2012) [#1]

As the title suggests. Press SpaceKey to toggle the display.

Import mojo


Function PointInCircle : Bool( x : Float, y : Float, r : Float, px : Float, py : Float )
	Local dx : Float = px - x
	Local dy : Float = py - y
	If (( dx * dx ) + ( dy * dy )) > ( r * r )
		Return False
	Endif
	Return True
End Function



'smallest quad threshold
Const THRESHOLD : Float = 10.0



Class QuadNode
	
	Field x1 : Float
	Field y1 : Float
	Field x2 : Float
	Field y2 : Float
	
	Field id : Int
	
	Field children : QuadNode[]
	
	Method New( x1 : Float, y1 : Float, x2 : Float, y2 : Float )
		Self.x1 = x1
		Self.y1 = y1
		Self.x2 = x2
		Self.y2 = y2
	End Method
	
	Method Draw( flag : Bool = False )
		If children.Length <> 0
			For Local i : Int = 0 Until children.Length
				children[ i ].Draw( flag )
			Next
		Else
			SetColor 255, 255, 255
			If Self.id = 4 Then SetColor 255, 0, 0
			If Self.id = 1 Then SetColor 100, 100, 100
			If Self.id = 0 Then SetColor 255, 255, 0
			If flag = False Or flag = True And Self.id > 1 And Self.id < 4
				DrawRectOutline( x1, y1, x2 - x1, y2 - y1, 1.0)
			Endif
		Endif
	End Method


	Method Check : Int()
		Local result : Int = 0
		result = result + PointInCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, DeviceHeight() / 2.0, x1, y1 )
		result = result + PointInCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, DeviceHeight() / 2.0, x2, y1 )
		result = result + PointInCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, DeviceHeight() / 2.0, x1, y2 )
		result = result + PointInCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, DeviceHeight() / 2.0, x2, y2 )
		'this prevents a quad from containing the circle
		If result = 0
			result = PointInCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, DeviceHeight() / 2.0, ( x2 + x1 ) / 2.0, ( y2 + y1 ) / 2.0 )
		Endif
		Return result
	End Method


	Method Split()
		
		Self.id = Self.Check()
		If Self.id = 4 Or Self.id = 0 Then Return

		If Self.x2 - Self.x1 < THRESHOLD Or Self.y2 - Self.y1 < THRESHOLD Then Return

		Self.children = Self.children.Resize( 4 )
		
		Local mx : Float = ( x2 + x1 ) / 2.0
		Local my : Float = ( y2 + y1 ) / 2.0
		
		Self.children[ 0 ] = New QuadNode( x1, y1, mx, my )
		Self.children[ 1 ] = New QuadNode( mx, y1, x2, my )
		Self.children[ 2 ] = New QuadNode( x1, my, mx, y2 )
		Self.children[ 3 ] = New QuadNode( mx, my, x2, y2 )
		
		For Local i : Int = 0 Until 4
			children[ i ].Split()
		Next
		
	End Method
	


End Class




Class QuadTree

	Field root : QuadNode
	
	Method Draw( flag : Bool = False )
		root.Draw( flag )
	End Method

End Class






Class MyApp Extends App


	Field tree : QuadTree
	
	Field debug : Bool = False
	
	
	Method OnCreate()
		SetUpdateRate 60
		

		tree = New QuadTree
		tree.root = New QuadNode( 0, 0, DeviceHeight(), DeviceHeight())
		tree.root.Split()
		
	End Method
	


	Method OnUpdate()
		
		If KeyHit( KEY_SPACE )
			Self.debug = Not Self.debug
		Endif
	
	End Method
	



	Method OnRender()
		Cls 255, 255, 255
		
		'Draws Background
		SetColor 0, 0, 0
		DrawRect 0, 0, DeviceHeight(), DeviceHeight()

		'Draws Tree
		SetColor 255, 0, 0
		tree.Draw( Self.debug )
		
	End Method
	

End Class



Function Main()
	New MyApp()
End Function




'/ Draws An Rect Outline.
Function DrawRectOutline( x : Float, y : Float, w : Float, h : Float, thickness : Float = 1.0 )
	If thickness = 1.0
		DrawLine x, y, x + w, y
		DrawLine x, y, x, y + h
		DrawLine x + w, y, x + w, y + h
		DrawLine x, y + h, x + w, y + h
	Else
		DrawThickLine( x, y, x + w, y, thickness, True )
		DrawThickLine( x, y, x, y + h, thickness, True )
		DrawThickLine( x + w, y, x + w, y + h, thickness, True )
		DrawThickLine( x, y + h, x + w, y + h, thickness, True )
	Endif
End Function



'/ Draws thick line, rounded ends optional
Function DrawThickLine( x1 : Float, y1 : Float, x2 : Float, y2 : Float, thickness : Float = 2.0, rounded : Bool = False )
	Local dx : Float = x2 - x1
	Local dy : Float = y2 - y1
	Local d : Float = Sqrt( dx * dx + dy * dy )
	Local vx : Float = dx / d
	Local vy : Float = dy / d
	Local nx : Float = vy
	Local ny : Float = -vx
	Local points : Float[ 8 ]
	points[ 0 ] = x1 + ( nx * ( thickness / 2.0 ))
	points[ 1 ] = y1 + ( ny * ( thickness / 2.0 ))
	points[ 2 ] = x1 + ( -nx * ( thickness / 2.0 ))
	points[ 3 ] = y1 + ( -ny * ( thickness / 2.0 ))
	points[ 4 ] = x2 + ( -nx * ( thickness / 2.0 ))
	points[ 5 ] = y2 + ( -ny * ( thickness / 2.0 ))	
	points[ 6 ] = x2 + ( nx * ( thickness / 2.0 ))
	points[ 7 ] = y2 + ( ny * ( thickness / 2.0 ))
	DrawPoly( points )
	If rounded = True
		DrawEllipse x1, y1, thickness / 2.0, thickness / 2.0
		DrawEllipse x2, y2, thickness / 2.0, thickness / 2.0
	Endif
End Function

slenkar

(Posted 2012) [#2]

whoa nice
why do you use quadtrees to draw a circle? they seem like they could be useful for something

NoOdle

(Posted 2012) [#3]

why do you use quadtrees to draw a circle?

lol why not? Its a fun visual representation, and yes they have lots of uses! Some taken from wikipedia:

+ Spatial indexing
+ Efficient collision detection in two dimensions
+ View frustum culling of terrain data
+ Storing sparse data, such as a formatting information for a spreadsheet or for some matrix calculations
+ Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
+ Conway's Game of Life simulation program
+ State estimation
+ Quadtrees are also used in the area of fractal image analysis

DruggedBunny

(Posted 2012) [#4]

Looks cool!

NoOdle

(Posted 2012) [#5]

another update, press 1 - 4 to change the shape and press space to toggle display

Import mojo


Function PointInCircle : Bool( x : Float, y : Float, r : Float, px : Float, py : Float )
	Local dx : Float = px - x
	Local dy : Float = py - y
	If (( dx * dx ) + ( dy * dy )) > ( r * r )
		Return False
	Endif
	Return True
End Function


Function PointInRect : Bool( x : Float, y : Float, x1 : Float, y1 : Float, x2 : Float, y2 : Float )
	If x > x1 And x < x2
		If y > y1 And y < y2
			Return True
		Endif
	Endif
	Return False
End Function



Function PointInTriangle : Bool( px : Float, py : Float, tri : Float[])
	If Orientation( tri[ 0 ], tri[ 1 ], tri[ 2 ], tri[ 3 ], px, py ) <> 1
		If Orientation( tri[ 2 ], tri[ 3 ], tri[ 4 ], tri[ 5 ], px, py ) <> 1
			If Orientation( tri[ 4 ], tri[ 5 ], tri[ 0 ], tri[ 1 ], px, py ) <> 1
				Return True	
			Endif
		Endif
	Endif
End Function



Function Orientation : Int ( x1 : Float,y1 : Float, x2 : Float,y2 : Float, Px : Float,Py : Float )
	Return Sgn((x2 - x1) * (Py - y1) - (Px - x1) * (y2 - y1))
End Function





'function test point in poly
Function PointInPoly : Bool( pointX : Float, pointY : Float, tris : Float[] )
	For Local i : Int = 0 Until tris.Length / 6
		Local index : Int = i * 6
		Local tri : Float[] = tris[ index..index + 6 ]
		If PointInTriangle( pointX, pointY, tri ) = True Then Return True
	Next
	Return False
End Function



'smallest quad threshold
Const THRESHOLD : Float = 12.0



Class QuadNode
	
	Field x1 : Float
	Field y1 : Float
	Field x2 : Float
	Field y2 : Float
	
	Field id : Int
	
	Field children : QuadNode[]
	
	Method New( x1 : Float, y1 : Float, x2 : Float, y2 : Float )
		Self.x1 = x1
		Self.y1 = y1
		Self.x2 = x2
		Self.y2 = y2
	End Method
	
	Method Draw( flag : Bool = False )
		If children.Length <> 0
			For Local i : Int = 0 Until children.Length
				children[ i ].Draw( flag )
			Next
		Else
			SetColor 255, 255, 255
			If Self.id = 4 Then SetColor 255, 0, 0
			If Self.id = 1 Then SetColor 100, 100, 100
			If Self.id = 0 Then SetColor 255, 255, 0
			If flag = False Or flag = True And Self.id > 1 And Self.id < 4
				DrawRectOutline( x1, y1, x2 - x1, y2 - y1, 1.0)
			Endif
		Endif
	End Method


	Method Check : Int()
		Local result : Int = 0
		result = result + PointInPoly( x1, y1, MapPoints )
		result = result + PointInPoly( x2, y1, MapPoints )
		result = result + PointInPoly( x1, y2, MapPoints )
		result = result + PointInPoly( x2, y2, MapPoints )
		'this prevents a quad from containing the shape
		If result = 0
			result = PointInPoly( ( x2 + x1 ) / 2.0, ( y2 + y1 ) / 2.0, MapPoints )
		Endif
		Return result
	End Method


	Method Split()
		
		Self.id = Self.Check()
		If Self.id = 4 Or Self.id = 0 Then Return

		If Self.x2 - Self.x1 < THRESHOLD Or Self.y2 - Self.y1 < THRESHOLD Then Return

		Self.children = Self.children.Resize( 4 )
		
		Local mx : Float = ( x2 + x1 ) / 2.0
		Local my : Float = ( y2 + y1 ) / 2.0
		
		Self.children[ 0 ] = New QuadNode( x1, y1, mx, my )
		Self.children[ 1 ] = New QuadNode( mx, y1, x2, my )
		Self.children[ 2 ] = New QuadNode( x1, my, mx, y2 )
		Self.children[ 3 ] = New QuadNode( mx, my, x2, y2 )
		
		For Local i : Int = 0 Until 4
			children[ i ].Split()
		Next
		
	End Method
	


End Class




Class QuadTree

	Field root : QuadNode
	
	Method New()
		Self.root = New QuadNode( 0, 0, DeviceHeight(), DeviceHeight())
		Self.root.Split()		
	End Method
	
	Method Draw( flag : Bool = False )
		root.Draw( flag )
	End Method

End Class







Global MapPoints : Float[]



Class MyApp Extends App


	Field tree : QuadTree
	
	Field debug : Bool = False
	Field mode : Int = 0
	
	
	Method OnCreate()
		SetUpdateRate 60
		
		MapPoints = ComputeCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, 32 )
		
		Self.tree = New QuadTree()
	
	End Method
	


	Method OnUpdate()
		
		If KeyHit( KEY_SPACE )
			Self.debug = Not Self.debug
		Endif
		
		If KeyHit( KEY_1 )
			MapPoints = ComputeCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, 32 )
			Self.tree = New QuadTree()
		Endif
		If KeyHit( KEY_2 )
			MapPoints = ComputeCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, 4 )
			Self.tree = New QuadTree()
		Endif
		If KeyHit( KEY_3 )
			MapPoints = ComputeCircle( DeviceHeight() / 2.0, DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, -50 + DeviceHeight() / 2.0, 6 )
			Self.tree = New QuadTree()
		Endif
		If KeyHit( KEY_4 )
			MapPoints = ComputeStar( DeviceHeight() / 2.0, DeviceHeight() / 2.0, -10 + DeviceHeight() / 4.0, DeviceHeight() / 2.0 )
			Self.tree = New QuadTree()
		Endif
	
	End Method
	



	Method OnRender()
		Cls 255, 255, 255
		
		'Draws Background
		SetColor 0, 0, 0
		DrawRect 0, 0, DeviceHeight(), DeviceHeight()

		'Draws Tree
		SetColor 255, 0, 0
		tree.Draw( Self.debug )

	End Method
	

End Class



Function Main()
	New MyApp()
End Function





Function ComputeStar : Float[]( x : Float, y : Float, aRadius : Float, bRadius : Float, segments : Int = 5 )
	Local div : Float  = 360 / segments
	Local mid : Float = div / 2.0
	Local points : Float[ segments * 12 ]
	For Local i : Int = 0 Until segments
		Local index : Int = i * 12
		points[ index + 0 ] = x
		points[ index + 1 ] = y
		points[ index + 2 ] = x + Sin( i * div ) * aRadius
		points[ index + 3 ] = y + Cos( i * div ) * aRadius
		points[ index + 4 ] = x + Sin( mid ) * bRadius
		points[ index + 5 ] = y + Cos( mid ) * bRadius
		points[ index + 6 ] = x
		points[ index + 7 ] = y
		points[ index + 8 ] = points[ index + 4 ]
		points[ index + 9 ] = points[ index + 5 ]
		points[ index + 10 ] = x + Sin(( i + 1 ) * div ) * aRadius
		points[ index + 11 ] = y + Cos(( i + 1 ) * div ) * aRadius
		mid = mid + div
	Next
	Return points
End Function



Function ComputeCircle : Float[]( x : Float, y : Float, xRadius : Float, yRadius : Float, segments : Int = 5 )
	Local div : Float = 360.0 / Float( segments )
	Local points : Float[ segments * 6 ]
	For Local i : Int = 0 Until segments
		Local index : Int = i * 6
		points[ index + 0 ] = x
		points[ index + 1 ] = y
		points[ index + 2 ] = x + Sin( i * div ) * xRadius
		points[ index + 3 ] = y + Cos( i * div ) * xRadius
		points[ index + 4 ] = x + Sin(( i + 1 ) * div ) * xRadius
		points[ index + 5 ] = y + Cos(( i + 1 ) * div ) * yRadius
	Next
	Return points
End Function



'/ Draws An Rect Outline.
Function DrawRectOutline( x : Float, y : Float, w : Float, h : Float, thickness : Float = 1.0 )
	If thickness = 1.0
		DrawLine x, y, x + w, y
		DrawLine x, y, x, y + h
		DrawLine x + w, y, x + w, y + h
		DrawLine x, y + h, x + w, y + h
	Else
		DrawThickLine( x, y, x + w, y, thickness, True )
		DrawThickLine( x, y, x, y + h, thickness, True )
		DrawThickLine( x + w, y, x + w, y + h, thickness, True )
		DrawThickLine( x, y + h, x + w, y + h, thickness, True )
	Endif
End Function



'/ Draws thick line, rounded ends optional
Function DrawThickLine( x1 : Float, y1 : Float, x2 : Float, y2 : Float, thickness : Float = 2.0, rounded : Bool = False )
	Local dx : Float = x2 - x1
	Local dy : Float = y2 - y1
	Local d : Float = Sqrt( dx * dx + dy * dy )
	Local vx : Float = dx / d
	Local vy : Float = dy / d
	Local nx : Float = vy
	Local ny : Float = -vx
	Local points : Float[ 8 ]
	points[ 0 ] = x1 + ( nx * ( thickness / 2.0 ))
	points[ 1 ] = y1 + ( ny * ( thickness / 2.0 ))
	points[ 2 ] = x1 + ( -nx * ( thickness / 2.0 ))
	points[ 3 ] = y1 + ( -ny * ( thickness / 2.0 ))
	points[ 4 ] = x2 + ( -nx * ( thickness / 2.0 ))
	points[ 5 ] = y2 + ( -ny * ( thickness / 2.0 ))	
	points[ 6 ] = x2 + ( nx * ( thickness / 2.0 ))
	points[ 7 ] = y2 + ( ny * ( thickness / 2.0 ))
	DrawPoly( points )
	If rounded = True
		DrawEllipse x1, y1, thickness / 2.0, thickness / 2.0
		DrawEllipse x2, y2, thickness / 2.0, thickness / 2.0
	Endif
End Function

slenkar

(Posted 2012) [#6]

Nice, I think I need quadtrees to see if many people are close enough on a map.

Would you mind giving a small explanation of how to do that with quadtrees?

JIM	(Posted 2012) [#7]

Depending on your particular case I would advise against quadtrees.

Where to use them:

Large area to cover, but very little space occupied with objects mostly static.

Where not to use them:

Small/medium area to cover with lots of objects that constantly move.

A quadtree essentially works by splitting an area into 4 every time there's too much data in that area. Suppose you want to keep a maximum of 16 objects in an area.

1. You start with a big area covering your map and consider all units in there.
2. Less than 16 units? You are done.
3. More than 16 units? Split the are into 4 equal parts and redistribute units. For each of those areas, go back to 2.

Why isn't this a very good idea with lots of moving units? If your units end up walking around the whole map, you will end up with a maximum split on your quad tree.

This is quite bad because at the lowest level you will essentially have a grid, except it's not all in one place in memory, it's all over the place and besides that, it has a whole tree structure above it that's mostly useless.

That's why I would go for a "bucket grid" if you may. Preallocate a grid of cells, each cell having space for n unit pointers (8, 16, etc.) and a counter (to avoid resizing the "bucket"). Updating is extremely easy. Each unit can instantly find it's proper bucket (x / grid_size, y / grid_size).
It's equally easy to find the neighbours of any cell.

To add to a cell you do something simple like:

grid[x].storage[grid[x].crt_count] = unit_pointer
grid[x].crt_count += 1

Removing is easier:

grid[x].crt_count -= 1

All of them are very fast operations that only change values in memory without messing it up :)

The only downside is the memory usage for preallocation. Try to find a balance to have as few cells as possible, but always make sure the bucket is large enough to hold the maximum possible units in that cell.

Again, depending on application, it might work to actually spill the bucket into the nearest neighbour that has enough room.

Whew! Wall of text. Hope that doesn't scare you :)

slenkar

(Posted 2012) [#8]

yeah thats probably the right approach thanks,
basically only test distance between units that are in the same or neighbouring squares

NoOdle

(Posted 2012) [#9]

oh sorry slenkar not sure how I didn't notice your question!! JIM is correct, although there are examples on the internet showing how to use quadtrees for proximity testing, the speed gained by using this is dependant on a good spread. Quite often brute force distance detection is as as fast if not faster in some extreme circumstances. I would recommend a grid based approach as well. Again, sorry for not replying sooner!