Autopsy  4.18.0
Graphical digital forensics platform for The Sleuth Kit and other tools.
Classes | Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
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

 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< XYZPointX_COMPARATOR
 
static final Comparator< XYZPointY_COMPARATOR
 
static final Comparator< XYZPointZ_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
pointsThe 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 ( value)

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

Parameters
valueT 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 ( value)

Does the tree contain the value.

Parameters
valueT 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
parentThe parent of this node or null if this will be root.
pointsThe points to be balanced in the tree.
depthThe 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,
value 
)

Searches for numNeighbors nearest neighbor.

Parameters
numNeighborsNumber of neighbors to retrieve. Can return more than numNeighbors, if last nodes are equal distances.
valueto 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
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
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:

Copyright © 2012-2021 Basis Technology. Generated on: Thu Jul 8 2021
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.