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

Computing a Minimum Enclosing Rectangle

This section describes a function to compute a minimal enclosing rectangle (not necessarily axis-parallel) of a given convex point set. Note that this rectangle is not unique in general.

#include <CGAL/minimum_enclosing_quadrilateral_2.h>

template < class ForwardIterator, class OutputIterator, class Traits >
OutputIterator
minimum_enclosing_rectangle_2 (
ForwardIterator points_begin,
ForwardIterator points_end,
OutputIterator o,
Traits& t = Default_traits)

computes a minimum enclosing rectangle of the point set described by [points_begin, points_end), writes its vertices (counterclockwise) to o and returns the past-the-end iterator of this sequence.
If the input range is empty, o remains unchanged.
If the input range consists of one element only, exactly this point is written to o.

Precondition

  1. If Traits is specified, it satisfies the requirements stated in section reference and the value type VT of InputIterator is Traits::Point_2. Otherwise VT is CGAL::Point_2<R> for some representation class R.
  2. OutputIterator accepts VT as value type.
  3. The points denoted by the range [points_begin, points_end) form the boundary of a convex polygon P in counterclockwise orientation.

Implementation

We use a rotating caliper algorithm [Tou83] with worst case running time linear in the number of input points.

Example

The following code generates a random convex polygon P with 20 vertices and computes the minimum enclosing rectangle of P.

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <CGAL/minimum_enclosing_quadrilateral_2.h>
#include <vector>
#include <iostream>

using CGAL::Random_points_in_square_2;
using CGAL::random_convex_set_2;
using CGAL::minimum_enclosing_rectangle_2;
using std::back_inserter;
using std::cout;
using std::endl;

typedef CGAL::Cartesian< double >                      R;
typedef R::Point_2                                     Point_2;
typedef R::Line_2                                      Line_2;
typedef CGAL::Polygon_traits_2< R >                    P_traits;
typedef std::vector< Point_2 >                         Cont;
typedef CGAL::Polygon_2< P_traits, Cont >              Polygon_2;
typedef CGAL::Creator_uniform_2< double, Point_2 >     Creator;
typedef Random_points_in_square_2< Point_2, Creator >  Point_generator;

int main()
{
  // build a random convex 20-gon p
  Polygon_2 p;
  random_convex_set_2(20, back_inserter(p), Point_generator(1.0));
  cout << p << endl;

  // compute the minimal enclosing rectangle p_m of p
  Polygon_2 p_m;
  minimum_enclosing_rectangle_2(
    p.vertices_begin(), p.vertices_end(), back_inserter(p_m));
  cout << p_m << endl;

  return 0;
} 


Next: Function Declaration of minimum_enclosing_parallelogram_2
Navigation: Up, Table of Contents, Bibliography, Index, Title Page
The GALIA project. Jan 18, 2000.