\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.13 - Spatial Sorting
Functions
Functions
Spatial Sorting Reference

Functions

template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::hilbert_sort (RandomAccessIterator begin, RandomAccessIterator end, const Traits &traits=Default_traits, PolicyTag policy=Default_policy)
 The function hilbert_sort() sorts an iterator range of points along a Hilbert curve. More...
 
template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::hilbert_sort_on_sphere (RandomAccessIterator begin, RandomAccessIterator end, const Traits &traits=Default_traits, PolicyTag policy=Default_policy, double sqr_radius=1.0, const Traits::Point_3 &center=Default_center)
 The function hilbert_sort_on_sphere() sorts an iterator range of points that are supposed to be close to a given sphere along a Hilbert curve on that same sphere. More...
 
template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Traits &traits=Default_traits, PolicyTag policy=Default_policy, std::ptrdiff_t threshold_hilbert=default, std::ptrdiff_t threshold_multiscale=default, double ratio=default)
 The function spatial_sort() sorts an iterator range of points in a way that improves space locality. More...
 
template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::spatial_sort_on_sphere (RandomAccessIterator begin, RandomAccessIterator end, const Traits &traits=Default_traits, PolicyTag policy=Default_policy, double sqr_radius=1.0, const Traits::Point_3 &center=Default_center, std::ptrdiff_t threshold_hilbert=default, std::ptrdiff_t threshold_multiscale=default, double ratio=default)
 The function spatial_sort_on_sphere() sorts an iterator range of points in a way that improves space locality with respect to the intrinsic metric on the sphere given as input. More...
 

Function Documentation

◆ hilbert_sort()

template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::hilbert_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const Traits &  traits = Default_traits,
PolicyTag  policy = Default_policy 
)

#include <CGAL/hilbert_sort.h>

The function hilbert_sort() sorts an iterator range of points along a Hilbert curve.

It sorts the range [begin, end) in place.

The default traits class Default_traits is the kernel in which the type std::iterator_traits<RandomAccessIterator>::value_type is defined. The default policy is Hilbert_sort_median_policy() and the other option is Hilbert_sort_middle_policy().

Requirements

  1. std::iterator_traits<RandomAccessIterator>::value_type is convertible to Traits::Point_2, Traits::Point_3, or Traits::Point_d.
  2. Traits is a model for concept SpatialSortingTraits_2, SpatialSortingTraits_3, or SpatialSortingTraits_d.

Implementation

Creates an instance of Hilbert_sort_2<Traits, PolicyTag>, Hilbert_sort_3<Traits, PolicyTag>, or Hilbert_sort_d<Traits, PolicyTag> and calls its operator().

Examples:
Spatial_sorting/hilbert.cpp, Spatial_sorting/hilbert_policies.cpp, and Spatial_sorting/small_example_delaunay_2.cpp.

◆ hilbert_sort_on_sphere()

template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::hilbert_sort_on_sphere ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const Traits &  traits = Default_traits,
PolicyTag  policy = Default_policy,
double  sqr_radius = 1.0,
const Traits::Point_3 &  center = Default_center 
)

#include <CGAL/hilbert_sort_on_sphere.h>

The function hilbert_sort_on_sphere() sorts an iterator range of points that are supposed to be close to a given sphere along a Hilbert curve on that same sphere.

If input points are not close to the input sphere, this function still works, but it might not be a good sorting function.

It sorts the range [begin, end) in place.

The default traits class Default_traits is the kernel in which the type std::iterator_traits<RandomAccessIterator>::value_type is defined. The default policy is Hilbert_sort_median_policy() and the other option is Hilbert_sort_middle_policy().

The input sphere is given by a squared radius and a center, parameter sqr_radius and parameter center respectively. The default squared radius of the sphere is 1.0. The default center of the sphere is the origin (0,0,0).

Requirements

  1. std::iterator_traits<RandomAccessIterator>::value_type is convertible to Traits::Point_3.
  2. Traits is a model for concept SpatialSortingTraits_3.

Precondition

  1. sqr_radius greater than 0.

Implementation

Creates an instance of Hilbert_sort_on_sphere<Traits, PolicyTag>, and calls its operator().

Examples:
Spatial_sorting/hilbert_sort_on_sphere.cpp.

