org.mini2Dx.core.collisions

Class ConcurrentPointQuadTree<T extends Positionable>

java.lang.Object

org.mini2Dx.core.geom.Shape

org.mini2Dx.core.geom.Rectangle

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

All Implemented Interfaces:

QuadTree<T>, PositionChangeListener<T>, Parallelogram

Direct Known Subclasses:

ConcurrentRegionQuadTree

public class ConcurrentPointQuadTree<T extends Positionable>
extends Rectangle
implements QuadTree<T>

Implements a thread-safe point quadtree

See Also:

Wikipedia: Point Quad Tree

Field Summary

Fields

Modifier and Type	Field and Description
protected ConcurrentPointQuadTree<T>	bottomLeft
protected ConcurrentPointQuadTree<T>	bottomRight
static com.badlogic.gdx.graphics.Color	ELEMENT_COLOR
protected int	elementLimitPerQuad
protected com.badlogic.gdx.utils.Array<T>	elements
protected java.util.concurrent.locks.ReadWriteLock	lock
protected int	mergeWatermark
protected float	minimumQuadHeight
protected float	minimumQuadWidth
protected ConcurrentPointQuadTree<T>	parent
static com.badlogic.gdx.graphics.Color	QUAD_COLOR
protected ConcurrentPointQuadTree<T>	topLeft
protected ConcurrentPointQuadTree<T>	topRight
protected int	totalElementsCache
protected int	totalMerges

Constructor Summary

Constructors

Constructor and Description
ConcurrentPointQuadTree(ConcurrentPointQuadTree<T> parent, float x, float y, float width, float height) Constructs a ConcurrentPointQuadTree as a child of another ConcurrentPointQuadTree
ConcurrentPointQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad, int mergeWatermark, float x, float y, float width, float height) Constructs a ConcurrentPointQuadTree with a specified minimum quad size, element limit and watermark
ConcurrentPointQuadTree(int elementLimitPerQuad, float x, float y, float width, float height) Constructs a ConcurrentPointQuadTree with a specified element limit and no merging watermark.
ConcurrentPointQuadTree(int elementLimitPerQuad, int mergeWatermark, float x, float y, float width, float height) Constructs a ConcurrentPointQuadTree 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(com.badlogic.gdx.utils.Array<T> elementsToAdd) Adds all element to this QuadTree.
protected boolean	addElement(T element)
protected boolean	addElementToChild(T element)
void	clear() Same a QuadTree.removeAll(Array) except the results are not stored
protected void	clearTotalElementsCache()
void	debugRender(Graphics g)
int	getElementLimitPerQuad()
com.badlogic.gdx.utils.Array<T>	getElements()
void	getElements(com.badlogic.gdx.utils.Array<T> result)
void	getElementsContainingPoint(com.badlogic.gdx.utils.Array<T> result, Point point)
com.badlogic.gdx.utils.Array<T>	getElementsContainingPoint(Point point)
void	getElementsIntersectingLineSegment(com.badlogic.gdx.utils.Array<T> result, LineSegment lineSegment)
com.badlogic.gdx.utils.Array<T>	getElementsIntersectingLineSegment(LineSegment lineSegment)
void	getElementsWithinArea(com.badlogic.gdx.utils.Array<T> result, Shape area)
com.badlogic.gdx.utils.Array<T>	getElementsWithinArea(Shape area)
int	getMergeWatermark()
float	getMinimumQuadHeight()
float	getMinimumQuadWidth()
QuadTree<T>	getParent()
int	getTotalElements()
int	getTotalMergeOperations()
int	getTotalQuads()
protected boolean	isMergable()
protected void	merge()
void	positionChanged(T moved)
boolean	remove(T element) Removes an element from this QuadTree
void	removeAll(com.badlogic.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 boolean	removeElementFromChild(T element)
protected void	subdivide()

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

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

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

add, intersects, subtract

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.mini2Dx.core.geom.Parallelogram

contains, contains, getHeight, getMaxX, getMaxY, getRotation, getWidth, getX, getY, intersects, intersects, intersectsLineSegment, rotate, rotateAround, setRotation, setRotationAround

Field Detail

QUAD_COLOR

public static com.badlogic.gdx.graphics.Color QUAD_COLOR

ELEMENT_COLOR

public static com.badlogic.gdx.graphics.Color ELEMENT_COLOR

parent

protected ConcurrentPointQuadTree<T extends Positionable> parent

topLeft

protected ConcurrentPointQuadTree<T extends Positionable> topLeft

topRight

protected ConcurrentPointQuadTree<T extends Positionable> topRight

bottomLeft

protected ConcurrentPointQuadTree<T extends Positionable> bottomLeft

bottomRight

protected ConcurrentPointQuadTree<T extends Positionable> bottomRight

elements

protected com.badlogic.gdx.utils.Array<T extends Positionable> elements

elementLimitPerQuad

protected final int elementLimitPerQuad

mergeWatermark

protected final int mergeWatermark

minimumQuadWidth

protected final float minimumQuadWidth

minimumQuadHeight

protected final float minimumQuadHeight

lock

protected final java.util.concurrent.locks.ReadWriteLock lock

totalElementsCache

protected int totalElementsCache

totalMerges

protected int totalMerges

Constructor Detail

ConcurrentPointQuadTree

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

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

Parameters:

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

x - The x coordinate of the ConcurrentPointQuadTree

y - The y coordiante of the ConcurrentPointQuadTree

width - The width of the ConcurrentPointQuadTree

height - The height of the ConcurrentPointQuadTree

ConcurrentPointQuadTree

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

Constructs a ConcurrentPointQuadTree as a child of another ConcurrentPointQuadTree

Parameters:

parent - The parent ConcurrentPointQuadTree

x - The x coordinate of the ConcurrentPointQuadTree

y - The y coordiante of the ConcurrentPointQuadTree

width - The width of the ConcurrentPointQuadTree

height - The height of the ConcurrentPointQuadTree

ConcurrentPointQuadTree

public ConcurrentPointQuadTree(int elementLimitPerQuad,
                               int mergeWatermark,
                               float x,
                               float y,
                               float width,
                               float height)

Constructs a ConcurrentPointQuadTree with a specified element limit and watermark

Parameters:

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

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

x - The x coordinate of the ConcurrentPointQuadTree

y - The y coordiante of the ConcurrentPointQuadTree

width - The width of the ConcurrentPointQuadTree

height - The height of the ConcurrentPointQuadTree

ConcurrentPointQuadTree

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

Constructs a ConcurrentPointQuadTree 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 ConcurrentPointQuadTrees

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

x - The x coordinate of the ConcurrentPointQuadTree

y - The y coordiante of the ConcurrentPointQuadTree

width - The width of the ConcurrentPointQuadTree

height - The height of the ConcurrentPointQuadTree

Method Detail

debugRender

public void debugRender(Graphics g)

Specified by:

debugRender in interface QuadTree<T extends Positionable>

addAll

public void addAll(com.badlogic.gdx.utils.Array<T> elementsToAdd)

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 Positionable>

Parameters:

elementsToAdd - 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 Positionable>

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)

