CGAL 5.5.2  dD Spatial Searching

#include <CGAL/Splitters.h>
Implements the sliding fair splitting rule.
This splitting rule is a compromise between the Fair
splitting rule and the Sliding_midpoint
rule. Sliding fairsplit 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>
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.  