Package jadex.extension.envsupport.environment.space2d

Class KdTree

java.lang.Object

jadex.extension.envsupport.environment.space2d.KdTree

public class KdTree
extends java.lang.Object

Implementation of a 2D variant of a k-dimensional-tree for spatial separation and searches.

Field Summary

Fields

Modifier and Type	Field	Description
protected static int	DEFAULT_MAX_LEAF_NODE_SIZE	Default value for maximum number of objects in leaf nodes.
protected static int	DEFAULT_MAX_MEDIAN_SAMPLES	Default value for maximum number of samples taken to estimate coordinate median.
protected int	maxLeafNodeSize	Maximum number of objects in leaf nodes.
protected int	maxMedianSamples	Maximum number of samples taken to estimate coordinate median.
protected java.util.Random	random	Random for picking object samples for estimating median.
protected KdNode	rootNode	The root node.

Constructor Summary

Constructors

Constructor	Description
KdTree()	Generates an empty KdTree using default configuration.
KdTree(int maxLeafNodeSize, int maxMedianSamples)	Generates an empty KdTree.

Method Summary

Modifier and Type	Method	Description
void	addObject(ISpaceObject obj)	Adds an object to the tree.
ISpaceObject	getNearestObject(IVector2 point)	Finds an object closest to the given point (exhaustive search!).
ISpaceObject	getNearestObject(IVector2 point, double searchRadius)	Finds an object closest to the given point with a given search radius.
ISpaceObject	getNearestObject(IVector2 point, double searchRadius, IFilter filter)	Finds an object closest to the given point with a given search radius, while filtering objects.
ISpaceObject	getNearestObject(IVector2 point, IFilter filter)	Finds an object closest to the given point while filtering objects (exhaustive search!).
java.util.List<ISpaceObject>	getNearestObjects(IVector2 point, double radius)	Finds all objects within a given search radius.
java.util.List<ISpaceObject>	getNearestObjects(IVector2 point, double radius, IFilter filter)	Finds all objects within a given search radius.
void	rebuild()	Rebuilds the tree, updating spatial information, adding objects and removing objects.
void	removeObject(ISpaceObject obj)	Removes an object to the tree.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MAX_LEAF_NODE_SIZE

protected static final int DEFAULT_MAX_LEAF_NODE_SIZE

Default value for maximum number of objects in leaf nodes.

See Also:

Constant Field Values

DEFAULT_MAX_MEDIAN_SAMPLES

protected static final int DEFAULT_MAX_MEDIAN_SAMPLES

Default value for maximum number of samples taken to estimate coordinate median.

See Also:

Constant Field Values

rootNode

protected KdNode rootNode

The root node.

random

protected java.util.Random random

Random for picking object samples for estimating median.

maxLeafNodeSize

protected int maxLeafNodeSize

Maximum number of objects in leaf nodes.

maxMedianSamples

protected int maxMedianSamples

Maximum number of samples taken to estimate coordinate median.

Constructor Detail

KdTree

public KdTree()

Generates an empty KdTree using default configuration.

KdTree

public KdTree(int maxLeafNodeSize,
              int maxMedianSamples)

Generates an empty KdTree.

Parameters:

maxLeafNodeSize - Maximum number of objects in leaf nodes.

maxMedianSamples - Maximum number of samples taken to estimate coordinate median.

Method Detail

getNearestObjects

public java.util.List<ISpaceObject> getNearestObjects(IVector2 point,
                                                      double radius)

Finds all objects within a given search radius.

Parameters:

point - Center of the search area.

radius - The search radius.

getNearestObjects

public java.util.List<ISpaceObject> getNearestObjects(IVector2 point,
                                                      double radius,
                                                      IFilter filter)

Finds all objects within a given search radius.

Parameters:

point - Center of the search area.

radius - The search radius.

filter - Object filter.

getNearestObject

public ISpaceObject getNearestObject(IVector2 point)

Finds an object closest to the given point (exhaustive search!).

Parameters:

point - The point.

Returns:

Object closest to the point.

getNearestObject

public ISpaceObject getNearestObject(IVector2 point,
                                     IFilter filter)

Finds an object closest to the given point while filtering objects (exhaustive search!).

Parameters:

point - The point.

filter - Object filter.

Returns:

Object closest to the point.

getNearestObject

public ISpaceObject getNearestObject(IVector2 point,
                                     double searchRadius)

Finds an object closest to the given point with a given search radius.

Parameters:

point - The point.

searchRadius - The search radius.

Returns:

Object closest to the point.

getNearestObject

public ISpaceObject getNearestObject(IVector2 point,
                                     double searchRadius,
                                     IFilter filter)

Finds an object closest to the given point with a given search radius, while filtering objects.

Parameters:

point - The point.

searchRadius - The search radius.

filter - Object filter.

Returns:

Object closest to the point.

addObject

public void addObject(ISpaceObject obj)

Adds an object to the tree. The object will not become visible until rebuild() is called.

Parameters:

obj - The object being added.

removeObject

public void removeObject(ISpaceObject obj)

Removes an object to the tree. The object will not vanish until rebuild() is called.

Parameters:

obj - The object being removed.

rebuild

public void rebuild()

Rebuilds the tree, updating spatial information, adding objects and removing objects.