Spatial Sorting

*Christophe Delage*

63.1 | Introduction | ||||

63.2 | Spatial Sorting |

Many geometric algorithms implemented in CGAL are incremental, and thus their speed is dependent on the order of insertion. This package provides sorting algorithms that may considerably improve running times of such algorithms.

The rationale is to sort objects along a space-filling curve so that two objects close geometrically will be close in the insertion order with high probability. That way, parts of a data structure that will be looked at during an insertion will probably have been looked at in a recent insertion, and thus probably will be in cache memory instead of main memory.

As another side-effect, these sorting functions usually improve memory locality of the data structures produced by incremental algorithms, sometimes leading to speed ups in other algorithm using these data structures.

CGAL provides a small set of sorting algorithms, currently implemented only for 2D and 3D points, although it is easy to extend them to other objects through a traits mechanism.

Given an iterator range of points, the function *hilbert_sort* sorts them
along the space-filling Hilbert curve.
Combined with a *std::random_shuffle*, the function *spatial_sort* will
sort points in a way keeping enough randomness to retain theoretical optimality
for some algorithms^{1},
and close enough to a space-filling curve to speed-up algorithms.

The 2D and 3D triangulation classes of CGAL internally sort points as described
above, when the points are passed as an iterator range to a constructor or the
*insert* method.

^{1} | in fact, this has only been proved for Delaunay triangulation |