addElementToChild

protected boolean addElementToChild(T element)

subdivide

protected void subdivide()

isMergable

protected boolean isMergable()

merge

protected void merge()

removeAll

public void removeAll(com.badlogic.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 Positionable>

Parameters:

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

clear

public void clear()

Description copied from interface: QuadTree

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

Specified by:

clear in interface QuadTree<T extends Positionable>

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 Positionable>

Parameters:

element - The element to remove

Returns:

True if the element was found and removed

removeElementFromChild

protected boolean removeElementFromChild(T element)

removeElement

protected boolean removeElement(T element,
                                boolean topDownInvocation)

getElementsWithinArea

public com.badlogic.gdx.utils.Array<T> getElementsWithinArea(Shape area)

Specified by:

getElementsWithinArea in interface QuadTree<T extends Positionable>

getElementsWithinArea

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

Specified by:

getElementsWithinArea in interface QuadTree<T extends Positionable>

getElementsContainingPoint

public com.badlogic.gdx.utils.Array<T> getElementsContainingPoint(Point point)

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Positionable>

getElementsContainingPoint

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

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Positionable>

getElementsIntersectingLineSegment

public com.badlogic.gdx.utils.Array<T> getElementsIntersectingLineSegment(LineSegment lineSegment)

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Positionable>

getElementsIntersectingLineSegment

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

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Positionable>

getElements

public com.badlogic.gdx.utils.Array<T> getElements()

Specified by:

getElements in interface QuadTree<T extends Positionable>

getElements

public void getElements(com.badlogic.gdx.utils.Array<T> result)

Specified by:

getElements in interface QuadTree<T extends Positionable>

getTotalQuads

public int getTotalQuads()

Specified by:

getTotalQuads in interface QuadTree<T extends Positionable>

getTotalElements

public int getTotalElements()

Specified by:

getTotalElements in interface QuadTree<T extends Positionable>

clearTotalElementsCache

protected void clearTotalElementsCache()

positionChanged

public void positionChanged(T moved)

Specified by:

positionChanged in interface PositionChangeListener<T extends Positionable>

getParent

public QuadTree<T> getParent()

Specified by:

getParent in interface QuadTree<T extends Positionable>

getTotalMergeOperations

public int getTotalMergeOperations()

getElementLimitPerQuad

public int getElementLimitPerQuad()

getMergeWatermark

public int getMergeWatermark()

getMinimumQuadWidth

public float getMinimumQuadWidth()

Specified by:

getMinimumQuadWidth in interface QuadTree<T extends Positionable>

getMinimumQuadHeight

public float getMinimumQuadHeight()

Specified by:

getMinimumQuadHeight in interface QuadTree<T extends Positionable>