Chapter 63
Spatial Sorting

Christophe Delage

Table of Contents

63.1   Introduction

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.

63.2   Spatial Sorting

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¹, 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.

Footnotes