◆ spatial_sort()

template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::spatial_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const Traits &  traits = Default_traits,
PolicyTag  policy = Default_policy,
std::ptrdiff_t  threshold_hilbert = default,
std::ptrdiff_t  threshold_multiscale = default,
double  ratio = default 
)

#include <CGAL/spatial_sort.h>

The function spatial_sort() sorts an iterator range of points in a way that improves space locality.

Two points close in the order will be close geometrically, and two points close geometrically will have a high probability of being close in the order.

It sorts the range [begin, end) in place.

The default traits class Default_traits is the kernel in which the type std::iterator_traits<RandomAccessIterator>::value_type is defined.

The default policy is Hilbert_sort_median_policy() and the other option is Hilbert_sort_middle_policy().

The default values for the thresholds and the ratio depend on the dimension.

Requirements

  1. std::iterator_traits<RandomAccessIterator>::value_type is convertible to Traits::Point_2, Traits::Point_3, or Traits::Point_d.
  2. Traits is a model for concept SpatialSortingTraits_2, SpatialSortingTraits_3, or SpatialSortingTraits_d.

Implementation

Creates an instance of Multiscale_sort<Hilbert_sort> where Hilbert_sort is an Hilbert sorting object, and calls its operator().

The threshold_hilbert is the minimal size of a point set to be subdivided recursively during Hilbert sorting, otherwise random order is used. The threshold_multiscale value is the minimal size for a sample to call Hilbert sort, otherwise random order is used. The ratio value is used to split the original set in two subsets, spatial sort is applied on the first subset of size ratio times the original size of the set, Hilbert sort is applied on the second subset.

Examples:
Spatial_sorting/myPoint.cpp, Spatial_sorting/small_example_delaunay_2.cpp, Spatial_sorting/sp_sort_using_property_map_2.cpp, Spatial_sorting/sp_sort_using_property_map_3.cpp, and Spatial_sorting/sp_sort_using_property_map_d.cpp.

◆ spatial_sort_on_sphere()

template<class RandomAccessIterator , class Traits , class PolicyTag >
void CGAL::spatial_sort_on_sphere ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const Traits &  traits = Default_traits,
PolicyTag  policy = Default_policy,
double  sqr_radius = 1.0,
const Traits::Point_3 &  center = Default_center,
std::ptrdiff_t  threshold_hilbert = default,
std::ptrdiff_t  threshold_multiscale = default,
double  ratio = default 
)

#include <CGAL/spatial_sort_on_sphere.h>

The function spatial_sort_on_sphere() sorts an iterator range of points in a way that improves space locality with respect to the intrinsic metric on the sphere given as input.

Two points close in the order will be close on the sphere, and two points close on the sphere will have a high probability of being close in the order. The input points are supposed to be close to the input sphere. If input points are not close to the input sphere, this function still works, but it might not be a good sorting function.

It sorts the range [begin, end) in place.

The default traits class Default_traits is the kernel in which the type std::iterator_traits<RandomAccessIterator>::value_type is defined.

The default policy is Hilbert_sort_median_policy() and the other option is Hilbert_sort_middle_policy().

The input sphere is given by a squared radius and a center, parameter sqr_radius and parameter center respectively. The default squared radius of the sphere is 1.0. The default center of the sphere is the origin (0,0,0).

Requirements

  1. std::iterator_traits<RandomAccessIterator>::value_type is convertible to Traits::Point_3.
  2. Traits is a model for concept SpatialSortingTraits_3.

Precondition

  1. sqr_radius greater than 0.

Implementation

Creates an instance of Multiscale_sort<Hilbert_sort_on_sphere_3> where Hilbert_sort_on_sphere_3 is an Hilbert sorting on the sphere object, and calls its operator().

The threshold_hilbert is the minimal size of a point set to be subdivided recursively during Hilbert sorting, otherwise random order is used. The threshold_multiscale value is the minimal size for a sample to call the Hilbert_sort_on_sphere_3 functor, otherwise random order is used. The ratio value is used to split the original set in two subsets, spatial sort is applied on the first subset of size ratio times the original size of the set, Hilbert_sort_on_sphere_3 functor is applied on the second subset.

Examples:
Spatial_sorting/spatial_sort_on_sphere.cpp.