CGAL::maximum_perimeter_inscribed_k_gon_2
Definition
The function maximum_perimeter_inscribed_k_gon_2 computes a maximum perimeter
-gon that can be inscribed into a given convex polygon .
Note that
- 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 and
- the vertices of a maximum perimeter -gon, where the
vertices are to be drawn from a planar point set , lie on the
convex hull of 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 -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
- the - at least three - points denoted by the range
[points_begin, points_end) form the boundary of a
convex polygon (oriented clock- or counterclockwise).
- .
Requirement
- Value type of RandomAccessIterator is K::Point_2
where K is a model for Kernel.
- There is a global function K::FT CGAL::sqrt(K::FT)
defined that computes the squareroot of a number.
- 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
[AKM87] and has a worst case running time of log, where is the number of vertices in
.
Example
The following code generates a random convex polygon
p with ten vertices and computes the maximum perimeter inscribed
five-gon of p.
File: examples/Matrix_search/extremal_polygon_2_perimeter.cpp
#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_2;
typedef CGAL::Random_points_in_square_2<Point> Generator;
int main() {
int n = 10;
int k = 5;
// generate random convex polygon:
Polygon_2 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_2 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;
}