Class KdTree<X extends Jcg.geometry.Point_>

java.lang.Object

KdTree<X>

public class KdTree<X extends Jcg.geometry.Point_>
extends java.lang.Object

A class implementing a Kd-tree data structure

Version:

jan 2014

Author:

Luca Castelli Aleardi and Steve Oudot (Ecole Polytechnique, INF562)

Field Summary

Fields

Modifier and Type	Field and Description
private int	cutDimension
private double	cutValue
private KdTree<X>	lowerHalf
private int	numPoints
private int	pointDimension
private PointCloud	points
private KdTree<X>	upperHalf

Constructor Summary

Constructors

Constructor and Description
KdTree(PointCloud N, int pDim, int cutDim) Constructor -- builds the entire Kd-tree at once recursively

Method Summary

Methods

Modifier and Type	Method and Description
static <X extends Jcg.geometry.Point_> boolean	checkBalance(KdTree<X> t)
static <X extends Jcg.geometry.Point_> KdTree<X>	constructDataStructure(PointCloud N, int pDim) Construct a Kd-Tree from a point cloud (in dimension pDim)
static <X extends Jcg.geometry.Point_> int	leavesNumber(KdTree<X> t)
PointCloud	OrthogonalRangeSearch(X q, double sqRad) Range search: return the list of nearest point to a given query point q.
static <X extends Jcg.geometry.Point_> int	size(KdTree<X> t)
static PointCloud[]	split(PointCloud N, double cutValue, int cutDim) Split a point cloud into two sub-point clouds (lower an upper point clouds)
static <X extends Jcg.geometry.Point_> java.util.ArrayList<Jcg.geometry.Point_d>	toList(KdTree<X> t, java.util.ArrayList<Jcg.geometry.Point_d> list)
static <X extends Jcg.geometry.Point_> java.lang.String	toString(KdTree<X> t)

Methods inherited from class java.lang.Object

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

Field Detail

pointDimension

private int pointDimension

cutDimension

private int cutDimension

cutValue

private double cutValue

numPoints

private int numPoints

points

private PointCloud points

lowerHalf

private KdTree<X extends Jcg.geometry.Point_> lowerHalf

upperHalf

private KdTree<X extends Jcg.geometry.Point_> upperHalf

Constructor Detail

KdTree

public KdTree(PointCloud N,
      int pDim,
      int cutDim)

Constructor -- builds the entire Kd-tree at once recursively

Method Detail

split

public static PointCloud[] split(PointCloud N,
                 double cutValue,
                 int cutDim)

Split a point cloud into two sub-point clouds (lower an upper point clouds)

constructDataStructure

public static <X extends Jcg.geometry.Point_> KdTree<X> constructDataStructure(PointCloud N,
                                                               int pDim)

Construct a Kd-Tree from a point cloud (in dimension pDim)

OrthogonalRangeSearch

public PointCloud OrthogonalRangeSearch(X q,
                               double sqRad)

Range search: return the list of nearest point to a given query point q. The output is the set of points at distance at most sqRad from q.

size

public static <X extends Jcg.geometry.Point_> int size(KdTree<X> t)

checkBalance

public static <X extends Jcg.geometry.Point_> boolean checkBalance(KdTree<X> t)

leavesNumber

public static <X extends Jcg.geometry.Point_> int leavesNumber(KdTree<X> t)

toString

public static <X extends Jcg.geometry.Point_> java.lang.String toString(KdTree<X> t)

toList

public static <X extends Jcg.geometry.Point_> java.util.ArrayList<Jcg.geometry.Point_d> toList(KdTree<X> t,
                                                                               java.util.ArrayList<Jcg.geometry.Point_d> list)