\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - dD Spatial Searching
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Sliding_fair< Traits, SpatialSeparator > Class Template Reference
Splitter Classes

#include <CGAL/Splitters.h>

Definition

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.