\( \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.12.1 - Inscribed Areas
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_2get_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

◆ const_iterator

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

◆ Largest_empty_iso_rectangle_2() [1/3]

Constructor.

The iso-rectangle b is the bounding rectangle.

◆ Largest_empty_iso_rectangle_2() [2/3]

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.

◆ Largest_empty_iso_rectangle_2() [3/3]

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

◆ get_largest_empty_iso_rectangle()

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.)

◆ get_left_bottom_right_top()

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.)

◆ insert()

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.

◆ remove()

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.