math.geom2d.point
Class KDTree2D

Package class diagram package KDTree2D
java.lang.Object
  extended by math.geom2d.point.KDTree2D

public class KDTree2D
extends 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(ArrayList<Point2D> points)
           
 
Method Summary
 void add(Point2D point)
           
 boolean contains(Point2D value)
           
 KDTree2D.Node getNode(Point2D point)
           
 KDTree2D.Node getRoot()
           
static void main(String[] args)
          Gives a small example of use.
 Point2D nearestNeighbor(Point2D point)
           
 Collection<Point2D> rangeSearch(Box2D range)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

KDTree2D

public KDTree2D(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 Collection<Point2D> rangeSearch(Box2D range)

nearestNeighbor

public Point2D nearestNeighbor(Point2D point)

main

public static void main(String[] args)
Gives a small example of use.



Copyright © 2012 AMIS research group, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic. All Rights Reserved.