dD Spatial Searching Reference

Hans Tangelder and Andreas Fabri

This package implements exact and approximate distance browsing by providing exact and approximate algorithms for range searching, k-nearest and k-furthest neighbor searching, as well as incremental nearest and incremental furthest neighbor searching, where the query items are points in dD Euclidean space.

Introduced in: CGAL 3.0
BibTeX: cgal:tf-ssd-24b
License: GPL
Windows Demo: 2D Spatial Searching

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.

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_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_leaf_node<Traits, Splitter, UseExtendedNode>
• CGAL::Kd_tree_internal_node<Traits, Splitter, UseExtendedNode>
• CGAL::Kd_tree_rectangle<FT,Dimension>
• CGAL::Plane_separator<FT>
• CGAL::Point_container<Traits>

Concepts

• FuzzyQueryItem
• GeneralDistance
• OrthogonalDistance
• SearchTraits
• SearchGeomTraits_3
• SearchGeomTraits_2
• RangeSearchTraits
• SpatialSeparator
• SpatialTree
• Splitter

Modules
	Concepts
	Search Classes
	Range Query Item Classes
	Search Traits Classes
	Distance Classes
	Splitter Classes
	Advanced Classes