Inherits Iterable< T >.

Classes
class	EuclideanComparator

class	KdNode

class	XYZPoint

Public Member Functions
	KdTree ()

	KdTree (List< XYZPoint > list)

	KdTree (List< XYZPoint > list, int k)

boolean	add (T value)

boolean	contains (T value)

Iterator< T >	iterator ()

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

boolean	remove (T value)

Iterator< T >	reverse_iterator ()

Static Protected Attributes
static final int	X_AXIS = 0

static final int	Y_AXIS = 1

static final int	Z_AXIS = 2

Static Private Member Functions
static KdNode	createNode (List< XYZPoint > list, int k, int depth)

static final< T extends KdTree.XYZPoint > KdNode	getNode (KdTree< T > tree, T value)

static final List< XYZPoint >	getTree (KdNode root)

static< TextendsXYZPoint > void	search (final KdNode node, final Deque< T > results)

static final< T extends KdTree.XYZPoint > void	searchNode (T value, KdNode node, int K, TreeSet< KdNode > results, Set< KdNode > examined)

Private Attributes
int	k = 3

KdNode	root = null

Static Private Attributes
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 52 of file KdTree.java.

Constructor & Destructor Documentation

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

Default constructor.

Definition at line 106 of file KdTree.java.

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

Constructor for creating a more balanced tree. It uses the "median of points" algorithm.

Parameters

list	of XYZPoints.

Definition at line 115 of file KdTree.java.

org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.KdTree	(	List< XYZPoint >	list,
		int	k
	)

Constructor for creating a more balanced tree. It uses the "median of points" algorithm.

Parameters

list	of XYZPoints.
k	of the tree.

Definition at line 129 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 197 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 239 of file KdTree.java.

static KdNode org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.createNode	(	List< XYZPoint >	list,
		int	k,
		int	depth
	)

staticprivate

Creates node from list of XYZPoints.

Parameters

list	of XYZPoints.
k	of the tree.
depth	depth of the node.

Returns: node created.

Definition at line 145 of file KdTree.java.

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

static final<T extends KdTree.XYZPoint> KdNode org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.getNode	(	KdTree< T >	tree,
		T	value
	)

staticprivate

Locates T in the tree.

Parameters

tree	to search.
value	to search for.

Returns: KdNode or NULL if not found

Definition at line 256 of file KdTree.java.

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

static final List<XYZPoint> org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.getTree ( KdNode root )

staticprivate

Gets the (sub) tree rooted at root.

Parameters

root	of tree to get nodes for.

Returns: points in (sub) tree, not including root.

Definition at line 337 of file KdTree.java.

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

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 526 of file KdTree.java.

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

Searches the K nearest neighbor.

Parameters

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

Returns: Collection of T neighbors.

Definition at line 365 of file KdTree.java.

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

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

Removes first occurrence of value in the tree.

Parameters

value T to remove from the tree.

Returns: True if value was removed from the tree.

Definition at line 287 of file KdTree.java.

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 538 of file KdTree.java.

static <TextendsXYZPoint> void org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.search	(	final KdNode	node,
		final Deque< T >	results
	)

staticprivate

Adds, in a specified queue, a given node and its related nodes (lesser, greater).

Parameters

node	Node to check. May be null.
results	Queue containing all found entries. Must not be null.

Definition at line 489 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.KdTree< MapWaypoint >.iterator(), org.sleuthkit.autopsy.geolocation.KdTree< MapWaypoint >.reverse_iterator(), and org.sleuthkit.autopsy.geolocation.KdTree< MapWaypoint >.search().

static final<T extends KdTree.XYZPoint> void org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.searchNode	(	T	value,
		KdNode	node,
		int	K,
		TreeSet< KdNode >	results,
		Set< KdNode >	examined
	)

staticprivate

Definition at line 408 of file KdTree.java.

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

Member Data Documentation

int org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.k = 3

private

Definition at line 54 of file KdTree.java.

Referenced by org.sleuthkit.autopsy.geolocation.KdTree< MapWaypoint >.createNode().

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

private

Definition at line 55 of file KdTree.java.

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

final int org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.X_AXIS = 0

staticprotected

Definition at line 99 of file KdTree.java.

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) {
            if (o1.x < o2.x)
                return -1;
            if (o1.x > o2.x)
                return 1;
            return 0;
        }
    }

Definition at line 57 of file KdTree.java.

final int org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint >.Y_AXIS = 1

staticprotected

Definition at line 100 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) {
            if (o1.y < o2.y)
                return -1;
            if (o1.y > o2.y)
                return 1;
            return 0;
        }
    }

Definition at line 71 of file KdTree.java.

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

staticprotected

Definition at line 101 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) {
            if (o1.z < o2.z)
                return -1;
            if (o1.z > o2.z)
                return 1;
            return 0;
        }
    }

Definition at line 85 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

Static Protected Attributes

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation