org.sleuthkit.autopsy.geolocation.KdTree< T extends KdTree.XYZPoint > Class Template Reference

Inherits Iterable< T >.

Classes
class	EuclideanComparator
class	KdNode
class	XYZPoint

Public Member Functions
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 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 50 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 113 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 154 of file KdTree.java.

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

(

)

Definition at line 102 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 394 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 206 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 406 of file KdTree.java.

Member Data Documentation

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

staticprivate

Definition at line 54 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 57 of file KdTree.java.

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 >.getRoot(), and org.sleuthkit.autopsy.geolocation.KdTree< 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 62 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 75 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 88 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