org.mini2Dx.core.collision

Class ConcurrentRegionQuadTree<T extends Sizeable>

java.lang.Object

org.mini2Dx.core.geom.Shape

org.mini2Dx.core.geom.Rectangle

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

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

All Implemented Interfaces:

QuadTree<T>, Positionable, PositionChangeListener<T>, Sizeable

public class ConcurrentRegionQuadTree<T extends Sizeable>
extends ConcurrentPointQuadTree<T>

Implements a thread-safe region quadtree

See Also:

Wikipedia: Region Quad Tree

Field Summary

Fields inherited from class org.mini2Dx.core.collision.ConcurrentPointQuadTree

bottomLeft, bottomRight, ELEMENT_COLOR, elementLimitPerQuad, elements, lock, mergeWatermark, minimumQuadHeight, minimumQuadWidth, parent, QUAD_COLOR, topLeft, topRight, totalElementsCache, totalMerges

Fields inherited from class org.mini2Dx.core.geom.Shape

geometry, positionChangeListeners, sizeChangeListeners

Constructor Summary

Constructors

Constructor and Description
ConcurrentRegionQuadTree(ConcurrentRegionQuadTree<T> parent, float x, float y, float width, float height) Constructs a ConcurrentRegionQuadTree as a child of another ConcurrentRegionQuadTree
ConcurrentRegionQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad, int mergeWatermark, float x, float y, float width, float height) Constructs a ConcurrentRegionQuadTree with a specified minimum quad size, element limit and watermark
ConcurrentRegionQuadTree(int elementLimit, float x, float y, float width, float height) Constructs a ConcurrentRegionQuadTree with a specified element limit and no merging watermark.
ConcurrentRegionQuadTree(int elementLimit, int mergeWatermark, float x, float y, float width, float height) Constructs a ConcurrentRegionQuadTree with a specified element limit and 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> elements) Adds all element to this QuadTree.
protected boolean	addElement(T element)
protected void	addElementsContainingPoint(org.mini2Dx.gdx.utils.Array<T> result, Point point)
protected void	addElementsIntersectingLineSegment(org.mini2Dx.gdx.utils.Array<T> result, LineSegment lineSegment)
protected void	addElementsWithinArea(org.mini2Dx.gdx.utils.Array<T> result, Shape area)
protected boolean	addElementToChild(T element)
void	debugRender(Graphics g)
org.mini2Dx.gdx.utils.Array<T>	getElements()
void	getElements(org.mini2Dx.gdx.utils.Array<T> result)
void	getElementsContainingPoint(org.mini2Dx.gdx.utils.Array<T> result, Point point)
void	getElementsContainingPoint(org.mini2Dx.gdx.utils.Array<T> result, Point point, QuadTreeSearchDirection searchDirection)
void	getElementsIntersectingLineSegment(org.mini2Dx.gdx.utils.Array<T> result, LineSegment lineSegment)
void	getElementsIntersectingLineSegment(org.mini2Dx.gdx.utils.Array<T> result, LineSegment lineSegment, QuadTreeSearchDirection searchDirection)
void	getElementsWithinArea(org.mini2Dx.gdx.utils.Array<T> result, Shape area)
void	getElementsWithinArea(org.mini2Dx.gdx.utils.Array<T> result, Shape area, QuadTreeSearchDirection searchDirection)
int	getTotalElements()
void	positionChanged(T moved)
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	removeElement(T element, boolean topDownInvocation)
protected void	subdivide()

Methods inherited from class org.mini2Dx.core.collision.ConcurrentPointQuadTree

clear, clearTotalElementsCache, getElementLimitPerQuad, getElementsContainingPoint, getElementsContainingPoint, getElementsIntersectingLineSegment, getElementsIntersectingLineSegment, getElementsWithinArea, getElementsWithinArea, getMergeWatermark, getMinimumQuadHeight, getMinimumQuadWidth, getParent, getTotalMergeOperations, getTotalQuads, intersects, isMergable, merge, removeElementFromChild

Methods inherited from class org.mini2Dx.core.geom.Rectangle

contains, contains, contains, contains, contains, copy, dispose, draw, edgeIterator, equals, fill, getCenterX, getCenterY, getDistanceTo, getHeight, getMaxX, getMaxY, getMinX, getMinY, getNumberOfSides, getPolygon, getRotation, getVertices, getWidth, getX, getY, hashCode, intersection, intersects, intersects, intersects, intersects, intersects, intersects, intersectsLineSegment, intersectsLineSegment, isCircle, lerp, rotate, rotateAround, scale, set, set, setCenter, setCenterX, setCenterY, setHeight, setRadius, setRotation, setRotationAround, setSize, setSize, setWidth, setX, setXY, setXY, setY, toString, translate

Methods inherited from class org.mini2Dx.core.geom.Shape

add, addPostionChangeListener, addSizeChangeListener, clearPositionChangeListeners, clearPositionListeners, clearPositionListeners, clearSizeChangeListeners, clearSizeListeners, clearSizeListeners, getDistanceTo, intersects, moveTowards, moveTowards, notifyPositionChangeListeners, notifyPositionListeners, notifyPositionListeners, notifySizeChangeListeners, notifySizeListeners, notifySizeListeners, removePositionChangeListener, removePositionListener, removePositionListener, removeSizeChangeListener, removeSizeListener, removeSizeListener, setRotationAround, subtract

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ConcurrentRegionQuadTree

public ConcurrentRegionQuadTree(int elementLimit,
                                int mergeWatermark,
                                float x,
                                float y,
                                float width,
                                float height)

Constructs a ConcurrentRegionQuadTree with a specified element limit and watermark

Parameters:

elementLimit - The maximum number of elements in a ConcurrentRegionQuadTree before it is split into 4 child quads

mergeWatermark - When a parent ConcurrentRegionQuadTree's total elements go lower than this mark, the child ConcurrentRegionQuadTrees will be merged back together

x - The x coordinate of the ConcurrentRegionQuadTree

y - The y coordiante of the ConcurrentRegionQuadTree

width - The width of the ConcurrentRegionQuadTree

height - The height of the ConcurrentRegionQuadTree

ConcurrentRegionQuadTree

public ConcurrentRegionQuadTree(int elementLimit,
                                float x,
                                float y,
                                float width,
                                float height)

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

Parameters:

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

x - The x coordinate of the ConcurrentRegionQuadTree

y - The y coordiante of the ConcurrentRegionQuadTree

width - The width of the ConcurrentRegionQuadTree

height - The height of the ConcurrentRegionQuadTree

ConcurrentRegionQuadTree

public ConcurrentRegionQuadTree(ConcurrentRegionQuadTree<T> parent,
                                float x,
                                float y,
                                float width,
                                float height)

Constructs a ConcurrentRegionQuadTree as a child of another ConcurrentRegionQuadTree

Parameters:

parent - The parent ConcurrentRegionQuadTree

x - The x coordinate of the ConcurrentRegionQuadTree

y - The y coordiante of the ConcurrentRegionQuadTree

width - The width of the ConcurrentRegionQuadTree

height - The height of the ConcurrentRegionQuadTree

ConcurrentRegionQuadTree

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

Constructs a ConcurrentRegionQuadTree 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 ConcurrentRegionQuadTrees

mergeWatermark - When a parent ConcurrentRegionQuadTree's total elements go lower than this mark, the child ConcurrentRegionQuadTrees will be merged back together

x - The x coordinate of the ConcurrentRegionQuadTree

y - The y coordiante of the ConcurrentRegionQuadTree

width - The width of the ConcurrentRegionQuadTree

height - The height of the ConcurrentRegionQuadTree

Method Detail

debugRender

public void debugRender(Graphics g)

Specified by:

debugRender in interface QuadTree<T extends Sizeable>

Overrides:

debugRender in class ConcurrentPointQuadTree<T extends Sizeable>

addAll

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

Description copied from interface: QuadTree

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 QuadTree<T extends Sizeable>

Overrides:

addAll in class ConcurrentPointQuadTree<T extends Sizeable>

Parameters:

elements - The elements to add

add

public boolean add(T element)

Description copied from interface: QuadTree

Adds an element to this QuadTree

Specified by:

add in interface QuadTree<T extends Sizeable>

Overrides:

add in class ConcurrentPointQuadTree<T extends Sizeable>

Parameters:

element - The element to add

Returns:

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

addElement

protected boolean addElement(T element)

Overrides:

addElement in class ConcurrentPointQuadTree<T extends Sizeable>

addElementToChild

protected boolean addElementToChild(T element)

Overrides:

addElementToChild in class ConcurrentPointQuadTree<T extends Sizeable>

subdivide

protected void subdivide()

Overrides:

subdivide in class ConcurrentPointQuadTree<T extends Sizeable>

removeAll

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

Description copied from interface: QuadTree

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

Specified by:

removeAll in interface QuadTree<T extends Sizeable>

Overrides:

removeAll in class ConcurrentPointQuadTree<T extends Sizeable>

Parameters:

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

remove

public boolean remove(T element)

Description copied from interface: QuadTree

Removes an element from this QuadTree

Specified by:

remove in interface QuadTree<T extends Sizeable>

Overrides:

remove in class ConcurrentPointQuadTree<T extends Sizeable>

Parameters:

element - The element to remove

Returns:

True if the element was found and removed

removeElement

protected boolean removeElement(T element,
                                boolean topDownInvocation)

Overrides:

removeElement in class ConcurrentPointQuadTree<T extends Sizeable>

addElementsWithinArea

protected void addElementsWithinArea(org.mini2Dx.gdx.utils.Array<T> result,
                                     Shape area)

Overrides:

addElementsWithinArea in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsWithinArea

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

Specified by:

getElementsWithinArea in interface QuadTree<T extends Sizeable>

Overrides:

getElementsWithinArea in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsWithinArea

public void getElementsWithinArea(org.mini2Dx.gdx.utils.Array<T> result,
                                  Shape area,
                                  QuadTreeSearchDirection searchDirection)

Specified by:

getElementsWithinArea in interface QuadTree<T extends Sizeable>

Overrides:

getElementsWithinArea in class ConcurrentPointQuadTree<T extends Sizeable>

addElementsContainingPoint

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

Overrides:

addElementsContainingPoint in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsContainingPoint

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

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Sizeable>

Overrides:

getElementsContainingPoint in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsContainingPoint

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

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Sizeable>

Overrides:

getElementsContainingPoint in class ConcurrentPointQuadTree<T extends Sizeable>

addElementsIntersectingLineSegment

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

Overrides:

addElementsIntersectingLineSegment in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsIntersectingLineSegment

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

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Sizeable>

Overrides:

getElementsIntersectingLineSegment in class ConcurrentPointQuadTree<T extends Sizeable>

getElementsIntersectingLineSegment

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

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Sizeable>

Overrides:

getElementsIntersectingLineSegment in class ConcurrentPointQuadTree<T extends Sizeable>

getElements

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

Specified by:

getElements in interface QuadTree<T extends Sizeable>

Overrides:

getElements in class ConcurrentPointQuadTree<T extends Sizeable>

getElements

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

Specified by:

getElements in interface QuadTree<T extends Sizeable>

Overrides:

getElements in class ConcurrentPointQuadTree<T extends Sizeable>

getTotalElements

public int getTotalElements()

Specified by:

getTotalElements in interface QuadTree<T extends Sizeable>

Overrides:

getTotalElements in class ConcurrentPointQuadTree<T extends Sizeable>

positionChanged

public void positionChanged(T moved)

Specified by:

positionChanged in interface PositionChangeListener<T extends Sizeable>

Overrides:

positionChanged in class ConcurrentPointQuadTree<T extends Sizeable>