math.geom2d.point
Class KDTree2D

java.lang.Object
  math.geom2d.point.KDTree2D

public class KDTree2D
extends java.lang.Object

A data structure for storing a great number of points. During construction of the tree, median point in current coordinate is chosen for each step, ensuring the final tree is balanced. The cost for retrieving a point is O(log n).
The cost for building the tree is O(n log^2 n), that can take some time for large points sets.
This implementation is semi-dynamic: points can be added, but can not be removed.

Author:

dlegland

Nested Class Summary

class

KDTree2D.Node

Constructor Summary

KDTree2D(java.util.ArrayList<Point2D> points)

Method Summary

void	add(Point2D point)
boolean	contains(Point2D value)
KDTree2D.Node	getNode(Point2D point)
KDTree2D.Node	getRoot()
static void	main(java.lang.String[] args) Gives a small example of use.
Point2D	nearestNeighbor(Point2D point)
java.util.Collection<Point2D>	rangeSearch(Box2D range)

Methods inherited from class java.lang.Object

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

Constructor Detail

KDTree2D

public KDTree2D(java.util.ArrayList<Point2D> points)

Method Detail

getRoot

public KDTree2D.Node getRoot()

contains

public boolean contains(Point2D value)

getNode

public KDTree2D.Node getNode(Point2D point)

add

public void add(Point2D point)

rangeSearch

public java.util.Collection<Point2D> rangeSearch(Box2D range)

nearestNeighbor

public Point2D nearestNeighbor(Point2D point)

main

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

Gives a small example of use.