## SpatialTree

### Definition

The concept SpatialTree defines the requirements for a tree supporting both neighbor searching and approximate range searching.

### Types

SpatialTree::SearchTraits
| Search traits.
SpatialTree::Point_d
| Point type.
SpatialTree::iterator;
| Bidirectional iterator with value type Point_d that allows to enumerate all points in the tree.
SpatialTree::Node_handle;
| Node handle.
SpatialTree::Point_d_iterator;
| Iterator with value type Point_d*.
SpatialTree::Splitter
| Splitter.
SpatialTree::Distance
| Distance.

### Creation

template <class InputIterator>

SpatialTree tree ( | InputIterator first, InputIterator beyond, SearchTraits t);

| Constructs a tree on the elements from the sequence [first,beyond).

### Operations

template <class OutputIterator, class FuzzyQueryItem>
OutputIterator | tree.search ( OutputIterator it, FuzzyQueryItem q)
|  | Reports the points that are approximately contained by q. The value type of OutputIterator must be Point_d.
iterator | tree.begin () | Returns an iterator to the first point in the tree.
iterator | tree.end () | Returns the corresponding past-the-end iterator.
Node_handle | tree.root () | Returns a handle to the root node of the tree.
Kd_tree_rectangle<SearchTraits>
| tree.bounding_box ()
|  | returns a const reference to the bounding box of the root node of the tree.
unsigned int | tree.size () | Returns the number of items that are stored in the tree.

### Has Models

CGAL::Kd_tree<Traits,Splitter,UseExtendedNode>.