CGAL 4.7 - Geometric Object Generators: Geometric Object Generators Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Geometric Object Generators

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Classes | Functions | Variables
Geometric Object Generators Reference

##

Pedro M. M. de Castro, Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, Sven Schönherr, and Alexandru Tifrea
This package provides a variety of generators for geometric objects. They are useful as synthetic test data sets, e.g. for testing algorithms on degenerate object sets and for performance analysis.

Introduced in: CGAL 1.0
BibTeX: cgal:dhhk-gog-15b
License: LGPL
Windows Demo: Generators
Common Demo Dlls: dlls

This chapter describes the functions and classes provided in CGAL that are useful for generating synthetic test data sets, e.g., for testing algorithms on degenerate object sets and for performance analysis. These include a class for generating random numbers and function for selecting random items from a set of objects, generators for two-dimensional and three-dimensional points sets, a generator for random convex sets and one for simple polygons. The STL algorithm `std::random_shuffle` is useful with these functions and classes to to achieve random permutations for otherwise regular generators ( e.g., points on a grid or segment).

## Classified Reference Pages

## Concepts

- `PointGenerator`
- `RandomConvexSetTraits_2`
- `RandomPolygonTraits_2`
- `RandomConvexHullTraits_2`

## Functions

- `CGAL::perturb_points_2()`
- `CGAL::points_on_segment_2()`
- `CGAL::points_on_square_grid_2()`
- `CGAL::points_on_cube_grid_3()`
- `CGAL::points_on_cube_grid_d()`
- `CGAL::random_collinear_points_2()`
- `CGAL::random_convex_set_2()`
- `CGAL::random_polygon_2()`
- `CGAL::random_selection()`
- `CGAL::random_convex_hull_in_disc_2()`

## Variables

- `CGAL::default_random`

## Classes

- `CGAL::Random`
- `CGAL::Points_on_segment_2<Point_2>`
- `CGAL::Random_points_in_ball_d<Point_d>`
- `CGAL::Random_points_in_cube_3<Point_3, Creator>`
- `CGAL::Random_points_in_cube_d<Point_d>`
- `CGAL::Random_points_in_disc_2<Point_2, Creator>`
- `CGAL::Random_points_in_triangle_2<Point_2, Creator>`
- `CGAL::Random_points_in_sphere_3<Point_3, Creator>`
- `CGAL::Random_points_in_triangle_3<Point_3, Creator>`
- `CGAL::Random_points_in_tetrahedron_3<Point_3, Creator>`
- `CGAL::Random_points_in_square_2<Point_2, Creator>`
- `CGAL::Random_points_on_circle_2<Point_2, Creator>`
- `CGAL::Random_points_on_segment_2<Point_2, Creator>`
- `CGAL::Random_points_on_sphere_3<Point_3, Creator>`
- `CGAL::Random_points_on_sphere_d<Point_d>`
- `CGAL::Random_points_on_square_2<Point_2, Creator>`

## Traits Class

- `CGAL::Random_convex_set_traits_2<Kernel>`

## Modules

| Concepts

## Classes

class | CGAL::Combination_enumerator< CombinationElement >
| The class `Combination_enumerator` is used to enumerate all fixed-size combinations (subsets) of a source range of elements. More...
class | CGAL::Random
| The class `Random` is a random numbers generator. More...

## Functions

template<class ForwardIterator , class Creator >
void | CGAL::perturb_points_2 (ForwardIterator first, ForwardIterator last, double xeps, double yeps=xeps, Random &rnd=default_random, Creator creator=Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >)
| perturbs each point in a given range of points by a random amount. More...
template<class P , class OutputIterator >
OutputIterator | CGAL::points_on_segment_2 (const P &p, const P &q, std::size_t n, OutputIterator o)
| generates a set of points equally spaced on a segment given the endpoints of the segment. More...
template<class OutputIterator , class Creator >
OutputIterator | CGAL::points_on_square_grid_2 (double a, std::size_t n, OutputIterator o, Creator creator=Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >)
| generates a given number of points on a square grid whose size is determined by the number of points to be generated. More...
template<class RandomAccessIterator , class OutputIterator , class Creator >
OutputIterator | CGAL::random_collinear_points_2 (RandomAccessIterator first, RandomAccessIterator last, std::size_t n, OutputIterator first2, Random &rnd=default_random, Creator creator=Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >)

