A very basic subdivision scheme for finding items in ranges. More...

#include <Spatial.h>

Classes
struct	SubDivisionGrid

Public Member Functions
	SpatialSubdivision ()

	~SpatialSubdivision ()

	SpatialSubdivision (const SpatialSubdivision &rhs)

SpatialSubdivision &	operator= (const SpatialSubdivision &rhs)

entity_pos_t	GetDivisionSize () const

uint32_t	GetWidth () const

uint32_t	GetHeight () const

void	Create (size_t count)

bool	operator== (const SpatialSubdivision &rhs)
	Equivalence test (ignoring order of items within each subdivision) More...

bool	operator!= (const SpatialSubdivision &rhs)

void	Reset (entity_pos_t maxX, entity_pos_t maxZ, entity_pos_t divisionSize)

void	Add (uint32_t item, CFixedVector2D toMin, CFixedVector2D toMax)
	Add an item with the given 'to' size. More...

void	Remove (uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax)
	Remove an item with the given 'from' size. More...

void	Move (uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax, CFixedVector2D toMin, CFixedVector2D toMax)
	Equivalent to Remove() then Add(), but potentially faster. More...

void	Add (uint32_t item, CFixedVector2D to)
	Convenience function for Add() of individual points. More...

void	Remove (uint32_t item, CFixedVector2D from)
	Convenience function for Remove() of individual points. More...

void	Move (uint32_t item, CFixedVector2D from, CFixedVector2D to)
	Convenience function for Move() of individual points. More...

void	GetInRange (SpatialQueryArray &out, CFixedVector2D posMin, CFixedVector2D posMax)
	Returns a sorted list of unique items that includes all items within the given axis-aligned square range. More...

void	GetNear (SpatialQueryArray &out, CFixedVector2D pos, entity_pos_t range)
	Returns a sorted list of unique items that includes all items within the given circular distance of the given point. More...

Private Member Functions
uint32_t	GetI0 (entity_pos_t x)

uint32_t	GetJ0 (entity_pos_t z)

uint32_t	GetI1 (entity_pos_t x)

uint32_t	GetJ1 (entity_pos_t z)

uint32_t	GetIndex0 (CFixedVector2D pos)

uint32_t	GetIndex1 (CFixedVector2D pos)

Private Attributes
entity_pos_t	m_DivisionSize

SubDivisionGrid *	m_Divisions

uint32_t	m_DivisionsW

uint32_t	m_DivisionsH

Friends
struct	SerializeSubDivisionGrid

struct	SerializeSpatialSubdivision

Detailed Description

A very basic subdivision scheme for finding items in ranges.

Items are stored in lists in fixed-size divisions. Items have a size (min/max values of their axis-aligned bounding box) and are stored in all divisions overlapping that area.

It is the caller's responsibility to ensure items are only added once, aren't removed unless they've been added, etc, and that Move/Remove are called with the same coordinates originally passed to Add (since this class doesn't remember which divisions an item occupies).

(TODO: maybe an adaptive quadtree would be better than fixed sizes?)

Definition at line 63 of file Spatial.h.

Constructor & Destructor Documentation

SpatialSubdivision::SpatialSubdivision ( )

inline

Definition at line 112 of file Spatial.h.

SpatialSubdivision::~SpatialSubdivision ( )

inline

Definition at line 115 of file Spatial.h.

SpatialSubdivision::SpatialSubdivision ( const SpatialSubdivision & rhs )

inline

Definition at line 119 of file Spatial.h.

Member Function Documentation

void SpatialSubdivision::Add	(	uint32_t	item,
		CFixedVector2D	toMin,
		CFixedVector2D	toMax
	)

inline

Add an item with the given 'to' size.

The item must not already be present.

Definition at line 200 of file Spatial.h.

void SpatialSubdivision::Add	(	uint32_t	item,
		CFixedVector2D	to
	)

inline

Convenience function for Add() of individual points.

(Note that points on a boundary may occupy multiple divisions.)

Definition at line 265 of file Spatial.h.

void SpatialSubdivision::Create ( size_t count )

inline

Definition at line 150 of file Spatial.h.

entity_pos_t SpatialSubdivision::GetDivisionSize ( ) const

inline

Definition at line 146 of file Spatial.h.

