\( \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.4 - Inscribed Areas
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Largest_empty_iso_rectangle_2< T > Class Template Reference

#include <CGAL/Largest_empty_iso_rectangle_2.h>

Definition

Given a set of points in the plane, the class Largest_empty_iso_rectangle_2 is a data structure that maintains an iso-rectangle with the largest area among all iso-rectangles that are inside a given bounding box( iso-rectangle), and that do not contain any point of the point set.

Template Parameters
Tmust be a model of the concept LargestEmptyIsoRectangleTraits_2.

Implementation

The algorithm is an implementation of [2]. The runtime of an insertion or a removal is \( O(\log n)\). A query takes \( O(n^2)\) worst case time and \( O(n \log n)\) expected time. The working storage is \( O(n)\).

Types

typedef Traits::Point_2 Point_2
 
typedef Traits::Iso_rectangle_2 Iso_rectangle_2
 
typedef unspecified_type const_iterator
 Iterator over the points. More...
 

Creation

 Largest_empty_iso_rectangle_2 (const Iso_rectangle_2 &b)
 Constructor. More...
 
 Largest_empty_iso_rectangle_2 (const Point_2 p, const Point_2 q)
 Constructor. More...
 
 Largest_empty_iso_rectangle_2 ()
 Constructor. More...
 
 Largest_empty_iso_rectangle_2 (const Largest_empty_iso_rectangle_2< Traits > tr)
 Copy constructor.
 

Assignment

Largest_empty_iso_rectangle_2< T > operator= (const Largest_empty_iso_rectangle_2< T > &tr)
 

Access Functions

const Traits & traits () const
 Returns a const reference to the traits object.
 
const_iterator begin () const
 Returns an iterator to the beginning of the point set.
 
const_iterator end () const
 Returns a past-the-end iterator for the point set.
 

Queries

Quadruple< Point_2, Point_2,
Point_2, Point_2
get_left_bottom_right_top ()
 Returns the four points that define the largest empty iso-rectangle. More...
 
Iso_rectangle_2 get_largest_empty_iso_rectangle ()
 Returns the largest empty iso-rectangle. More...
 
Iso_rectangle_2 get_bounding_box ()
 Returns the iso-rectangle passed in the constructor.
 

Insertion

void insert (const Point_2 &p)
 Inserts point p in the point set, if it is not already in the set.
 
void push_back (const Point_2 &p)
 Inserts point p in the point set, if it is not already in the set.
 
template<class InputIterator >
int insert (InputIterator first, InputIterator last)
 Inserts the points in the range [first, last), and returns the number of inserted points. More...
 

Removal

bool remove (const Point_2 &p)
 Removes point p. More...
 
void clear ()
 Removes all points.
 

Member Typedef Documentation

Iterator over the points.

This iterator allows to enumerate the points. It is non mutable, bidirectional and its value type is Point_2. It is invalidated by any insertion or removal of a point.

Constructor & Destructor Documentation

Constructor.

The iso-rectangle b is the bounding rectangle.

template<typename T >
CGAL::Largest_empty_iso_rectangle_2< T >::Largest_empty_iso_rectangle_2 ( const Point_2  p,
const Point_2  q 
)

Constructor.

The iso-rectangle whose lower left and upper right points are p and q respectively is the bounding rectangle.

Constructor.

The iso-rectangle whose lower left point and upper right points are (0,0) and (1,1) respectively is the bounding rectangle.

Member Function Documentation

template<typename T >
Iso_rectangle_2 CGAL::Largest_empty_iso_rectangle_2< T >::get_largest_empty_iso_rectangle ( )

Returns the largest empty iso-rectangle.

(Note that the two points defining the iso-rectangle are not necessarily part of the point set.)

template<typename T >
Quadruple<Point_2, Point_2, Point_2, Point_2> CGAL::Largest_empty_iso_rectangle_2< T >::get_left_bottom_right_top ( )

Returns the four points that define the largest empty iso-rectangle.

(Note that these points are not necessarily on a corner of an iso-rectangle.)

template<typename T >
template<class InputIterator >
int CGAL::Largest_empty_iso_rectangle_2< T >::insert ( InputIterator  first,
InputIterator  last 
)

Inserts the points in the range [first, last), and returns the number of inserted points.

Template Parameters
InputIteratormust be an iterator with value type Point_2.
template<typename T >
bool CGAL::Largest_empty_iso_rectangle_2< T >::remove ( const Point_2 p)

Removes point p.

Returns false iff p is not in the point set.