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.

35.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>

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>

Advanced Classes

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

Concepts

FuzzyQueryItem
GeneralDistance
OrthogonalDistance
SearchTraits
SpatialSeparator
SpatialTree

35.6   Alphabetical List of Reference Pages

Euclidean_distance<Traits>

Euclidean_distance_sphere_point<Traits>

Fair<Traits, SpatialSeparator>

FuzzyQueryItem

Fuzzy_iso_box<Traits>

Fuzzy_sphere<Traits>

GeneralDistance

Incremental_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>

Kd_tree<Traits, Splitter, UseExtendedNode>

Kd_tree_node<Traits, Splitter, UseExtendedNode>

Kd_tree_rectangle<Traits>

K_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>

Manhattan_distance_iso_box_point<Traits>

Median_of_max_spread<Traits, SpatialSeparator>

Median_of_rectangle<Traits, SpatialSeparator>

Midpoint_of_max_spread<Traits, SpatialSeparator>

Midpoint_of_rectangle<Traits, SpatialSeparator>

OrthogonalDistance

Orthogonal_incremental_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>

Orthogonal_k_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>

Plane_separator<FT>

SearchTraits

Search_traits<NT,Point,CartesianIterator,ConstructCartesianIterator,ConstructMinVertex,ConstructMaxVertex>

Search_traits_2<Kernel>

Search_traits_3<Kernel>

Search_traits_d<Kernel>

Sliding_fair<Traits, SpatialSeparator>

Sliding_midpoint<Traits, SpatialSeparator>

SpatialSeparator

SpatialTree

Splitter

Weighted_Minkowski_distance<Traits>