Package jadex.extension.envsupport.environment.space2d

Class KdNode

java.lang.Object

jadex.extension.envsupport.environment.space2d.KdNode

public class KdNode
extends java.lang.Object

Node for the k-dimensional-tree.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static interface	KdNode.IKdValueFetcher	Interface for hyperplane coordinate value fetchers.
protected static class	KdNode.KdValueFetcherX	Fetcher for the x-axis values.
protected static class	KdNode.KdValueFetcherY	Fetcher for the x-axis values.

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.List<ISpaceObject>	content	List containing objects in leaf nodes, null otherwise.
protected KdNode.IKdValueFetcher	fetcher	Value fetcher for fetching the correct coordinate on the splitting hyperplane.
protected double	hyperplane	Coordinate for the splitting hyperplane.
protected KdNode	left	Node for objects with coordinate below the splitting hyperplane, null for leaf nodes.
protected int	maxLeafNodeSize	Default value for maximum number of objects in leaf nodes.
protected int	maxMedianSamples	Default value for maximum number of samples taken to estimate coordinate median.
protected KdNode	right	Node for objects with coordinate above the splitting hyperplane, null for leaf nodes.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	KdNode(java.util.List<ISpaceObject> input, java.util.Random random)	Generates a new KdNode with the given input using default configuration.
protected	KdNode(java.util.List<ISpaceObject> input, java.util.Random random, int maxLeafNodeSize, int maxMedianSamples)	Generates a new KdNode with the given input.
protected	KdNode(java.util.List<ISpaceObject> input, java.util.Random random, KdNode.IKdValueFetcher fetcher, int maxLeafNodeSize, int maxMedianSamples)	Generates a new KdNode with the given input.

Method Summary

Modifier and Type	Method	Description
protected double	estimateMedian(java.util.List<ISpaceObject> input, java.util.Random random, KdNode.IKdValueFetcher fetcher)	Estimates the median value of the hyperplane coordinate of the input using random sampling.
protected static IVector2	getDistance(ISpaceObject obj, IVector2 point)
ISpaceObject	getNearestObject(IVector2 point, double radiusSquared)	Finds the object nearest to a given point within a search radius.
ISpaceObject	getNearestObject(IVector2 point, double radiusSquared, IFilter filter)	Finds the object nearest to a given point within a search radius while filtering objects.
java.util.List<ISpaceObject>	getNearestObjects(IVector2 point, double radiusSquared, IFilter filter)	Finds all objects within a given search radius.
protected static IVector2	getPosition(ISpaceObject obj)

Methods inherited from class java.lang.Object

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

Field Detail

maxLeafNodeSize

protected int maxLeafNodeSize

Default value for maximum number of objects in leaf nodes.

maxMedianSamples

protected int maxMedianSamples

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

fetcher

protected KdNode.IKdValueFetcher fetcher

Value fetcher for fetching the correct coordinate on the splitting hyperplane.

left

protected KdNode left

Node for objects with coordinate below the splitting hyperplane, null for leaf nodes.

right

protected KdNode right

Node for objects with coordinate above the splitting hyperplane, null for leaf nodes.

hyperplane

protected double hyperplane

Coordinate for the splitting hyperplane.

content

protected java.util.List<ISpaceObject> content

List containing objects in leaf nodes, null otherwise.

Constructor Detail

KdNode

protected KdNode(java.util.List<ISpaceObject> input,
                 java.util.Random random)

Generates a new KdNode with the given input using default configuration.

Parameters:

input - The objects.

random - Source of randomness for median estimation sampling.

KdNode

protected KdNode(java.util.List<ISpaceObject> input,
                 java.util.Random random,
                 int maxLeafNodeSize,
                 int maxMedianSamples)

Generates a new KdNode with the given input.

Parameters:

input - The objects.

random - Source of randomness for median estimation sampling.

maxLeafNodeSize - Maximum number of objects in leaf nodes.

maxMedianSamples - Maximum number of samples taken to estimate median for hyperplane.

KdNode

protected KdNode(java.util.List<ISpaceObject> input,
                 java.util.Random random,
                 KdNode.IKdValueFetcher fetcher,
                 int maxLeafNodeSize,
                 int maxMedianSamples)

Generates a new KdNode with the given input.

Parameters:

input - The objects.

random - Source of randomness for median estimation sampling.

fetcher - Value fetcher for the coordinate of the current hyperplane.

maxLeafNodeSize - Maximum number of objects in leaf nodes.

maxMedianSamples - Maximum number of samples taken to estimate median for hyperplane.

Method Detail

getNearestObjects

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

Finds all objects within a given search radius.

Parameters:

point - Center of the search area.

radiusSquared - Square of the search radius.

filter - Object filter.

getNearestObject

public ISpaceObject getNearestObject(IVector2 point,
                                     double radiusSquared)

Finds the object nearest to a given point within a search radius.

Parameters:

point - The point.

radiusSquared - The squared search radius.

Returns:

Object nearest to the point or null if none is found.

getNearestObject

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

Finds the object nearest to a given point within a search radius while filtering objects.

Parameters:

point - The point.

radiusSquared - The squared search radius.

filter - Object filter.

Returns:

Object nearest to the point or null if none is found.

estimateMedian

protected double estimateMedian(java.util.List<ISpaceObject> input,
                                java.util.Random random,
                                KdNode.IKdValueFetcher fetcher)

Estimates the median value of the hyperplane coordinate of the input using random sampling.

Parameters:

input - The input objects.

random - A source of randomness for sampling.

fetcher - The value fetcher for the hyperplane coordinate.

Returns:

Estimated coordinate median.

getPosition

protected static final IVector2 getPosition(ISpaceObject obj)

getDistance

protected static final IVector2 getDistance(ISpaceObject obj,
                                            IVector2 point)