randomly chooses two points from the range `[first,last)`, creates a random third point on the segment connecting these two points, writes it to `first2`, and repeats this \( n\) times, thus writing \( n\) points to `first2` that are collinear with points in the range `[first,last)`. More...

template<class OutputIterator , class Creator >
OutputIterator | CGAL::points_on_cube_grid_3 (double a, std::size_t n, OutputIterator o, Creator creator=Creator_uniform_3< Kernel_traits< Point_3 >::Kernel::RT, Point_3 >)
| generates a given number of points on a cubic grid whose size is determined by the number of points to be generated. More...
template<class OutputIterator , class Creator >
OutputIterator | CGAL::points_on_cube_grid_d (int dim, double a, std::size_t n, OutputIterator o, Creator creator)
| generates a given number of points on a cubic grid in any dimension whose size is determined by the number of points to be generated. More...
template<class OutputIterator , class Traits , class Generator >
void | CGAL::random_convex_hull_in_disc_2 (std::size_t n, double radius, Generator &gen, OutputIterator it, const Traits &traits, bool fast=true)
| Computes a random convex polygon as the convex hull of \( n \) random points in a disc centered at the origin with radius `radius`. More...
template<class OutputIterator , class PointGenerator , class Traits >
OutputIterator | CGAL::random_convex_set_2 (std::size_t n, OutputIterator o, const PointGenerator &pg, Traits t=Random_convex_set_traits_2)
| computes a random convex planar point set of given size where the points are drawn from a specific domain. More...
template<class OutputIterator , class PointGenerator , class Traits >
OutputIterator | CGAL::random_polygon_2 (std::size_t n, OutputIterator result, const PointGenerator &pg, Traits t=Default_traits)
| computes a random simple polygon by writing its vertices (oriented counterclockwise) to `result`. More...
template<class RandomAccessIterator , class Size , class OutputIterator , class Random >
OutputIterator | CGAL::random_selection (RandomAccessIterator first, RandomAccessIterator last, Size n, OutputIterator result, Random &rnd=default_random)
| chooses `n` items at random from a random access iterator range which is useful to produce degenerate input data sets with multiple entries of identical items. More...

## Variables

CGAL::Random | CGAL::default_random
| The variable `default_random` is the default random numbers generator used for the generator functions and classes.

## Creation

| CGAL::Combination_enumerator< CombinationElement >::Combination_enumerator (int k, const CombinationElement &first, const CombinationElement &beyond)
| This constructor initializes the object to enumerate the combinations of `k` elements from the source range `[first, beyond)`. More...
| CGAL::Combination_enumerator< CombinationElement >::Combination_enumerator (const Combination_enumerator &combi)
| The copy constructor.

## Access to the Current Combination

const CombinationElement & | CGAL::Combination_enumerator< CombinationElement >::operator[] (int i)
| Returns the `i`-th element of the current combination. More...

## Access to the Enumeration

