Inherits Iterable< T >.

Classes
class	EuclideanComparator

class	KdNode

class	XYZPoint

Public Member Functions
	KdTree ()

	KdTree (List< T > points)

boolean	add (T value)

boolean	contains (T value)

KdNode	getRoot ()

Iterator< T >	iterator ()

Collection< T >	nearestNeighbourSearch (int numNeighbors, T value)

Iterator< T >	reverse_iterator ()

Private Member Functions
KdNode	getBalancedNode (KdNode parent, List< T > points, int depth)

Private Attributes
KdNode	root = null

Static Private Attributes
static final int	DIMENSIONS = 2

static final double	EARTH_RADIUS = 6371e3

static final Comparator< XYZPoint >	X_COMPARATOR

static final Comparator< XYZPoint >	Y_COMPARATOR

static final Comparator< XYZPoint >	Z_COMPARATOR

Detailed Description

A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

See also: K-D Tree (Wikipedia)

Original other was JustinWetherell phish.nosp@m.man3.nosp@m.579@g.nosp@m.mail.nosp@m..com.

See also: Original version

Definition at line 51 of file KdTree.java.

Constructor & Destructor Documentation

org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.KdTree ( )

Main constructor.

Definition at line 102 of file KdTree.java.

org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.KdTree ( List< T > points )

Constructor that creates a balanced tree with the provided nodes.

Parameters

points The points to add and balance.

Definition at line 110 of file KdTree.java.

Member Function Documentation

boolean org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.add ( T value )

Adds value to the tree. Tree can contain multiple equal values.

Parameters

value T to add to the tree.

Returns: True if successfully added to tree.

Definition at line 163 of file KdTree.java.

boolean org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.contains ( T value )

Does the tree contain the value.

Parameters

value T to locate in the tree.

Returns: True if tree contains value.

Definition at line 204 of file KdTree.java.

KdNode org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.getBalancedNode	(	KdNode	parent,
		List< T >	points,
		int	depth
	)

private

Recursively creates balanced KdNode's from the given list. NOTE: The approach is to: 1) sort the list based on the depth's comparator 2) find a center point 3) For lesser and greater, recurse until base case.

There may be more efficient means of achieving balanced nodes.

Parameters

parent	The parent of this node or null if this will be root.
points	The points to be balanced in the tree.
depth	The current depth (used to determine axis to sort on).

Returns: The balanced KdNode.

Definition at line 134 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.KdTree< org.sleuthkit.autopsy.geolocation.MapWaypoint >.getBalancedNode(), and org.sleuthkit.autopsy.geolocation.KdTree< org.sleuthkit.autopsy.geolocation.MapWaypoint >.KdTree().

KdNode org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.getRoot ( )

Definition at line 118 of file KdTree.java.

Iterator<T> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.iterator ( )

Searches all entries from the first to the last entry.

Returns: Iterator allowing to iterate through a collection containing all found entries.

Definition at line 444 of file KdTree.java.

Collection<T> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.nearestNeighbourSearch	(	int	numNeighbors,
		T	value
	)

Searches for numNeighbors nearest neighbor.

Parameters

numNeighbors	Number of neighbors to retrieve. Can return more than numNeighbors, if last nodes are equal distances.
value	to find neighbors of.

Returns: Collection of T neighbors.

Definition at line 256 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.MapPanel.findClosestWaypoint().

Iterator<T> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.reverse_iterator ( )

Searches all entries from the last to the first entry.

Returns: Iterator allowing to iterate through a collection containing all found entries.

Definition at line 456 of file KdTree.java.

Member Data Documentation

final int org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.DIMENSIONS = 2

staticprivate

Definition at line 55 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.KdNode.compareTo().

final double org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.EARTH_RADIUS = 6371e3

staticprivate

Definition at line 58 of file KdTree.java.

KdNode org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.root = null

private

Definition at line 56 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.KdTree< org.sleuthkit.autopsy.geolocation.MapWaypoint >.add(), org.sleuthkit.autopsy.geolocation.KdTree< org.sleuthkit.autopsy.geolocation.MapWaypoint >.getRoot(), and org.sleuthkit.autopsy.geolocation.KdTree< org.sleuthkit.autopsy.geolocation.MapWaypoint >.nearestNeighbourSearch().

final Comparator<XYZPoint> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.X_COMPARATOR

staticprivate

Initial value:

= new Comparator<XYZPoint>() {
        
        @Override
        public int compare(XYZPoint o1, XYZPoint o2) {
            return Double.compare(o1.x, o2.x);
        }
    }

Compares two XYZPoints by their X value.

Definition at line 63 of file KdTree.java.

final Comparator<XYZPoint> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.Y_COMPARATOR

staticprivate

Initial value:

= new Comparator<XYZPoint>() {
        
        @Override
        public int compare(XYZPoint o1, XYZPoint o2) {
            return Double.compare(o1.y, o2.y);
        }
    }

Compares two XYZPoints by their Y value.

Definition at line 76 of file KdTree.java.

final Comparator<XYZPoint> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.Z_COMPARATOR

staticprivate

Initial value:

= new Comparator<XYZPoint>() {
        
        @Override
        public int compare(XYZPoint o1, XYZPoint o2) {
            return Double.compare(o1.z, o2.z);
        }
    }

Compares two XYZPoints by their Z value.

Definition at line 89 of file KdTree.java.

The documentation for this class was generated from the following file:

/home/carriersleuth/repos/autopsy/Core/src/org/sleuthkit/autopsy/geolocation/KdTree.java

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation