CGAL 5.1.2 - Inscribed Areas
|
The optimization code uses infix OPTIMISATION
in the assertions, e.g. defining the compiler flag CGAL_OPTIMISATION_NO_PRECONDITIONS
switches precondition checking off, cf. Section Checks.
CGAL::maximum_area_inscribed_k_gon_2
CGAL::maximum_perimeter_inscribed_k_gon_2
CGAL::extremal_polygon_2
CGAL::Largest_empty_iso_rectangle_2<T>
CGAL::Extremal_polygon_area_traits_2<K>
CGAL::Extremal_polygon_perimeter_traits_2<K>
ExtremalPolygonTraits_2
LargestEmptyIsoRectangleTraits_2
Modules | |
Concepts | |
Classes | |
struct | CGAL::Extremal_polygon_area_traits_2< K > |
This is an advanced class. More... | |
struct | CGAL::Extremal_polygon_perimeter_traits_2< K > |
This is an advanced class. More... | |
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. More... | |
Functions | |
template<class RandomAccessIterator , class OutputIterator , class Traits > | |
OutputIterator | CGAL::extremal_polygon_2 (RandomAccessIterator points_begin, RandomAccessIterator points_end, int k, OutputIterator o, const Traits &t) |
computes a maximal (as specified by t ) 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. More... | |
template<class RandomAccessIterator , class OutputIterator > | |
OutputIterator | CGAL::maximum_area_inscribed_k_gon_2 (RandomAccessIterator points_begin, RandomAccessIterator points_end, int k, OutputIterator o) |
computes a maximum area 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. More... | |
template<class RandomAccessIterator , class OutputIterator > | |
OutputIterator | CGAL::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. More... | |
OutputIterator CGAL::extremal_polygon_2 | ( | RandomAccessIterator | points_begin, |
RandomAccessIterator | points_end, | ||
int | k, | ||
OutputIterator | o, | ||
const Traits & | t | ||
) |
#include <CGAL/extremal_polygon_2.h>
computes a maximal (as specified by t
) 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.
The function extremal_polygon_2()
computes a maximal k
-gon that can be inscribed into a given convex polygon. The criterion for maximality and some basic operations have to be specified in an appropriate traits class parameter.
[points_begin, points_end)
form the boundary of a convex polygon (oriented clock- or counterclockwise). k >= t.min_k()
.Traits | must be a model for ExtremalPolygonTraits_2 . |
RandomAccessIterator | must be an iterator with value type Traits::Point_2 . |
OutputIterator | must accepts dereference/assignments of Traits::Point_2 . |
CGAL::maximum_area_inscribed_k_gon_2()
CGAL::maximum_perimeter_inscribed_k_gon_2()
ExtremalPolygonTraits_2
Implementation
The implementation uses monotone matrix search [1] and has a worst case running time of \( O(k \cdot n + n \cdot \log n)\), where \( n\) is the number of vertices in \( P\).
OutputIterator CGAL::maximum_area_inscribed_k_gon_2 | ( | RandomAccessIterator | points_begin, |
RandomAccessIterator | points_end, | ||
int | k, | ||
OutputIterator | o | ||
) |
#include <CGAL/extremal_polygon_2.h>
computes a maximum area 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.
Computes a maximum area k
-gon \( P_k\) that can be inscribed into a given convex polygon \( P\). Note that
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. [points_begin, points_end)
form the boundary of a convex polygon (oriented clock- or counterclockwise). k >= 3
.RandomAccessIterator | must be an iterator with value type K::Point_2 where K is a model of Kernel . |
OutputIterator | must accepts dereference/assignments of Traits::Point_2 . |
CGAL::maximum_perimeter_inscribed_k_gon_2()
ExtremalPolygonTraits_2
CGAL::Extremal_polygon_area_traits_2<K>
CGAL::Extremal_polygon_perimeter_traits_2<K>
CGAL::extremal_polygon_2()
Implementation
The implementation uses monotone matrix search [1] and has a worst case running time of \( O(k \cdot n + n \cdot \log n)\), 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 area inscribed five-gon of p
.
File Inscribed_areas/extremal_polygon_2_area.cpp
OutputIterator CGAL::maximum_perimeter_inscribed_k_gon_2 | ( | RandomAccessIterator | points_begin, |
RandomAccessIterator | points_end, | ||
int | k, | ||
OutputIterator | o | ||
) |
#include <CGAL/extremal_polygon_2.h>
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.
The function maximum_perimeter_inscribed_k_gon_2()
computes a maximum perimeter k
-gon \( P_k\) that can be inscribed into a given convex polygon \( P\). Note that
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. [points_begin, points_end)
form the boundary of a convex polygon (oriented clock- or counterclockwise). k >= 2
.RandomAccessIterator | must be an iterator with value type K::Point_2 where K is a model for Kernel . |
OutputIterator | must accepts dereference/assignments of Traits::Point_2 . |
There must be a global function K::FT CGAL::sqrt(K::FT)
defined that computes the squareroot of a number.
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()
Implementation
The implementation uses monotone matrix search [1] and has a worst case running time of \( O(k \cdot n + n \cdot \log n)\), 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
.
File Inscribed_areas/extremal_polygon_2_perimeter.cpp