CGAL::Largest_empty_iso_rectangle_2< T > Class Template Reference

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