org.mini2Dx.core.collision

Class PointQuadTree<T extends CollisionObject>

java.lang.Object

org.mini2Dx.core.collision.PointQuadTree<T>

All Implemented Interfaces:

CollisionDetection<T>, QuadTree<T>, PositionChangeListener<T>

Direct Known Subclasses:

RegionQuadTree

public class PointQuadTree<T extends CollisionObject>
extends java.lang.Object
implements QuadTree<T>

Implements a point quadtree

See Also:

Wikipedia: Point Quad Tree

Field Summary

Fields

Modifier and Type	Field and Description
static Color	BOUNDS_COLOR
static float	DEFAULT_MINIMUM_QUAD_SIZE
static Color	ELEMENT_COLOR
protected int	elementLimitPerQuad
protected org.mini2Dx.gdx.utils.IntIntMap	elementsToQuads
static int	INITIAL_QUAD_ELEMENTS_POOL_SIZE
protected org.mini2Dx.gdx.utils.Array<Quad>	leaves
protected float	minimumQuadHeight
protected float	minimumQuadWidth
protected org.mini2Dx.gdx.utils.Array<Quad>	processQueue
static Color	QUAD_COLOR
protected FreeArray<QuadElements<T>>	quadElements
protected org.mini2Dx.gdx.utils.Queue<QuadElements<T>>	quadElementsPool
protected FreeArray<Quad>	quads
protected Quad	rootQuad

Constructor Summary

Constructors

Constructor and Description
PointQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad, float x, float y, float width, float height) Constructs a PointQuadTree with a specified minimum quad size, element limit and watermark
PointQuadTree(int elementLimitPerQuad, float x, float y, float width, float height) Constructs a PointQuadTree with a specified element limit and no merging watermark.

Method Summary

Modifier and Type	Method and Description
boolean	add(T element) Adds an element to this QuadTree
void	addAll(org.mini2Dx.gdx.utils.Array<T> elementsToAdd) Adds all element to this QuadTree.
protected void	addElementsContainedInArea(Quad quad, org.mini2Dx.gdx.utils.Array<T> result, Rectangle area, boolean allElements)
protected void	addElementsContainingPoint(Quad quad, org.mini2Dx.gdx.utils.Array<T> result, Point point)
protected void	addElementsIntersectingLineSegment(Quad quad, org.mini2Dx.gdx.utils.Array<T> result, LineSegment lineSegment)
protected void	addElementsOverlappingArea(Quad quad, org.mini2Dx.gdx.utils.Array<T> result, Rectangle area, boolean allElements)
protected void	addElementsOverlappingAreaIgnoringEdges(Quad quad, org.mini2Dx.gdx.utils.Array<T> result, Rectangle area, boolean allElements)
protected boolean	addToQuad(Quad quad, T element)
protected QuadElements<T>	allocateQuadElements()
protected boolean	belongsToQuad(Quad quad, T element)
boolean	cleanup()
void	clear() Same a CollisionDetection.removeAll(Array) except the results are not stored
boolean	contains(T element) Checks if an element is added to the quad tree
void	debugRender(Graphics g)
protected void	debugRender(Graphics g, Quad quad)
protected Quad	findQuad(Quad startQuad, T element, boolean updateBounds)
protected Quad	findQuad(Quad startQuad, T element, float x, float y, boolean updateBounds)
protected Quad	findQuad(T element, float x, float y, boolean updateBounds)
int	getElementLimitPerQuad()
org.mini2Dx.gdx.utils.Array<T>	getElements()
void	getElements(org.mini2Dx.gdx.utils.Array<T> result)
void	getElements(QuadTreeInspector<T> inspector)
void	getElementsContainedInArea(org.mini2Dx.gdx.utils.Array<T> result, Rectangle area)
org.mini2Dx.gdx.utils.Array<T>	getElementsContainedInArea(Rectangle area)
void	getElementsContainingArea(org.mini2Dx.gdx.utils.Array<T> result, Rectangle area)
org.mini2Dx.gdx.utils.Array<T>	getElementsContainingArea(Rectangle area)
void	getElementsContainingPoint(org.mini2Dx.gdx.utils.Array<T> result, Point point)
org.mini2Dx.gdx.utils.Array<T>	getElementsContainingPoint(Point point)
void	getElementsIntersectingLineSegment(org.mini2Dx.gdx.utils.Array<T> result, LineSegment lineSegment)
org.mini2Dx.gdx.utils.Array<T>	getElementsIntersectingLineSegment(LineSegment lineSegment)
void	getElementsOverlappingArea(org.mini2Dx.gdx.utils.Array<T> result, Circle area)
void	getElementsOverlappingArea(org.mini2Dx.gdx.utils.Array<T> result, Rectangle area)
org.mini2Dx.gdx.utils.Array<T>	getElementsOverlappingArea(Circle area)
org.mini2Dx.gdx.utils.Array<T>	getElementsOverlappingArea(Rectangle area)
void	getElementsOverlappingAreaIgnoringEdges(org.mini2Dx.gdx.utils.Array<T> result, Rectangle area)
org.mini2Dx.gdx.utils.Array<T>	getElementsOverlappingAreaIgnoringEdges(Rectangle area)
float	getMinimumQuadHeight()
float	getMinimumQuadWidth()
Quad	getQuad(T element) Returns the Quad that the specified element belongs to
int	getTotalElements()
int	getTotalQuads()
protected void	initBounds(Quad quad, T element)
void	positionChanged(T moved)
protected void	releaseQuadElements(QuadElements<T> elements)
boolean	remove(T element) Removes an element from this QuadTree
void	removeAll(org.mini2Dx.gdx.utils.Array<T> elementsToRemove) Removes all elements in this QuadTree and stores them in an Array
protected boolean	removeFromQuad(Quad quad, T element)
protected boolean	updateBounds(Quad quad, T element)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INITIAL_QUAD_ELEMENTS_POOL_SIZE

