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>
|
|
|
|
|
|
|
|
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.
| |
Iterator over the points.
|
| |
Constructor. The iso-rectangle b is the bounding rectangle.
| |
| |
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.
| |
| |
Copy constructor.
|
|
|
| ||
| 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.) | |
|
| |
Returns the largest empty iso-rectangle. (Note that the two points defining the iso-rectangle are not necessarily part of the point set.) | ||
|
| Returns the iso-rectangle passed in the constructor. |
|
| Inserts point p in the point set, if it is not already in the set. |
|
| Inserts point p in the point set, if it is not already in the set. |
| ||
|
| |
Inserts the points in the range first,
last. Returns the number of inserted points.RequirementsThe value_type of first and last is Point. |
|
| Removes point p. Returns false iff p is not in the point set. |
|
| Removes all points of l. |
The algorithm is an implementation of [Orl90]. The runtime of an insertion or a removal is log. A query takes worst case time and log expected time. The working storage is .