dD Spatial Searching
Reference Manual

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.

61.5   Classified 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>
CGAL::Search_traits_adapter<Key,PointPropertyMap,BaseTraits>

Distance Classes

CGAL::Euclidean_distance<Traits>
CGAL::Euclidean_distance_sphere_point<Traits>
CGAL::Manhattan_distance_iso_box_point<Traits>
CGAL::Weighted_Minkowski_distance<Traits>
CGAL::Distance_for_point_adapter<Key,PointPropertyMap,Base_distance>

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>

Advanced Classes

CGAL::Kd_tree_node<Traits, Splitter, UseExtendedNode>
CGAL::Kd_tree_rectangle<FT>
CGAL::Plane_separator<FT>
CGAL::Point_container<Traits>

Concepts

FuzzyQueryItem
GeneralDistance
OrthogonalDistance
SearchTraits
RangeSearchTraits
SpatialSeparator
SpatialTree
Splitter

61.6   Alphabetical List of Reference Pages

s