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.

#include <CGAL/spatial_sort.h>

template <class RandomAccessIterator, class Traits>
spatial_sort ( RandomAccessIterator begin,
RandomAccessIterator end,
Traits traits = Default_traits)
sorts the range [begin,end) in place.

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


  1. RandomAccessIterator::value_type is convertible to Traits::Point_2 or Traits::Point_3.
  2. Traits is a model for concept SpatialSortingTraits_2 or SpatialSortingTraits_3.


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