Computing a Minimum Enclosing Parallelogram

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

#include <CGAL/minimum_enclosing_quadrilateral_2.h>

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

computes a minimum enclosing parallelogram 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 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

Example

#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_parallelogram_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 parallelogram p_m of p
  Polygon_2 p_m;
  minimum_enclosing_parallelogram_2(
    p.vertices_begin(), p.vertices_end(), back_inserter(p_m));
  cout << p_m << endl;

  return 0;
}