CGAL 6.1 - Spatial Sorting

Loading...
Searching...
No Matches
Functions
Functions
Reference Manual

##

## Functions
template<class ConcurrencyTag = Sequential_tag, class InputPointIterator , class Traits , class PolicyTag >
void | CGAL::hilbert_sort (InputPointIterator begin, InputPointIterator end, const Traits &traits=Default_traits, PolicyTag policy=Default_policy)
| The function `hilbert_sort()` sorts an iterator range of points along a Hilbert curve.
template<class InputPointIterator , class Traits , class PolicyTag >
void | CGAL::hilbert_sort_on_sphere (InputPointIterator begin, InputPointIterator 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.
template<class ConcurrencyTag = Sequential_tag, class InputPointIterator , class Traits , class PolicyTag >
void | CGAL::spatial_sort (InputPointIterator begin, InputPointIterator 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.
template<class InputPointIterator , class Traits , class PolicyTag >
void | CGAL::spatial_sort_on_sphere (InputPointIterator begin, InputPointIterator 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.

## Function Documentation

## ◆ hilbert_sort()

template<class ConcurrencyTag = Sequential_tag, class InputPointIterator , class Traits , class PolicyTag >

void CGAL::hilbert_sort | ( | InputPointIterator | begin,
|  | InputPointIterator | 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.

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`. With parallelism enabled, sorting will be performed using up to four threads in 2D, and up to eight threads in 3D. Parallel sorting is available only when the median strategy policy (the default policy) is used.
  InputPointIterator | must be a model of `RandomAccessIterator` and `std::iterator_traits<InputPointIterator>::value_type` must be convertible to `Traits::Point_2`, `Traits::Point_3`, or `Traits::Point_d`.
  Traits | must be a model for concept `SpatialSortingTraits_2`, `SpatialSortingTraits_3`, or `SpatialSortingTraits_d`. The default traits class `Default_traits` is the kernel in which the type `std::iterator_traits<InputPointIterator>::value_type` is defined.
  PolicyTag | is used to specify the strategy policy. Possible values are `Hilbert_sort_median_policy` (the default policy) or `Hilbert_sort_middle_policy` .

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 InputPointIterator , class Traits , class PolicyTag >

void CGAL::hilbert_sort_on_sphere | ( | InputPointIterator | begin,
|  | InputPointIterator | 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.

Template Parameters

  InputPointIterator | must be a model of `RandomAccessIterator` and `std::iterator_traits<InputPointIterator>::value_type` must be convertible to `Traits::Point_3`.
  Traits | must be a model for concept `SpatialSortingTraits_3`. The default traits class `Default_traits` is the kernel in which the type `std::iterator_traits<InputPointIterator>::value_type` is defined.
  PolicyTag | is used to specify the strategy policy. Possible values are `Hilbert_sort_median_policy` (the default policy) or `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).

Precondition
  `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 ConcurrencyTag = Sequential_tag, class InputPointIterator , class Traits , class PolicyTag >

void CGAL::spatial_sort | ( | InputPointIterator | begin,
|  | InputPointIterator | 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.

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`. With parallelism enabled, sorting will be performed using up to four threads in 2D, and up to eight threads in 3D. Parallel sorting is available only when the median strategy policy (the default policy) is used.
  InputPointIterator | must be a model of `RandomAccessIterator` and `std::iterator_traits<InputPointIterator>::value_type` must be convertible to `Traits::Point_2`, `Traits::Point_3`, or `Traits::Point_d`.
  Traits | must be a model for concept `SpatialSortingTraits_2`, `SpatialSortingTraits_3`, or `SpatialSortingTraits_d`. The default traits class `Default_traits` is the kernel in which the type `std::iterator_traits<InputPointIterator>::value_type` is defined.
  PolicyTag | is used to specify the strategy policy. Possible values are `Hilbert_sort_median_policy` (the default policy) or `Hilbert_sort_middle_policy` .

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

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/parallel_spatial_sort_3.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 InputPointIterator , class Traits , class PolicyTag >

void CGAL::spatial_sort_on_sphere | ( | InputPointIterator | begin,
|  | InputPointIterator | 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 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).

Template Parameters

  InputPointIterator | must be a model of `RandomAccessIterator` and `std::iterator_traits<InputPointIterator>::value_type` must be convertible to `Traits::Point_3`.
  Traits | must be a model for concept `SpatialSortingTraits_3`. The default traits class `Default_traits` is the kernel in which the type `std::iterator_traits<InputPointIterator>::value_type` is defined.
  PolicyTag | is used to specify the strategy policy. Possible values are `Hilbert_sort_median_policy` (the default policy) or `Hilbert_sort_middle_policy` .

Precondition
  `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.