org.mini2Dx.core.collisions

Class PointQuadTree<T extends Positionable>

java.lang.Object

org.mini2Dx.core.geom.Shape

org.mini2Dx.core.geom.Rectangle

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

All Implemented Interfaces:

QuadTree<T>, PositionChangeListener<T>, Parallelogram

Direct Known Subclasses:

RegionQuadTree

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

Implements a point quadtree

See Also:

Wikipedia: Point Quad Tree

Field Summary

Fields

Modifier and Type	Field and Description
protected PointQuadTree<T>	bottomLeft
protected PointQuadTree<T>	bottomRight
static com.badlogic.gdx.graphics.Color	ELEMENT_COLOR
protected int	elementLimitPerQuad
protected java.util.List<T>	elements
protected int	mergeWatermark
protected PointQuadTree<T>	parent
static com.badlogic.gdx.graphics.Color	QUAD_COLOR
protected PointQuadTree<T>	topLeft
protected PointQuadTree<T>	topRight
protected int	totalElementsCache

Constructor Summary

Constructors

Constructor and Description
PointQuadTree(int elementLimitPerQuad, float x, float y, float width, float height) Constructs a PointQuadTree with a specified element limit and no merging watermark.
PointQuadTree(int elementLimitPerQuad, int mergeWatermark, float x, float y, float width, float height) Constructs a PointQuadTree with a specified element limit and watermark
PointQuadTree(PointQuadTree<T> parent, float x, float y, float width, float height) Constructs a PointQuadTree as a child of another PointQuadTree

Method Summary

Modifier and Type	Method and Description
boolean	add(T element)
void	addAll(java.util.List<T> elementsToAdd)
protected boolean	addElement(T element)
protected boolean	addElementToChild(T element)
void	clear()
protected void	clearTotalElementsCache()
void	debugRender(Graphics g)
int	getElementLimitPerQuad()
java.util.List<T>	getElements()
void	getElements(java.util.List<T> result)
void	getElementsContainingPoint(java.util.Collection<T> result, Point point)
java.util.List<T>	getElementsContainingPoint(Point point)
void	getElementsIntersectingLineSegment(java.util.Collection<T> result, LineSegment lineSegment)
java.util.List<T>	getElementsIntersectingLineSegment(LineSegment lineSegment)
void	getElementsWithinArea(java.util.Collection<T> result, Shape area)
java.util.List<T>	getElementsWithinArea(Shape area)
int	getMergeWatermark()
QuadTree<T>	getParent()
int	getTotalElements()
int	getTotalQuads()
boolean	hasChildQuads()
protected boolean	isMergable()
protected void	merge()
void	positionChanged(T moved)
boolean	remove(T element)
void	removeAll(java.util.List<T> elementsToRemove)
protected boolean	removeElement(T element)
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, fill, getCenterX, getCenterY, getDistanceTo, getDistanceTo, getHeight, getMaxX, getMaxY, getMinX, getMinY, getNumberOfSides, getPolygon, getRotation, getVertices, getWidth, getX, getY, intersection, intersects, intersects, intersects, intersects, intersects, intersects, intersects, intersectsLineSegment, intersectsLineSegment, intersectsLineSegment, isCircle, lerp, rotate, rotateAround, set, set, set, set, setHeight, setRotation, setRotationAround, setRotationAround, setSize, setSize, setWidth, setX, setY, toString, translate

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

intersects

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, 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 PointQuadTree<T extends Positionable> parent

topLeft

protected PointQuadTree<T extends Positionable> topLeft

topRight

protected PointQuadTree<T extends Positionable> topRight

bottomLeft

protected PointQuadTree<T extends Positionable> bottomLeft

bottomRight

protected PointQuadTree<T extends Positionable> bottomRight

elements

protected java.util.List<T extends Positionable> elements

elementLimitPerQuad

protected final int elementLimitPerQuad

mergeWatermark

protected final int mergeWatermark

totalElementsCache

protected int totalElementsCache

Constructor Detail

PointQuadTree

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

Constructs a PointQuadTree with a specified element limit and watermark

Parameters:

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

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

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(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(PointQuadTree<T> parent,
                     float x,
                     float y,
                     float width,
                     float height)

Constructs a PointQuadTree as a child of another PointQuadTree

Parameters:

parent - The parent PointQuadTree

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

debugRender

public void debugRender(Graphics g)

Specified by:

debugRender in interface QuadTree<T extends Positionable>

addAll

public void addAll(java.util.List<T> elementsToAdd)

Specified by:

addAll in interface QuadTree<T extends Positionable>

add

public boolean add(T element)

Specified by:

add in interface QuadTree<T extends Positionable>

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(java.util.List<T> elementsToRemove)

Specified by:

removeAll in interface QuadTree<T extends Positionable>

remove

public boolean remove(T element)

Specified by:

remove in interface QuadTree<T extends Positionable>

clear

public void clear()

removeElementFromChild

protected boolean removeElementFromChild(T element)

removeElement

protected boolean removeElement(T element)

getElementsWithinArea

public java.util.List<T> getElementsWithinArea(Shape area)

Specified by:

getElementsWithinArea in interface QuadTree<T extends Positionable>

getElementsWithinArea

public void getElementsWithinArea(java.util.Collection<T> result,
                                  Shape area)

Specified by:

getElementsWithinArea in interface QuadTree<T extends Positionable>

getElementsContainingPoint

public java.util.List<T> getElementsContainingPoint(Point point)

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Positionable>

getElementsContainingPoint

public void getElementsContainingPoint(java.util.Collection<T> result,
                                       Point point)

Specified by:

getElementsContainingPoint in interface QuadTree<T extends Positionable>

getElementsIntersectingLineSegment

public java.util.List<T> getElementsIntersectingLineSegment(LineSegment lineSegment)

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Positionable>

getElementsIntersectingLineSegment

public void getElementsIntersectingLineSegment(java.util.Collection<T> result,
                                               LineSegment lineSegment)

Specified by:

getElementsIntersectingLineSegment in interface QuadTree<T extends Positionable>

getElements

public java.util.List<T> getElements()

Specified by:

getElements in interface QuadTree<T extends Positionable>

getElements

public void getElements(java.util.List<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>

getElementLimitPerQuad

public int getElementLimitPerQuad()

getMergeWatermark

public int getMergeWatermark()

hasChildQuads

public boolean hasChildQuads()