CGAL 6.1.1 - Inscribed Areas

Loading...
Searching...
No Matches
List of all members
CGAL::Largest_empty_iso_rectangle_2< T > Class Template Reference
Reference Manual

`#include <CGAL/Largest_empty_iso_rectangle_2.h>`

## Definition

template<typename T>
class CGAL::Largest_empty_iso_rectangle_2< T >

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

  T | must 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.

## Creation
| Largest_empty_iso_rectangle_2 (const Iso_rectangle_2 &b)
| Constructor.
| Largest_empty_iso_rectangle_2 (const Point_2 p, const Point_2 q)
| Constructor.
| Largest_empty_iso_rectangle_2 ()
| Constructor.
| 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.
Iso_rectangle_2 | get_largest_empty_iso_rectangle ()
| Returns the largest empty iso-rectangle.
Iso_rectangle_2 | get_bounding_box ()
| Returns the iso-rectangle passed in the constructor.

## Insertion
bool | insert (const Point_2 &p)
| Inserts point `p` in the point set, if it is not already in the set and on the bounded side of the bounding rectangle.
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.

## Removal
bool | remove (const Point_2 &p)
| Removes point `p`.
void | clear ()
| Removes all points.

## Member Typedef Documentation

## ◆ const_iterator

template<typename T >

typedef unspecified_type CGAL::Largest_empty_iso_rectangle_2< T >::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]

template<typename T >

CGAL::Largest_empty_iso_rectangle_2< T >::Largest_empty_iso_rectangle_2 | ( | const Iso_rectangle_2 & | b | ) |

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]

template<typename T >

CGAL::Largest_empty_iso_rectangle_2< T >::Largest_empty_iso_rectangle_2 | ( |  | ) |

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() [1/2]

template<typename T >

bool CGAL::Largest_empty_iso_rectangle_2< T >::insert | ( | const Point_2 & | p | ) |

Inserts point `p` in the point set, if it is not already in the set and on the bounded side of the bounding rectangle.

Note
  Points on the boundary can be ignored as they lead to the same result.

## ◆ insert() [2/2]

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

  InputIterator | must 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.