public static int INITIAL_QUAD_ELEMENTS_POOL_SIZE

DEFAULT_MINIMUM_QUAD_SIZE

public static float DEFAULT_MINIMUM_QUAD_SIZE

QUAD_COLOR

public static Color QUAD_COLOR

BOUNDS_COLOR

public static Color BOUNDS_COLOR

ELEMENT_COLOR

public static Color ELEMENT_COLOR

quadElementsPool

protected final org.mini2Dx.gdx.utils.Queue<QuadElements<T extends CollisionObject>> quadElementsPool

elementsToQuads

protected final org.mini2Dx.gdx.utils.IntIntMap elementsToQuads

quads

protected final FreeArray<Quad> quads

quadElements

protected final FreeArray<QuadElements<T extends CollisionObject>> quadElements

rootQuad

protected final Quad rootQuad

elementLimitPerQuad

protected final int elementLimitPerQuad

minimumQuadWidth

protected final float minimumQuadWidth

minimumQuadHeight

protected final float minimumQuadHeight

processQueue

protected final org.mini2Dx.gdx.utils.Array<Quad> processQueue

leaves

protected final org.mini2Dx.gdx.utils.Array<Quad> leaves

Constructor Detail

PointQuadTree

public PointQuadTree(int elementLimitPerQuad,
                     float x,
                     float y,
                     float width,
                     float height)

Constructs a PointQuadTree with a specified element limit and no merging watermark. As elements are removed, small sized child PointQuadTrees will not be merged back together.

Parameters:

elementLimitPerQuad - The maximum number of elements in a quad before it is split into 4 child PointQuadTrees

x - The x coordinate of the PointQuadTree

y - The y coordiante of the PointQuadTree

width - The width of the PointQuadTree

height - The height of the PointQuadTree

PointQuadTree

public PointQuadTree(float minimumQuadWidth,
                     float minimumQuadHeight,
                     int elementLimitPerQuad,
                     float x,
                     float y,
                     float width,
                     float height)

Constructs a PointQuadTree with a specified minimum quad size, element limit and watermark

Parameters:

minimumQuadWidth - The minimum width of quads. Quads will not subdivide smaller than this width.

minimumQuadHeight - The minimum height of quads. Quads will not subdivide smaller than this height.

elementLimitPerQuad - The maximum number of elements in a quad before it is split into 4 child PointQuadTrees

x - The x coordinate of the PointQuadTree

y - The y coordiante of the PointQuadTree

width - The width of the PointQuadTree

height - The height of the PointQuadTree

Method Detail

allocateQuadElements

protected QuadElements<T> allocateQuadElements()

releaseQuadElements

protected void releaseQuadElements(QuadElements<T> elements)

cleanup

public boolean cleanup()

debugRender

public void debugRender(Graphics g)

Specified by:

debugRender in interface CollisionDetection<T extends CollisionObject>

