com.yobotics.simulationconstructionset.util
Class KDTree

java.lang.Object
  com.yobotics.simulationconstructionset.util.KDTree

public class KDTree
extends java.lang.Object

Use this class to efficiently search for closest points to various test points of interest. The dimensionality of the points is arbitrary (D > 0), and the tree's splitting is binary (K = 2).

Constructor Summary

KDTree(double[][] points, int maxPointsInLeaves)
Creates a KDTree from an array of points and an equally sized array of objects.

KDTree(double[][] points, java.lang.Object[] objects, int maxPointsInLeaves)
Creates a KDTree from an array of points and an equally sized array of objects.

KDTree(java.lang.String BDITerrainFilePath, int maxPointsInLeaves)
Creates a KDTree from an array of (X, Y) terrain points and an equally sized array of (Z) terrain heights.

Method Summary

java.lang.Object	closestObject(double[] testPoint)
java.lang.Object	closestObject(double[] testPoint, double maxDistance)
java.util.ArrayList<java.lang.Object>	closestObjects(double[] testPoint, int numObjects, double maxDistance)
double[]	closestPoint(double[] testPoint) closestPoint
double[]	closestPoint(double[] testPoint, double maxDistance)
double[]	closestPointBruteForceSearch(double[] testPoint)
java.util.ArrayList<double[]>	closestPoints(double[] testPoint, int numPoints, double maxDistance)
static double	distanceSquared(double[] point1, double[] point2) This is a fast Euclidean distance metric.
java.lang.Object	getClosestNovelObject(double[] testPoint, double maxDistance, boolean preserveAsNovel)
java.util.ArrayList<java.lang.Object>	getClosestNovelObjects(double[] testPoint, double maxDistance, boolean preserveAsNovel)
void	getExtents(double[] min, double[] max)
double[][]	getPoints() Returns the list of points.
static double[][]	loadPoints3D(java.io.BufferedReader bufferedReader) Loads terrain data from a BufferedReader and returns the Terrain object represented by the data.
static double[][]	loadPoints3D(java.lang.String filename) Loads an ASCII file of 3D points.
static void	main(java.lang.String[] args) This method tests the KD Tree using a BDI terrain file containing an unordered collection of 3D points.
KDTree	prunePointsCopy(double minDistanceBetweenPoints)
static void	testLookupSamePointOnGrid(KDTree kdTree) Test a KDTree to make sure it returns the same point if you query for each point
static void	testLookupSamePointPlusDeltaOnGrid(KDTree kdTree, double maxDelta, int skipPoints, double maxDistance) Test a KDTree to make sure it gives you back the same point or a closer point if you query for each point plus a small delta
static void	testLookupTimingOnGrid(KDTree kdTree, boolean checkWithBruteForce)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KDTree

public KDTree(double[][] points,
              java.lang.Object[] objects,
              int maxPointsInLeaves)

Creates a KDTree from an array of points and an equally sized array of objects. The value MaxPointsInLeaves specifies the maximum number of points in a leaf Node. Use a small value (5-20) unless building the tree takes too long.

Parameters:

points - double[][]

objects - Object[]

maxPointsInLeaves - int

KDTree

public KDTree(double[][] points,
              int maxPointsInLeaves)

Creates a KDTree from an array of points and an equally sized array of objects. The value MaxPointsInLeaves specifies the maximum number of points in a leaf Node. Use a small value (5-20) unless building the tree takes too long.

Parameters:

points - double[][]

maxPointsInLeaves - int

KDTree

public KDTree(java.lang.String BDITerrainFilePath,
              int maxPointsInLeaves)

Creates a KDTree from an array of (X, Y) terrain points and an equally sized array of (Z) terrain heights. The value MaxPointsInLeaves specifies the maximum number of points in a leaf Node. Use a small value (5-20) unless building the tree takes too long.

Parameters:

points - double[][]

maxPointsInLeaves - int

Method Detail

getPoints

public double[][] getPoints()

Returns the list of points. The user may not have this in advance if the points are loaded from a file.

Returns:

double[][]

getExtents

public void getExtents(double[] min,
                       double[] max)

prunePointsCopy

public KDTree prunePointsCopy(double minDistanceBetweenPoints)

closestPoint

public double[] closestPoint(double[] testPoint)

closestPoint

Parameters:

testPoint - double[]

Returns:

double[]

closestPoint

public double[] closestPoint(double[] testPoint,
                             double maxDistance)

closestPointBruteForceSearch

public double[] closestPointBruteForceSearch(double[] testPoint)

closestObject

public java.lang.Object closestObject(double[] testPoint)

closestObject

public java.lang.Object closestObject(double[] testPoint,
                                      double maxDistance)

closestObjects

public java.util.ArrayList<java.lang.Object> closestObjects(double[] testPoint,
                                                            int numObjects,
                                                            double maxDistance)

closestPoints

public java.util.ArrayList<double[]> closestPoints(double[] testPoint,
                                                   int numPoints,
                                                   double maxDistance)

getClosestNovelObject

public java.lang.Object getClosestNovelObject(double[] testPoint,
                                              double maxDistance,
                                              boolean preserveAsNovel)

getClosestNovelObjects

public java.util.ArrayList<java.lang.Object> getClosestNovelObjects(double[] testPoint,
                                                                    double maxDistance,
                                                                    boolean preserveAsNovel)

loadPoints3D

public static double[][] loadPoints3D(java.lang.String filename)

Loads an ASCII file of 3D points. The first line must contain the number of points, and all subsequent lines must contain three scalar values.

Parameters:

filename - String

Returns:

OneDTerrainGrid

loadPoints3D

public static double[][] loadPoints3D(java.io.BufferedReader bufferedReader)

Loads terrain data from a BufferedReader and returns the Terrain object represented by the data. Returns null if the operation does not succeed. There must be 3 scalar values on each line.

Parameters:

bufferedReader - BufferedReader

Returns:

BreadthFirstStateEnumerator

distanceSquared

public static double distanceSquared(double[] point1,
                                     double[] point2)

This is a fast Euclidean distance metric.

Parameters:

point1 - double[]

point2 - double[]

Returns:

double

main

public static void main(java.lang.String[] args)

This method tests the KD Tree using a BDI terrain file containing an unordered collection of 3D points.

Parameters:

args - String[]

testLookupTimingOnGrid

public static void testLookupTimingOnGrid(KDTree kdTree,
                                          boolean checkWithBruteForce)

testLookupSamePointOnGrid

public static void testLookupSamePointOnGrid(KDTree kdTree)

Test a KDTree to make sure it returns the same point if you query for each point

Parameters:

kdTree - KDTree

testLookupSamePointPlusDeltaOnGrid

public static void testLookupSamePointPlusDeltaOnGrid(KDTree kdTree,
                                                      double maxDelta,
                                                      int skipPoints,
                                                      double maxDistance)

Test a KDTree to make sure it gives you back the same point or a closer point if you query for each point plus a small delta

Parameters:

kdTree - KDTree