Inscribed Areas Reference

Michael Hoffmann and Eli Packer

This package provides algorithms for computing inscribed areas. The algorithms for computing inscribed areas are: the largest inscribed k-gon (area or perimeter) of a convex point set and the largest inscribed iso-rectangle.

Introduced in: CGAL 1.1
BibTeX: cgal:hp-ia-22a
License: GPL
Windows Demos: 2D Inscribed k-gon as part of Polygon demo, 2D Largest Empty Rectangle
Common Demo Dlls: dlls

Assertions

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.

Classified Reference Pages

• 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...

Function Documentation

extremal_polygon_2()

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
	)

#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.

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).

k >= t.min_k().

Template Parameters

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.

See also

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\).

maximum_area_inscribed_k_gon_2()

template<class RandomAccessIterator , class OutputIterator >

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

• \( P_k\) 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 area 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.

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).

k >= 3.

Template Parameters

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.

See also

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

#include <CGAL/Simple_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;

typedef CGAL::Simple_cartesian<FT>                Kernel;

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 area incribed k-gon of p:
  Polygon_2 k_gon;
  CGAL::maximum_area_inscribed_k_gon_2(
    p.vertices_begin(), p.vertices_end(), k, std::back_inserter(k_gon));
  std::cout << "Maximum area " << k << "-gon:\n"
            << k_gon << std::endl;

  return 0;
}

Examples:

Inscribed_areas/extremal_polygon_2_area.cpp.

maximum_perimeter_inscribed_k_gon_2()

template<class RandomAccessIterator , class OutputIterator >

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

• \( P_k\) 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.

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).

k >= 2.

Template Parameters

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.

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()

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

#include <CGAL/Simple_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;

typedef CGAL::Simple_cartesian<FT>                Kernel;

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;
}

Examples:

Inscribed_areas/extremal_polygon_2_perimeter.cpp.