CGAL 6.1 - dD Spatial Searching

Loading...
Searching...
No Matches
List of all members
CGAL::Sliding_fair< Traits, SpatialSeparator > Class Template Reference
Reference Manual » Splitter Classes

`#include <CGAL/Splitters.h>`

## Definition

template<typename Traits, typename SpatialSeparator>
class CGAL::Sliding_fair< Traits, SpatialSeparator >

Implements the sliding fair splitting rule.

This splitting rule is a compromise between the `Fair` splitting rule and the `Sliding_midpoint` rule. Sliding fair-split is based on the theory that there are two types of splits that are good: balanced splits that produce fat rectangles, and unbalanced splits provided the rectangle with fewer points is fat.

Also, this splitting rule maintains an upper bound on the maximal allowed ratio of the longest and shortest side of a rectangle (the value of this upper bound is set in the constructor of the fair splitting rule). Among the splits that satisfy this bound, it selects the one one in which the points have the largest spread. It then considers the most extreme cuts that would be allowed by the aspect ratio bound. This is done by dividing the longest side of the rectangle by the aspect ratio bound. If the median cut lies between these extreme cuts, then we use the median cut. If not, then consider the extreme cut that is closer to the median. If all the points lie to one side of this cut, then we slide the cut until it hits the first point. This may violate the aspect ratio bound, but will never generate empty cells.

Parameters

Expects for the first template argument a model of the concept `SearchTraits`, for example `CGAL::Cartesian_d<double>`.

Expects for the second template argument a model of the concept `SpatialSeparator`. It has as default value the type, `CGAL::Plane_separator<Traits::FT>`

Is model of
  `Splitter`

See also
  `Splitter`
  `SpatialSeparator`

## Types
typedef Traits::FT | FT
| Number type.

## Creation
| Sliding_fair (unsigned int bucket_size, FT aspect_ratio=FT(3))
| Constructor.

## Operations
FT | aspect_ratio ()
| Returns the maximal ratio between the largest and smallest side of a cell allowed for fair splitting.
unsigned int | bucket_size ()
| Returns the bucket size of the leaf nodes.