debugRender

protected void debugRender(Graphics g,
                           Quad quad)

findQuad

protected Quad findQuad(T element,
                        float x,
                        float y,
                        boolean updateBounds)

findQuad

protected Quad findQuad(Quad startQuad,
                        T element,
                        boolean updateBounds)

findQuad

protected Quad findQuad(Quad startQuad,
                        T element,
                        float x,
                        float y,
                        boolean updateBounds)

belongsToQuad

protected boolean belongsToQuad(Quad quad,
                                T element)

addToQuad

protected boolean addToQuad(Quad quad,
                            T element)

removeFromQuad

protected boolean removeFromQuad(Quad quad,
                                 T element)

addAll

public void addAll(org.mini2Dx.gdx.utils.Array<T> elementsToAdd)

Description copied from interface: CollisionDetection

Adds all element to this QuadTree. Note that if an element exists outside of this QuadTree's bounds, it will not be added

Specified by:

addAll in interface CollisionDetection<T extends CollisionObject>

Parameters:

elementsToAdd - The elements to add

add

public boolean add(T element)

Description copied from interface: CollisionDetection

Adds an element to this QuadTree

Specified by:

add in interface CollisionDetection<T extends CollisionObject>

Parameters:

element - The element to add

Returns:

False if the element exists outside of this QuadTree's bounds and was not added

removeAll

public void removeAll(org.mini2Dx.gdx.utils.Array<T> elementsToRemove)

Description copied from interface: CollisionDetection

Removes all elements in this QuadTree and stores them in an Array

Specified by:

removeAll in interface CollisionDetection<T extends CollisionObject>

Parameters:

elementsToRemove - After executing, this Array will contain all the removed elements

remove

public boolean remove(T element)

Description copied from interface: CollisionDetection

Removes an element from this QuadTree

Specified by:

remove in interface CollisionDetection<T extends CollisionObject>

Parameters:

element - The element to remove

Returns:

True if the element was found and removed

initBounds

protected void initBounds(Quad quad,
                          T element)

updateBounds

protected boolean updateBounds(Quad quad,
                               T element)

clear

public void clear()

Description copied from interface: CollisionDetection

Same a CollisionDetection.removeAll(Array) except the results are not stored

Specified by:

clear in interface CollisionDetection<T extends CollisionObject>

addElementsOverlappingArea

protected void addElementsOverlappingArea(Quad quad,
                                          org.mini2Dx.gdx.utils.Array<T> result,
                                          Rectangle area,
                                          boolean allElements)

addElementsOverlappingAreaIgnoringEdges

protected void addElementsOverlappingAreaIgnoringEdges(Quad quad,
                                                       org.mini2Dx.gdx.utils.Array<T> result,
                                                       Rectangle area,
                                                       boolean allElements)

addElementsContainedInArea

protected void addElementsContainedInArea(Quad quad,
                                          org.mini2Dx.gdx.utils.Array<T> result,
                                          Rectangle area,
                                          boolean allElements)

addElementsIntersectingLineSegment

protected void addElementsIntersectingLineSegment(Quad quad,
                                                  org.mini2Dx.gdx.utils.Array<T> result,
                                                  LineSegment lineSegment)

addElementsContainingPoint

protected void addElementsContainingPoint(Quad quad,
                                          org.mini2Dx.gdx.utils.Array<T> result,
                                          Point point)

getElementsOverlappingArea

public org.mini2Dx.gdx.utils.Array<T> getElementsOverlappingArea(Rectangle area)

Specified by:

getElementsOverlappingArea in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsOverlappingArea in interface QuadTree<T extends CollisionObject>

getElementsOverlappingArea

public void getElementsOverlappingArea(org.mini2Dx.gdx.utils.Array<T> result,
                                       Rectangle area)

Specified by:

getElementsOverlappingArea in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsOverlappingArea in interface QuadTree<T extends CollisionObject>

getElementsOverlappingArea

public org.mini2Dx.gdx.utils.Array<T> getElementsOverlappingArea(Circle area)

Specified by:

getElementsOverlappingArea in interface CollisionDetection<T extends CollisionObject>

getElementsOverlappingArea

public void getElementsOverlappingArea(org.mini2Dx.gdx.utils.Array<T> result,
                                       Circle area)

Specified by:

getElementsOverlappingArea in interface CollisionDetection<T extends CollisionObject>

getElementsOverlappingAreaIgnoringEdges

