Maven module :un.api : api-geometry :
Class :
un.api.geometry.index.quadtrees.QuadTreeBasic
Extends/Implements :
un.api.geometry.index.quadtrees.QuadTreeType
Subclasses : -
Variables : -
Functions :
newQuadTree,
quadTreeClear,
quadTreeGetPositionX,
quadTreeGetPositionY,
quadTreeGetSizeX,
quadTreeGetSizeY,
quadTreeInsert,
quadTreeIterateObjects,
quadTreeQueryAreaContaining,
quadTreeQueryAreaOverlapping,
quadTreeQueryRaycast,
quadTreeQueryRaycastQuadrants,
quadTreeRemove,
quadTreeTraverse,
toString
public QuadTreeType
newQuadTree (Vector size, Vector position)
public void
quadTreeClear ()
public double
quadTreeGetPositionX ()
public double
quadTreeGetPositionY ()
public double
quadTreeGetSizeX ()
public double
quadTreeGetSizeY ()
public boolean
quadTreeInsert (T item)
public void
quadTreeIterateObjects (Predicate f)
public void
quadTreeQueryAreaContaining (BBox area, SortedSet items)
public void
quadTreeQueryAreaOverlapping (BBox area, SortedSet items)
public void
quadTreeQueryRaycast (Ray ray, SortedSet> items)
public void
quadTreeQueryRaycastQuadrants (Ray ray, SortedSet> items)
public boolean
quadTreeRemove (T item)
public void
quadTreeTraverse (QuadTreeTraversalType traversal)
public String
toString ()
An extremely simple quadtree implementation. This implementation emphasizes
simplicity and correctness over performance, to serve as a base for an
understanding of the other implementations.
The tree has the following properties (or lack thereof):
In most games and other simulations, objects are inserted into an empty
quadtree once per frame. If most of those objects do not move (such as
static geometry in the game/simulation world), then they will always be
inserted into the same point in the tree and re-inserting them every frame
is wasteful and/or redundant. An obvious optimization, therefore, is to
distinguish between static and movable objects in the tree and to provide
support for removing just the movable objects in one efficient operation.
As various operations can potentially traverse the entire tree, it is
desirable to keep the number of nodes (quadrants) in the tree to a minimum.
This implementation does not allow the programmer to specify a minimum size
for quadrants and does not attempt to remove redundant nodes when an object
is removed from the tree.
Each child quadrant of a given quadrant is exactly half the width and
height of the parent.
Values of type
QuadTreeBasiccannot be safely accessed frommultiple threads without explicit synchronization.
@param
@author Mark Raynsford