\( \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
CGAL::Point_container< Traits > Class Template Reference

#include <CGAL/Point_container.h>

Definition

A custom container for points used to build a tree.

Each point container holds the points from a rectangle associated with a node of the tree. In the remainder of this reference page this rectangle is called the associated rectangle. Provides a method to split a container and a number of methods to support the implementation of splitting rules.

Template Parameters
Traitsmust be model of the concept SearchTraits, for example Simple_cartesian<double>.
See Also
SearchTraits
SpatialSeparator

Related Functions

(Note that these are not member functions.)

template<class Traits >
std::ostream & operator<< (std::ostream &s, Point_container< Traits > c)
 Prints the point container c to the output stream s and returns s.
 

Types

typedef Traits::FT FT
 Number type.
 
typedef Traits::Point_d Point_d
 Point type.
 
typedef unspecified_type iterator
 An iterator with value type Point_d*.
 
typedef unspecified_type const_iterator
 A const iterator with value type const Point_d*.
 

Creation

 Point_container (int d)
 Construct an empty container for storing d-dimensional points.
 
template<class InputIterator >
 Point_container (int d, InputIterator begin, InputIterator end)
 Construct the container of d-dimensional points of type Point_d given by the iterator sequence [begin, end).
 

Operations

template<class SpatialSeparator >
void split (Point_container< Traits > &c2, SpatialSeparator sep, bool sliding=false)
 Given an empty container c2 with the same dimension as c, splits c into cand c2 using the separator sep. More...
 
void swap (Point_container< Traits > &c2)
 Swap the contents of c and c2
 
void recompute_tight_bounding_box ()
 Recompute the bounding box of the points in the container.
 
iterator begin ()
 Returns an iterator to a pointer to the first point.
 
iterator end ()
 Returns the appropriate past-the-end iterator.
 
const_iterator begin () const
 Returns a const iterator to a pointer to the first point.
 
const_iterator end () const
 Returns the appropriate past-the-end const iterator.
 
int dimension () const
 Returns the dimension.
 
int built_coordinate () const
 Returns coordinate for which the pointer list is built.
 
int max_span_coord () const
 Returns coordinate where the associated rectangle has maximal span.
 
int max_tight_span_coord () const
 Returns coordinate where the point coordinates have maximal span.
 
FT max_span_lower () const
 Returns lower value of the interval corresponding to max_span_coord().
 
FT max_tight_span_lower () const
 Returns lower value of the interval corresponding to max_tight_span_coord(). More...
 
FT max_span_upper () const
 Returns upper value of the interval corresponding to max_span_coord().
 
FT max_span_upper_without_dim (int d) const
 Returns upper value of the interval over all dimensions without taking dimension d into account.
 
FT max_tight_span_upper () const
 Returns upper value of the interval corresponding to max_tight_span_coord().
 
FT max_spread () const
 Returns the size of the interval corresponding to max_span_coord().
 
FT max_tight_spread () const
 Returns the size of the interval corresponding to max_tight_span_coord().
 
FT median (int split_coord) const
 Returns the median value of the points stored in the container for dimension split_coord.
 
const Kd_tree_rectangle< Traits > & bounding_box () const
 Returns the associated rectangle.
 
const Kd_tree_rectangle< Traits > & tight_bounding_box ()
 Returns the bounding box of the items in associated rectangle.
 
int max_tight_span_coord_balanced (FT aspect_ratio) const
 Returns the dimension with the maximal point spread, for which after fair splitting the ratio of the length of the longest side and the smallest side of the bounding box of the items in associated rectangle, does not exceed aspect_ratio.
 
FT balanced_fair (int d, FT aspect_ratio)
 Returns the splitting value for fair splitting.
 
FT balanced_sliding_fair (int d, FT aspect_ratio)
 Returns the splitting value for sliding fair splitting.
 
std::size_t size () const
 Returns the number of points stored.
 
bool empty () const
 Returns true if no points are present, false otherwise.
 

Member Function Documentation

template<typename Traits >
FT CGAL::Point_container< Traits >::max_tight_span_lower ( ) const

Returns lower value of the interval corresponding to max_tight_span_coord().

That is, the smallest max_tight_span_coord()-th coordinate of the points in c.

template<typename Traits >
template<class SpatialSeparator >
void CGAL::Point_container< Traits >::split ( Point_container< Traits > &  c2,
SpatialSeparator  sep,
bool  sliding = false 
)

Given an empty container c2 with the same dimension as c, splits c into cand c2 using the separator sep.

If sliding is true after splitting each container contains at least one point. Container c should contain at least two points.