NativeSparseQuadtree< T > Struct Template Reference

A spatial data structure for quick point queries suited for moving or concentrated positions in 2D space. The sparse variant uses less memory, but is slightly slower for insertions and removals than the dense variant. More...

Public Member Functions
void	Clear ()
	Clears and resets the tree without deallocating memory.
void	Dispose ()
void	DisposeIfCreated ()
float3	GetBottomLeftPosition ()
bool	GetCell (float3 position, out uint code)
int2	GetCellCoordinates (float3 position)
JobHandle	GetCellsInRadii (NativeArray< float2 > centers, NativeArray< float > radii, ref NativeParallelHashSet< uint > result, JobHandle dependsOn=default, int innerLoopBatchCount=1)
	Searches for all cells that lie within a list of circles (center + radius) and writes the morton code (cell ids) to a result-list.
JobHandle	GetCellsInRadius (float2 center, float radius, ref NativeList< uint > result, JobHandle dependsOn=default)
	Searches for all cells within a given circle (center + radius) and writes the morton code (cell ids) to a result-list.
JobHandle	GetCellsInRectangle (Rect rect, ref NativeList< uint > result, JobHandle dependsOn=default)
	Searches for all cells within the given rectangle and writes the morton code (cell ids) to a result-list.
JobHandle	GetCellsInRectangles (NativeArray< Rect > rectangles, ref NativeParallelHashSet< uint > result, JobHandle dependsOn=default, int innerLoopBatchCount=1)
	Searches for all cells that lie within the given list of rectangles and writes the morton code (cell ids) to a result-list.
NativeParallelMultiHashMap< uint, T >	GetDataBuckets ()
int	GetMaxDepth ()
NativeList< QuadtreeNode >	GetNodes ()
QuadtreeNode *	GetRoot ()
float2	GetScale ()
void	Insert (float3 position, T value)
	Inserts a value at a given position into the tree.
	NativeSparseQuadtree (float3 position, float2 scale, int maxDepth, int capacity, Allocator allocator)
	NativeSparseQuadtree (Rect bounds, int maxDepth, int capacity, Allocator allocator)
bool	Remove (float3 position, T value)
bool	Update (T value, float3 oldPosition, float3 newPosition)
	Important Note: If you have a lot of things moving in the quadtree, it will be a lot cheaper performance-wise to recreate the whole tree by calling Clear() and then reinserting each element.
Public Member Functions inherited from IQuadtree< T >

Properties
int	Count [get]
bool	IsCreated [get]
Properties inherited from IQuadtree< T >

Detailed Description

A spatial data structure for quick point queries suited for moving or concentrated positions in 2D space. The sparse variant uses less memory, but is slightly slower for insertions and removals than the dense variant.

Template Parameters

T

Type Constraints

T	:	unmanaged
T	:	IEquatable<T>

Constructor & Destructor Documentation

NativeSparseQuadtree() [1/2]

NativeSparseQuadtree	(	Rect	bounds,
		int	maxDepth,
		int	capacity,
		Allocator	allocator )

Parameters

bounds	Bounds of the quadtree
maxDepth	Maximum depth / height of the quadtree - also determines the number of cells
capacity
allocator

NativeSparseQuadtree() [2/2]

NativeSparseQuadtree	(	float3	position,
		float2	scale,
		int	maxDepth,
		int	capacity,
		Allocator	allocator )

Parameters

position	Center of the quadtree
scale	The size of the quadtree in meters
maxDepth	Maximum depth / height of the quadtree - also determines the number of cells
capacity
allocator

Member Function Documentation

Clear()

void Clear

(

)

Clears and resets the tree without deallocating memory.

Implements IQuadtree< T >.

GetBottomLeftPosition()

float3 GetBottomLeftPosition

(

)

Implements IQuadtree< T >.

GetCell()

bool GetCell	(	float3	position,
		out uint	code )

Parameters

position
code

Returns

The morton code (cell id) for the closest cell to the given position. If the position is outside the bounds of this quadtree or the cell does not exist, false is returned

Implements IQuadtree< T >.

GetCellCoordinates()

int2 GetCellCoordinates

(

float3

position

)

Parameters

position

Returns

The coordinates of the cell closest to the given position. They are unchecked (might be negative or bigger than the number of cells in the tree)

Implements IQuadtree< T >.

GetCellsInRadii()

JobHandle GetCellsInRadii	(	NativeArray< float2 >	centers,
		NativeArray< float >	radii,
		ref NativeParallelHashSet< uint >	result,
		JobHandle	dependsOn = default,
		int	innerLoopBatchCount = 1 )

Searches for all cells that lie within a list of circles (center + radius) and writes the morton code (cell ids) to a result-list.

Parameters

centers
radii
result
dependsOn
innerLoopBatchCount

Returns

Implements IQuadtree< T >.

GetCellsInRadius()

JobHandle GetCellsInRadius	(	float2	center,
		float	radius,
		ref NativeList< uint >	result,
		JobHandle	dependsOn = default )

Searches for all cells within a given circle (center + radius) and writes the morton code (cell ids) to a result-list.

Parameters

center
radius
result
dependsOn

Returns

Implements IQuadtree< T >.

GetCellsInRectangle()

JobHandle GetCellsInRectangle	(	Rect	rect,
		ref NativeList< uint >	result,
		JobHandle	dependsOn = default )

Searches for all cells within the given rectangle and writes the morton code (cell ids) to a result-list.

Parameters

rect
result
dependsOn

Returns

Implements IQuadtree< T >.

GetCellsInRectangles()

JobHandle GetCellsInRectangles	(	NativeArray< Rect >	rectangles,
		ref NativeParallelHashSet< uint >	result,
		JobHandle	dependsOn = default,
		int	innerLoopBatchCount = 1 )

Searches for all cells that lie within the given list of rectangles and writes the morton code (cell ids) to a result-list.

Parameters

rectangles
result
dependsOn
innerLoopBatchCount

Returns

Implements IQuadtree< T >.

GetDataBuckets()

NativeParallelMultiHashMap< uint, T > GetDataBuckets

(

)

Implements IQuadtree< T >.

GetMaxDepth()

int GetMaxDepth

(

)

Implements IQuadtree< T >.

GetNodes()

NativeList< QuadtreeNode > GetNodes

(

)

Implements IQuadtree< T >.

GetRoot()

QuadtreeNode * GetRoot

(

)

Implements IQuadtree< T >.

GetScale()

float2 GetScale

(

)

Implements IQuadtree< T >.

Insert()

void Insert	(	float3	position,
		T	value )

Inserts a value at a given position into the tree.

Parameters

position
value

Implements IQuadtree< T >.

Remove()

bool Remove	(	float3	position,
		T	value )

Parameters

position
value

Returns

True, if the value was found in the bucket that represents the given position. False otherwise. Note, that if the function returns false, that that does not necessarily mean the value is not present somewhere in the quadtree, just that it is not in the bucket at the given position

Implements IQuadtree< T >.

Update()

bool Update	(	T	value,
		float3	oldPosition,
		float3	newPosition )

Important Note: If you have a lot of things moving in the quadtree, it will be a lot cheaper performance-wise to recreate the whole tree by calling Clear() and then reinserting each element.

Parameters

value
oldPosition
newPosition

Returns

Returns false if the value was not found at the old position or the new position is outside the quadtree

Implements IQuadtree< T >.

Property Documentation

Count

int Count

get

Implements IQuadtree< T >.

IsCreated

bool IsCreated

get

Implements IQuadtree< T >.