Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Chapter 62
Spatial Searching

Hans Tangelder and Andreas Fabri
This package provides data structures and algorithms for exact and approximate distance browsing, supporting

both nearest and furthest neighbor searching,
both exact and approximate searching,
(approximate) range searching,
(approximate) k-nearest and k-furthest neighbor searching,
(approximate) incremental nearest and incremental furthest neighbor searching,
query items representing points and spatial objects.

The spatial searching package consists of the following concepts and classes that are described in the reference pages.

Search Classes

CGAL::K_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>
CGAL::Incremental_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>
CGAL::Orthogonal_incremental_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>
CGAL::Orthogonal_k_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>
CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

Range Query Item Classes

CGAL::Fuzzy_iso_box<Traits>
CGAL::Fuzzy_sphere<Traits>

Search Traits Classes

CGAL::Search_traits_2<Kernel>
CGAL::Search_traits_3<Kernel>
CGAL::Search_traits_d<Kernel>
CGAL::Search_traits<NT,Point,CartesianIterator,ConstructCartesianIterator,ConstructMinVertex,ConstructMaxVertex>

Distance Classes

CGAL::Euclidean_distance<Traits>
CGAL::Euclidean_distance_sphere_point<Traits>
CGAL::Manhattan_distance_iso_box_point<Traits>
CGAL::Weighted_Minkowski_distance<Traits>

Splitter Classes

CGAL::Sliding_midpoint<Traits, SpatialSeparator>
CGAL::Sliding_fair<Traits, SpatialSeparator>
CGAL::Fair<Traits, SpatialSeparator>
CGAL::Median_of_max_spread<Traits, SpatialSeparator>
CGAL::Median_of_rectangle<Traits, SpatialSeparator>
CGAL::Midpoint_of_max_spread<Traits, SpatialSeparator>
CGAL::Midpoint_of_rectangle<Traits, SpatialSeparator>