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

## CGAL::maximum_perimeter_inscribed_k_gon_2

### Definition

The function maximum_perimeter_inscribed_k_gon_2 computes a maximum perimeter k-gon Pk that can be inscribed into a given convex polygon P. Note that

- Pk is not unique in general, but it can be chosen in such a way that its vertices form a subset of the vertex set of P and
- the vertices of a maximum perimeter k-gon, where the k vertices are to be drawn from a planar point set S, lie on the convex hull of S i.e. a convex polygon.

#include <CGAL/extremal_polygon_2.h>

template < class RandomAccessIterator, class OutputIterator >
OutputIterator |
maximum_perimeter_inscribed_k_gon_2 (
| RandomAccessIterator points_begin, RandomAccessIterator points_end, int k, OutputIterator o)

computes a maximum perimeter inscribed k-gon of the convex polygon described by [points_begin, points_end), writes its vertices to o and returns the past-the-end iterator of this sequence.

Precondition:

1. the - at least three - points denoted by the range [points_begin, points_end) form the boundary of a convex polygon (oriented clock- or counterclockwise).
2. k 2.

Requirement:

1. Value type of RandomAccessIterator is K::Point_2 where K is a model for Kernel.
2. There is a global function K::FT CGAL::sqrt(K::FT) defined that computes the squareroot of a number.
3. OutputIterator accepts the value type of RandomAccessIterator as value type.

### See Also

CGAL::maximum_area_inscribed_k_gon_2
ExtremalPolygonTraits_2
CGAL::Extremal_polygon_area_traits_2<K>
CGAL::Extremal_polygon_perimeter_traits_2<K>
CGAL::extremal_polygon_2
CGAL::monotone_matrix_search

### Implementation

The implementation uses monotone matrix search [AKM+87] and has a worst case running time of O(k · n + n · logn), where n is the number of vertices in P.

### Example

The following code generates a random convex polygon p with ten vertices and computes the maximum perimeter inscribed five-gon of p.

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

    typedef double                                    FT;

    struct Kernel : public CGAL::Cartesian<FT> {};

    typedef Kernel::Point_2                           Point;
    typedef std::vector<int>                          Index_cont;
    typedef CGAL::Polygon_2<Kernel>                   Polygon;
    typedef CGAL::Random_points_in_square_2<Point>    Generator;

    int main() {

      int n = 10;
      int k = 5;

      // generate random convex polygon:
      Polygon p;
      CGAL::random_convex_set_2(n, std::back_inserter(p), Generator(1));
      std::cout << "Generated Polygon:\n" << p << std::endl;

      // compute maximum perimeter incribed k-gon of p:
      Polygon k_gon;
      CGAL::maximum_perimeter_inscribed_k_gon_2(
        p.vertices_begin(), p.vertices_end(), k, std::back_inserter(k_gon));
      std::cout << "Maximum perimeter " << k << "-gon:\n"
                << k_gon << std::endl;

      return 0;
    }

Next: extremal_polygon_2

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

The CGAL Project . Tue, December 21, 2004 .