Navigation: Up, Table of Contents, Bibliography, Index, Title Page

CGAL::Largest_empty_iso_rectangle_2<T>

Definition

Given a set of points in the plane, the class Largest_empty_iso_rectangle_2<T> 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. The class Largest_empty_iso_rectangle_2<T> expects a model of the concept LargestEmptyIsoRectangleTraits_2 as its template argument. #include <CGAL/Largest_empty_iso_rectangle_2.h>

Types

The class Largest_empty_iso_rectangle_2<T> defines the following types:

typedef T Traits;

typedef Traits::Point_2
Point_2;

typedef Traits::Iso_rectangle_2
Iso_rectangle_2;
The following 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.
Largest_empty_iso_rectangle_2<T>::const_iterator
Iterator over the points.

Creation

Largest_empty_iso_rectangle_2<T> l ( Iso_rectangle_2 b);
Constructor. The iso-rectangle b is the bounding rectangle.

Largest_empty_iso_rectangle_2<T> l ( 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<T> l;
Constructor. The iso-rectangle whose lower left point and upper right points are (0,0) and (1,1) respectively is the bounding rectangle.

Largest_empty_iso_rectangle_2<T> l ( const Largest_empty_iso_rectangle_2<Traits> tr);
Copy constructor.

Operations

Assignment

Largest_empty_iso_rectangle_2<T>
l = tr

Access Functions

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

Queries

Quadruple<Point_2, Point_2, Point_2, Point_2>
l.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.)
Iso_rectangle_2 l.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.)
Iso_rectangle_2 l.get_bounding_box ()
Returns the iso-rectangle passed in the constructor.

Insertion

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

Requirements

The value_type of first and last is Point.

Removal

bool l.remove ( Point_2 p)
Removes point p. Returns false iff p is not in the point set.

void l.clear ()
Removes all points of l.

Implementation

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

Next: LargestEmptyIsoRectangleTraits_2
Navigation: Table of Contents, Bibliography, Index, Title Page
The CGAL Project . Tue, December 21, 2004 .