public org.mini2Dx.gdx.utils.Array<T> getElementsOverlappingAreaIgnoringEdges(Rectangle area)

Specified by:

getElementsOverlappingAreaIgnoringEdges in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsOverlappingAreaIgnoringEdges in interface QuadTree<T extends CollisionObject>

getElementsOverlappingAreaIgnoringEdges

public void getElementsOverlappingAreaIgnoringEdges(org.mini2Dx.gdx.utils.Array<T> result,
                                                    Rectangle area)

Specified by:

getElementsOverlappingAreaIgnoringEdges in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsOverlappingAreaIgnoringEdges in interface QuadTree<T extends CollisionObject>

getElementsContainedInArea

public org.mini2Dx.gdx.utils.Array<T> getElementsContainedInArea(Rectangle area)

Specified by:

getElementsContainedInArea in interface CollisionDetection<T extends CollisionObject>

getElementsContainedInArea

public void getElementsContainedInArea(org.mini2Dx.gdx.utils.Array<T> result,
                                       Rectangle area)

Specified by:

getElementsContainedInArea in interface CollisionDetection<T extends CollisionObject>

getElements

public void getElements(QuadTreeInspector<T> inspector)

Specified by:

getElements in interface QuadTree<T extends CollisionObject>

getElementsContainingArea

public org.mini2Dx.gdx.utils.Array<T> getElementsContainingArea(Rectangle area)

Specified by:

getElementsContainingArea in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsContainingArea in interface QuadTree<T extends CollisionObject>

getElementsContainingArea

public void getElementsContainingArea(org.mini2Dx.gdx.utils.Array<T> result,
                                      Rectangle area)

Specified by:

getElementsContainingArea in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsContainingArea in interface QuadTree<T extends CollisionObject>

getElementsIntersectingLineSegment

public org.mini2Dx.gdx.utils.Array<T> getElementsIntersectingLineSegment(LineSegment lineSegment)

Specified by:

getElementsIntersectingLineSegment in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends CollisionObject>

getElementsIntersectingLineSegment

public void getElementsIntersectingLineSegment(org.mini2Dx.gdx.utils.Array<T> result,
                                               LineSegment lineSegment)

Specified by:

getElementsIntersectingLineSegment in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends CollisionObject>

getElementsContainingPoint

public org.mini2Dx.gdx.utils.Array<T> getElementsContainingPoint(Point point)

Specified by:

getElementsContainingPoint in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsContainingPoint in interface QuadTree<T extends CollisionObject>

getElementsContainingPoint

public void getElementsContainingPoint(org.mini2Dx.gdx.utils.Array<T> result,
                                       Point point)

Specified by:

getElementsContainingPoint in interface CollisionDetection<T extends CollisionObject>

Specified by:

getElementsContainingPoint in interface QuadTree<T extends CollisionObject>

getElements

public org.mini2Dx.gdx.utils.Array<T> getElements()

Specified by:

getElements in interface CollisionDetection<T extends CollisionObject>

getElements

public void getElements(org.mini2Dx.gdx.utils.Array<T> result)

Specified by:

getElements in interface CollisionDetection<T extends CollisionObject>

positionChanged

public void positionChanged(T moved)

Specified by:

positionChanged in interface PositionChangeListener<T extends CollisionObject>

getQuad

public Quad getQuad(T element)

Returns the Quad that the specified element belongs to

Parameters:

element - The element to search for

Returns:

Null if not contained in this quad tree

contains

public boolean contains(T element)

Checks if an element is added to the quad tree

Parameters:

element - The element to check

Returns:

True if added to the quad tree

getElementLimitPerQuad

public int getElementLimitPerQuad()

Specified by:

getElementLimitPerQuad in interface QuadTree<T extends CollisionObject>

getMinimumQuadWidth

public float getMinimumQuadWidth()

Specified by:

getMinimumQuadWidth in interface QuadTree<T extends CollisionObject>

getMinimumQuadHeight

public float getMinimumQuadHeight()

Specified by:

getMinimumQuadHeight in interface QuadTree<T extends CollisionObject>

getTotalQuads

public int getTotalQuads()

Specified by:

getTotalQuads in interface QuadTree<T extends CollisionObject>

getTotalElements

public int getTotalElements()

Specified by:

getTotalElements in interface CollisionDetection<T extends CollisionObject>

Specified by:

getTotalElements in interface QuadTree<T extends CollisionObject>