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

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

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

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.

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.

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

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

InputIterator

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