uint32_t SpatialSubdivision::GetHeight ( ) const

inline

Definition at line 148 of file Spatial.h.

uint32_t SpatialSubdivision::GetI0 ( entity_pos_t x )

inlineprivate

Definition at line 327 of file Spatial.h.

uint32_t SpatialSubdivision::GetI1 ( entity_pos_t x )

inlineprivate

Definition at line 337 of file Spatial.h.

uint32_t SpatialSubdivision::GetIndex0 ( CFixedVector2D pos )

inlineprivate

Definition at line 347 of file Spatial.h.

uint32_t SpatialSubdivision::GetIndex1 ( CFixedVector2D pos )

inlineprivate

Definition at line 352 of file Spatial.h.

void SpatialSubdivision::GetInRange	(	SpatialQueryArray &	out,
		CFixedVector2D	posMin,
		CFixedVector2D	posMax
	)

inline

Returns a sorted list of unique items that includes all items within the given axis-aligned square range.

Definition at line 290 of file Spatial.h.

uint32_t SpatialSubdivision::GetJ0 ( entity_pos_t z )

inlineprivate

Definition at line 332 of file Spatial.h.

uint32_t SpatialSubdivision::GetJ1 ( entity_pos_t z )

inlineprivate

Definition at line 342 of file Spatial.h.

void SpatialSubdivision::GetNear	(	SpatialQueryArray &	out,
		CFixedVector2D	pos,
		entity_pos_t	range
	)

inline

Returns a sorted list of unique items that includes all items within the given circular distance of the given point.

Definition at line 314 of file Spatial.h.

uint32_t SpatialSubdivision::GetWidth ( ) const

inline

Definition at line 147 of file Spatial.h.

void SpatialSubdivision::Move	(	uint32_t	item,
		CFixedVector2D	fromMin,
		CFixedVector2D	fromMax,
		CFixedVector2D	toMin,
		CFixedVector2D	toMax
	)

inline

Equivalent to Remove() then Add(), but potentially faster.

Definition at line 251 of file Spatial.h.

void SpatialSubdivision::Move	(	uint32_t	item,
		CFixedVector2D	from,
		CFixedVector2D	to
	)

inline

Convenience function for Move() of individual points.

Definition at line 281 of file Spatial.h.

bool SpatialSubdivision::operator!= ( const SpatialSubdivision & rhs )

inline

Definition at line 181 of file Spatial.h.

SpatialSubdivision& SpatialSubdivision::operator= ( const SpatialSubdivision & rhs )

inline

Definition at line 129 of file Spatial.h.

bool SpatialSubdivision::operator== ( const SpatialSubdivision & rhs )

inline

Equivalence test (ignoring order of items within each subdivision)

Definition at line 159 of file Spatial.h.

void SpatialSubdivision::Remove	(	uint32_t	item,
		CFixedVector2D	fromMin,
		CFixedVector2D	fromMax
	)

inline

Remove an item with the given 'from' size.

The item should already be present. The size must match the size that was last used when adding the item.

Definition at line 222 of file Spatial.h.

void SpatialSubdivision::Remove	(	uint32_t	item,
		CFixedVector2D	from
	)

inline

Convenience function for Remove() of individual points.

Definition at line 273 of file Spatial.h.

void SpatialSubdivision::Reset	(	entity_pos_t	maxX,
		entity_pos_t	maxZ,
		entity_pos_t	divisionSize
	)

inline

Definition at line 186 of file Spatial.h.

Friends And Related Function Documentation

friend struct SerializeSpatialSubdivision

friend

Definition at line 109 of file Spatial.h.

friend struct SerializeSubDivisionGrid

friend

Definition at line 108 of file Spatial.h.

Member Data Documentation

SubDivisionGrid* SpatialSubdivision::m_Divisions

private

Definition at line 104 of file Spatial.h.

uint32_t SpatialSubdivision::m_DivisionsH

private

Definition at line 106 of file Spatial.h.

entity_pos_t SpatialSubdivision::m_DivisionSize

private

Definition at line 103 of file Spatial.h.

uint32_t SpatialSubdivision::m_DivisionsW

private

Definition at line 105 of file Spatial.h.

The documentation for this class was generated from the following file:

/home/sathyam/0ad.svn/source/simulation2/helpers/Spatial.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation