Facemorph.mdl
Class KdTree

java.lang.Object
  extended by Facemorph.mdl.KdTree

public class KdTree
extends java.lang.Object

KdTree implementation


Constructor Summary
KdTree(java.util.ArrayList<KdTreePoint> points)
          KdTree constructor
KdTree(java.util.ArrayList<KdTreePoint> points, int sortIndex)
          KdTree constructor
 
Method Summary
static double distance(double[] p, double[] q)
          Find the distance between two points
 KdTreePoint getNearest(KdTreePoint position)
          Get the nearest to the point
 KdTreePoint getNearest(KdTreePoint position, KdTreePoint currentNearest, double currentDistance)
          Get the nearest to position
static void quickSort(java.util.ArrayList<KdTreePoint> points, int index, int start, int len)
          Does a quick sort on the values given
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

KdTree

public KdTree(java.util.ArrayList<KdTreePoint> points)
KdTree constructor

Parameters:
points - the points to build the Kd tree from

KdTree

public KdTree(java.util.ArrayList<KdTreePoint> points,
              int sortIndex)
KdTree constructor

Parameters:
points - the points to put in this tree
sortIndex - the index of the split
Method Detail

getNearest

public KdTreePoint getNearest(KdTreePoint position)
Get the nearest to the point

Parameters:
position - the position
Returns:
return the closest point to the position

getNearest

public KdTreePoint getNearest(KdTreePoint position,
                              KdTreePoint currentNearest,
                              double currentDistance)
Get the nearest to position

Parameters:
position - the position we're looking for the nearest point to
currentNearest - the current nearest (or null at the start)
currentDistance - the distance of the current nearest from the target point
Returns:
return the nearest point

distance

public static double distance(double[] p,
                              double[] q)
Find the distance between two points

Parameters:
p - first point
q - second point
Returns:
returns the distance between the points

quickSort

public static void quickSort(java.util.ArrayList<KdTreePoint> points,
                             int index,
                             int start,
                             int len)
Does a quick sort on the values given

Parameters:
points - the values to sort
index - the data associated with each point.
start - the start of the portion of the array to sort
len - the length of the portion of the array to sort