Class FastRangeSearch<X extends Jcg.geometry.Point_>

java.lang.Object

FastRangeSearch<X>

All Implemented Interfaces:

RangeSearch<X>

public class FastRangeSearch<X extends Jcg.geometry.Point_>
extends java.lang.Object
implements RangeSearch<X>

Class providing fast range search (using Kd-trees)

Version:

jan 2014

Author:

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

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static long	basicQueryTime
(package private) static long	constructionTime
private KdTree<X>	kdTree
(package private) static long	queryTime

Constructor Summary

Constructors

Constructor and Description
FastRangeSearch(PointCloud N) Construct the data structure for range search

Method Summary

Methods

Modifier and Type	Method and Description
PointCloud	NN(X q, double sqRad) Main search procedure (for Range search queries)
PointCloud	OrthogonalRangeSearch(X q, double sqRad) Perform range search using KdTrees
static void	timePerformance()

Methods inherited from class java.lang.Object

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

Field Detail

kdTree

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

queryTime

static long queryTime

constructionTime

static long constructionTime

basicQueryTime

static long basicQueryTime

Constructor Detail

FastRangeSearch

public FastRangeSearch(PointCloud N)

Construct the data structure for range search

Parameters:

PointCloud - the input points

Method Detail

timePerformance

public static void timePerformance()

NN

public PointCloud NN(X q,
            double sqRad)

Main search procedure (for Range search queries)

OrthogonalRangeSearch

public PointCloud OrthogonalRangeSearch(X q,
                               double sqRad)

Perform range search using KdTrees

Specified by:

OrthogonalRangeSearch in interface RangeSearch<X extends Jcg.geometry.Point_>

Parameters:

q - the query point

sqRad - the (squared) radius of the Euclidean ball

Returns:

PointCloud the points in the range (epsilon close to q)