int | CGAL::Combination_enumerator< CombinationElement >::number_of_elements ()
| Returns the size of the enumerated combinations (the parameter `k` from the class' constructor).
const CombinationElement & | CGAL::Combination_enumerator< CombinationElement >::min_element ()
| Returns the smallest element of the source range. More...
const CombinationElement & | CGAL::Combination_enumerator< CombinationElement >::beyond_element ()
| Returns the successor to the largest element of the source range (the parameter `beyond` of the constructor of the class).
bool | CGAL::Combination_enumerator< CombinationElement >::finished ()
| Returns `true` if and only if all combinations have been enumerated.

## Operations

void | CGAL::Combination_enumerator< CombinationElement >::reset ()
| Resets the enumerator. More...
void | CGAL::Combination_enumerator< CombinationElement >::operator++ ()
| Moves *this to the next combination.
Combination_enumerator | CGAL::Combination_enumerator< CombinationElement >::operator++ (int)
| Post-incrementation. More...

## Function Documentation

template<class CombinationElement>

CGAL::Combination_enumerator< CombinationElement >::Combination_enumerator | ( | int | k,
|  | const CombinationElement & | first,
|  | const CombinationElement & | beyond
| ) |  |

This constructor initializes the object to enumerate the combinations of `k` elements from the source range `[first, beyond)`.

The current combination is set to the first combination of the enumeration.

Precondition
  `1 <= k <= beyond - first`

`#include <CGAL/Combination_enumerator.h>`

template<class CombinationElement>

const CombinationElement& CGAL::Combination_enumerator< CombinationElement >::min_element | ( | ) |  |

Returns the smallest element of the source range.

(the parameter `first` of the constructor of the class).

`#include <CGAL/Combination_enumerator.h>`

template<class CombinationElement>

Combination_enumerator CGAL::Combination_enumerator< CombinationElement >::operator++ | ( | int | ) |  |

Post-incrementation.

Same as the pre-incrementation above, but returns the original value of `*this`.

`#include <CGAL/Combination_enumerator.h>`

template<class CombinationElement>

const CombinationElement& CGAL::Combination_enumerator< CombinationElement >::operator[] | ( | int | i) |  |

Returns the `i`-th element of the current combination.

Precondition
  `0 <= i < number_of_elements()`

`#include <CGAL/Combination_enumerator.h>`

template<class ForwardIterator , class Creator >

void CGAL::perturb_points_2 | ( | ForwardIterator | first,
|  | ForwardIterator | last,
|  | double | xeps,
|  | double | yeps = `xeps`,
|  | Random & | rnd = `default_random`,
|  | Creator | creator = `Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >`
| ) |  |

perturbs each point in a given range of points by a random amount.

The function perturbs the points in the range `[first,last)` by replacing each point with a random point from the `xeps` \( \times\) `yeps` rectangle centered at the original point. Two random numbers are needed from `rnd` for each point.

Requires

- `Creator` must be a function object accepting two `double` values \( x\) and \( y\) and returning an initialized point `(x,y)` of type `P`. Predefined implementations for these creators like the default are described in Section Creator Function Objects.
- The `value_type` of the `ForwardIterator` must be assignable to `P`.
- `P` is equal to the `value_type` of the `ForwardIterator` when using the default initializer.
- The expressions `to_double((*first).x())` and `to_double((*first).y())` must result in the respective coordinate values.

See Also
  `CGAL::points_on_segment_2()`
  `CGAL::points_on_square_grid_2()`
  `CGAL::random_selection()`
  `CGAL::random_selection()`
  `std::random_shuffle`

`#include <CGAL/point_generators_2.h>`

template<class OutputIterator , class Creator >

OutputIterator CGAL::points_on_cube_grid_3 | ( | double | a,
|  | std::size_t | n,
|  | OutputIterator | o,
|  | Creator | creator = `Creator_uniform_3< Kernel_traits< Point_3 >::Kernel::RT, Point_3 >`
| ) |  |

generates a given number of points on a cubic grid whose size is determined by the number of points to be generated.

The function creates the first \( n\) points on the regular \( \lceil n^{1/3}\,\rceil\times\lceil n^{1/3}\,\rceil\times\lceil n^{1/3}\,\rceil\) grid within the cube \( [-a,a]\times[-a,a]\times[-a, a]\). Returns the value of \( o\) after inserting the \( n\) points.

Requires

- `Creator` must be a function object accepting three `double` values \( x\), \( y\), and \( z\) and returning an initialized point `(x,y,z)` of type `P`. Predefined implementations for these creators like the default can be found in Section Creator Function Objects.
- The `OutputIterator` must accept values of type `P`. If the `OutputIterator` has a `value_type` the default initializer of the `creator` can be used. `P` is set to the `value_type` in this case.

See Also
  `CGAL::points_on_square_grid_2()`
  `CGAL::random_selection()`

`#include <CGAL/point_generators_3.h>`

template<class OutputIterator , class Creator >

OutputIterator CGAL::points_on_cube_grid_d | ( | int | dim,
|  | double | a,
|  | std::size_t | n,
|  | OutputIterator | o,
|  | Creator | creator
| ) |  |

generates a given number of points on a cubic grid in any dimension whose size is determined by the number of points to be generated.

It creates the first \( n\) points on the regular \( \lceil n^{1/dim}\,\rceil\times\lceil n^{1/dim}\,\rceil\times\ldots\times\lceil n^{1/dim}\,\rceil\) grid within the hypercube \( [-a,a]^{dim}\).

Returns
  the value of \( o\) after inserting the \( n\) points.

Requirements

- `Creator` must be a functor accepting an integer (the dimension) and two iterators and returning an initialized point of type `P` whose coordinates are given by the iterator. For example: `Creator_uniform_d<Kernel_traits<Point_d>Kernel::RT, Point_d>`. The dimension of `Creator` should be \( dim\).
- The `OutputIterator` must accept values of type `P`.

See Also
  `CGAL::points_on_square_grid_2()`
  `CGAL::points_on_cube_grid_3()`

`#include <CGAL/point_generators_d.h>`

Examples:
  Generator/grid_d.cpp.

template<class P , class OutputIterator >

OutputIterator CGAL::points_on_segment_2 | ( | const P & | p,
|  | const P & | q,
|  | std::size_t | n,
|  | OutputIterator | o
| ) |  |

generates a set of points equally spaced on a segment given the endpoints of the segment.

The function creates \( n\) points equally spaced on the segment from \( p\) to \( q\), i.e. \( \forall i: 0 \le i < n: o[i] := \frac{n-i-1}{n-1}\, p + \frac{i}{n-1}\, q\). Returns the value of \( o\) after inserting the \( n\) points.

See Also
  `CGAL::points_on_segment_2()`
  `CGAL::points_on_square_grid_2()`
  `CGAL::random_collinear_points_2()`

`#include <CGAL/point_generators_2.h>`

template<class OutputIterator , class Creator >

OutputIterator CGAL::points_on_square_grid_2 | ( | double | a,
|  | std::size_t | n,
|  | OutputIterator | o,
|  | Creator | creator = `Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >`
| ) |  |

generates a given number of points on a square grid whose size is determined by the number of points to be generated.

The function creates the first \( n\) points on the regular \( \lceil\sqrt{n}\,\rceil\times\lceil\sqrt{n}\,\rceil\) grid within the square \( [-a,a]\times[-a,a]\). Returns the value of \( o\) after inserting the \( n\) points.

Requires

- `Creator` must be a function object accepting two `double` values \( x\) and \( y\) and returning an initialized point `(x,y)` of type `P`. Predefined implementations for these creators like the default can be found in Section Creator Function Objects.
- The `OutputIterator` must accept values of type `P`. If the `OutputIterator` has a `value_type` the default initializer of the `creator` can be used. `P` is set to the `value_type` in this case.

See Also
  `CGAL::perturb_points_2()`
  `CGAL::points_on_segment_2()`
  `CGAL::points_on_cube_grid_3()`
  `CGAL::random_collinear_points_2()`
  `CGAL::random_selection()`
  `std::random_shuffle`

`#include <CGAL/point_generators_2.h>`

Examples:
  Generator/random_degenerate_point_set.cpp, and Generator/random_grid.cpp.

template<class RandomAccessIterator , class OutputIterator , class Creator >

OutputIterator CGAL::random_collinear_points_2 | ( | RandomAccessIterator | first,
|  | RandomAccessIterator | last,
|  | std::size_t | n,
|  | OutputIterator | first2,
|  | Random & | rnd = `default_random`,
|  | Creator | creator = `Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >`
| ) |  |

randomly chooses two points from the range `[first,last)`, creates a random third point on the segment connecting these two points, writes it to `first2`, and repeats this \( n\) times, thus writing \( n\) points to `first2` that are collinear with points in the range `[first,last)`.

Three random numbers are needed from `rnd` for each point. Returns the value of `first2` after inserting the \( n\) points.

Requires

- `Creator` must be a function object accepting two `double` values \( x\) and \( y\) and returning an initialized point `(x,y)` of type `P`. Predefined implementations for these creators like the default can be found in Section Creator Function Objects.
- The `value_type` of the `RandomAccessIterator` must be assignable to `P`. `P` is equal to the `value_type` of the `RandomAccessIterator` when using the default initializer.
- The expressions `to_double((*first).x())` and `to_double((*first).y())` must result in the respective coordinate values.

See Also
  `CGAL::perturb_points_2()`
  `CGAL::points_on_segment_2()`
  `CGAL::points_on_square_grid_2()`
  `CGAL::random_selection()`
  `std::random_shuffle`

`#include <CGAL/point_generators_2.h>`

Examples:
  Generator/random_degenerate_point_set.cpp.

template<class OutputIterator , class Traits , class Generator >

void CGAL::random_convex_hull_in_disc_2 | ( | std::size_t | n,
|  | double | radius,
|  | Generator & | gen,
|  | OutputIterator | it,
|  | const Traits & | traits,
|  | bool | fast = `true`
| ) |  |

Computes a random convex polygon as the convex hull of \( n \) random points in a disc centered at the origin with radius `radius`.

The vertices are stored counterclockwise in `it`. The generated polygon will have an average number of vertices \( n^\frac{1}{3}(1+o(1))\).

Precondition
  \(n \geq 3 \)

Requirements

- `Generator` has to be a Boost random generator, such as `boost::random::mt19937`.
- `fast` is a Boolean , set to `true` for time efficiency and to `false` for memory efficiency.
- `Traits` is a model of the concept `RandomConvexHullTraits_2`.
- The `OutputIterator` must accept values of type `Traits::Point_2`.

See Also
  `CGAL::random_polygon_2()`
  `CGAL::random_convex_set_2()`

Implementation

The implementation is based on an incremental construction of a convex hull. At each step, we choose a number of points to pick uniformly at random in the disc. Then, a subset of these points, that won't change the convex hull, is evaluated using a Binomial law. As these points won't be generated, the time and size complexities are reduced [1]. A tradeoff between time and memory is provided with the option `fast`, true by default. Using the `fast` option, both time and size expected complexities are \(O\left(n^\frac{1}{3}\log^\frac{2}{3}n \right)\). If this option is disabled, the expected size complexity becomes \(O\left(n^\frac{1}{3}\right)\) but the expected time complexity becomes \(O\left(n^\frac{1}{3}\log^2 n \right)\).

Example

The following program computes a random polygon defined as the convex hull of \(10000\) points uniformly generated in the disc of radius \(1\) centered in \(0\).

File Generator/random_convex_hull_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/random_convex_hull_in_disc_2.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <boost/random.hpp>
#include <iostream>
#include <vector>
using namespace CGAL;
typedef Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef K::FT FT;
const double RADIUS=1.0;
int main( )
{
int N=10000;
std::vector<Point> v;
boost::mt19937 gen;
gen.seed(0u);
random_convex_hull_in_disc_2(N,RADIUS,gen,std::back_inserter(v),K());
size_t size = v.size();
FT area=polygon_area_2(v.begin(),v.end(),K());
std::cout<<"A random convex polygon inscribed in a disc with "<<size<<" vertices and area "<<area<<" has been generated."<<std::endl;
return 0;
}

`#include <CGAL/random_convex_hull_in_disc_2.h>`

Examples:
  Generator/random_convex_hull_2.cpp.

template<class OutputIterator , class PointGenerator , class Traits >

OutputIterator CGAL::random_convex_set_2 | ( | std::size_t | n,
|  | OutputIterator | o,
|  | const PointGenerator & | pg,
|  | Traits | t = `Random_convex_set_traits_2`
| ) |  |

computes a random convex planar point set of given size where the points are drawn from a specific domain.

The function computes a random convex `n`-gon by writing its vertices (oriented counterclockwise) to `o`. The resulting polygon is scaled such that it fits into the bounding box as specified by `pg`. Therefore we cannot easily describe the resulting distribution.

Precondition
  \( n \ge3\).

Requirements

- `PointGenerator` is a model of the concept PointGenerator
- `Traits` is a model of the concept RandomConvexSetTraits_2
- `Point_generator::value_type` is equivalent to `Traits::Point_2` and `OutputIterator::value_type`.
- if `Traits` is not specified, `Point_generator::value_type` must be `Point_2< R >` for some representation class `R`,

See Also
  `CGAL::Random_points_in_square_2<Point_2, Creator>`
  `CGAL::Random_points_in_disc_2<Point_2, Creator>`

Implementation

The implementation uses the centroid method described in [2] and has a worst case running time of \( O(r \cdot n + n \cdot \log n)\), where \( r\) is the time needed by `pg` to generate a random point.

Example

The following program displays a random convex 500-gon where the points are drawn uniformly from the unit square centered at the origin.

File Generator/random_convex_set.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <iostream>
#include <iterator>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef CGAL::Random_points_in_square_2<
Point_2,
CGAL::Creator_uniform_2< double, Point_2 > >
Point_generator;
int main() {
// create 500-gon and write it into a window:
CGAL::random_convex_set_2(
500,
std::ostream_iterator<Point_2>(std::cout, "\n"),
Point_generator( 0.5));
return 0;
}

`#include <CGAL/random_convex_set_2.h>`

Examples:
  Generator/random_convex_set.cpp.

template<class OutputIterator , class PointGenerator , class Traits >

OutputIterator CGAL::random_polygon_2 | ( | std::size_t | n,
|  | OutputIterator | result,
|  | const PointGenerator & | pg,
|  | Traits | t = `Default_traits`
| ) |  |

computes a random simple polygon by writing its vertices (oriented counterclockwise) to `result`.

The polygon generated will have a number of vertices equal to the number of unique points in the first \( n\) points generated by `pg`.

Constructs a random simple polygon from points that are drawn from a specific domain. Though each simple polygon defined on this set of points has a non-zero probability of being constructed, some polygons may have higher probabilities than others. The overall distribution of the generated polygons is not known since it depends on the generated points.

Requirements

- `Traits` is a model of the concept RandomPolygonTraits_2
- `PointGenerator::value_type` is equivalent to `Traits::Point_2` and `OutputIterator::value_type`.

The default traits class `Default_traits` is the kernel in which `Traits::Point_2` is defined.

See Also
  `CGAL::Random_points_in_disc_2<Point_2, Creator>`
  `CGAL::Random_points_in_square_2<Point_2, Creator>`

Implementation

The implementation is based on the method of eliminating self-intersections in a polygon by using so-called "2-opt" moves. Such a move eliminates an intersection between two edges by reversing the order of the vertices between the edges. No more than \( O(n^3)\) such moves are required to simplify a polygon defined on \( n\) points [3]. Intersecting edges are detected using a simple sweep through the vertices and then one intersection is chosen at random to eliminate after each sweep. The worse-case running time is therefore \( O(n^4 \log n)\).

Example

The following program displays a random simple polygon with up to 100 vertices, where the vertex coordinates are drawn uniformly from the unit square centered at the origin.

File Generator/random_polygon.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_polygon_2.h>
#include <CGAL/Random.h>
#include <CGAL/algorithm.h>
#ifdef CGAL_USE_GMP
#include <CGAL/Gmpz.h>
typedef CGAL::Gmpz RT;
#else
// NOTE: the choice of double here for a number type may cause problems
// for degenerate point sets
#include <CGAL/double.h>
typedef double RT;
#endif
#include <fstream>
#include <list>
typedef CGAL::Simple_cartesian<RT> K;
typedef K::Point_2 Point_2;
typedef std::list<Point_2> Container;
typedef CGAL::Polygon_2<K, Container> Polygon_2;
typedef CGAL::Creator_uniform_2<int, Point_2> Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator;
const double RADIUS = 100;
const int MAX_POLY_SIZE = 100;
int main( )
{
Polygon_2 polygon;
std::list<Point_2> point_set;
CGAL::Random rand;
int size = rand.get_int(4, MAX_POLY_SIZE);
// copy size points from the generator, eliminating duplicates, so the
// polygon will have <= size vertices
CGAL::copy_n_unique(Point_generator(RADIUS), size,
std::back_inserter(point_set));
std::ostream_iterator< Point_2 > out( std::cout, " " );
std::cout << "From the following " << point_set.size() << " points "
<< std::endl;
std::copy(point_set.begin(), point_set.end(), out);
std::cout << std::endl;
CGAL::random_polygon_2(point_set.size(), std::back_inserter(polygon),
point_set.begin());
std::cout << "The following simple polygon was made: " << std::endl;
std::cout << polygon << std::endl;
return 0;
}

`#include <CGAL/random_polygon_2.h>`

Examples:
  Generator/random_polygon.cpp, and Generator/random_polygon2.cpp.

template<class RandomAccessIterator , class Size , class OutputIterator , class Random >

OutputIterator CGAL::random_selection | ( | RandomAccessIterator | first,
|  | RandomAccessIterator | last,
|  | Size | n,
|  | OutputIterator | result,
|  | Random & | rnd = `default_random`
| ) |  |

chooses `n` items at random from a random access iterator range which is useful to produce degenerate input data sets with multiple entries of identical items.

The function chooses a random item from the range `[first,last)` and writes it to `result`, each item from the range with equal probability, and repeats this \( n\) times, thus writing `n` items to `result`. A single random number is needed from `rnd` for each item. Returns the value of `result` after inserting the `n` items.

Precondition
  `Random` is a random number generator type as provided by the STL or by `Random`.

See Also
  `CGAL::perturb_points_2()`

`#include <CGAL/random_selection.h>`

Examples:
  Generator/random_degenerate_point_set.cpp.

template<class CombinationElement>

void CGAL::Combination_enumerator< CombinationElement >::reset | ( | ) |  |

Resets the enumerator.

The current combination is set to the first one of the enumeration.

`#include <CGAL/Combination_enumerator.h>`