Facemorph.mdl
Class KdTree

java.lang.Object
  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