CGAL 6.2 - Geometric Object Generators

Loading...
Searching...
No Matches
Modules | Classes | Functions | Variables
Reference Manual

##

Pedro M. M. de Castro, Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, Sven Schönherr, Alexandru Tifrea, and Maxime Gimeno
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-26a
License: LGPL
Windows Demo: Generators

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 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()`
- `CGAL::get_default_random()`

## Classes

- `CGAL::Random`
- `CGAL::Points_on_segment_2<Point_2>`
- `CGAL::Random_points_on_segment_2<Point_2, Creator>`
- `CGAL::Random_points_in_triangle_2<Point_2, Creator>`
- `CGAL::Random_points_in_square_2<Point_2, Creator>`
- `CGAL::Random_points_in_disc_2<Point_2, Creator>`
- `CGAL::Random_points_on_circle_2<Point_2, Creator>`
- `CGAL::Random_points_on_segment_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_cube_3<Point_3, Creator>`
- `CGAL::Random_points_in_sphere_3<Point_3, Creator>`
- `CGAL::Random_points_on_sphere_3<Point_3, Creator>`
- `CGAL::Random_points_in_ball_d<Point_d>`
- `CGAL::Random_points_in_cube_d<Point_d>`
- `CGAL::Random_points_on_sphere_d<Point_d>`
- `CGAL::Random_points_in_triangle_mesh_2<Point_2, Triangulation>`
- `CGAL::Random_points_in_triangles_2<Point_2, Creator>`
- `CGAL::Random_points_in_triangle_mesh_3<TriangleMesh, VertexPointMap, Creator>`
- `CGAL::Random_points_on_graph_edges_3<EdgeListGraph, VertexPointMap, Creator>`
- `CGAL::Random_points_in_triangles_3<Point_3, Creator>`
- `CGAL::Random_points_in_triangle_soup_3<PointRange,Triangle, Creator>`
- `CGAL::Random_points_in_tetrahedral_mesh_3<C3t3>`
- `CGAL::Random_points_in_tetrahedral_mesh_boundary_3<C3t3>`

## 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=get_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.
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.
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.
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=get_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)`.
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.
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.
Random & | CGAL::get_default_random ()
| The global function `get_default_random()` returns the default random numbers generator used for the generator functions and classes.
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`.
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.
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`.
template<class RandomAccessIterator , class Size , class OutputIterator , class Random >
OutputIterator | CGAL::random_selection (RandomAccessIterator first, RandomAccessIterator last, Size n, OutputIterator result, Random &rnd=get_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.

## Variables
CGAL::Random | CGAL::default_random

## Function Documentation

## ◆ get_default_random()

Random & CGAL::get_default_random | ( |  | ) |

`#include <CGAL/Random.h>`

The global function `get_default_random()` returns the default random numbers generator used for the generator functions and classes.

The returned generator is thread local.

## ◆ perturb_points_2()

template<class ForwardIterator , class Creator >

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

`#include <CGAL/point_generators_2.h>`

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()`
  `std::random_shuffle()`

## ◆ points_on_cube_grid_3()

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

`#include <CGAL/point_generators_3.h>`

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

## ◆ points_on_cube_grid_d()

template<class OutputIterator , class Creator >

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

`#include <CGAL/point_generators_d.h>`

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

Examples
  Generator/grid_d.cpp.

## ◆ points_on_segment_2()

template<class P , class OutputIterator >

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

`#include <CGAL/point_generators_2.h>`

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

## ◆ points_on_square_grid_2()

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

`#include <CGAL/point_generators_2.h>`

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

## ◆ random_collinear_points_2()

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 = `get_default_random()`,
|  | Creator | creator = `Creator_uniform_2< Kernel_traits< P >::Kernel::RT, P >`
| ) |  |

`#include <CGAL/point_generators_2.h>`

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

## ◆ random_convex_hull_in_disc_2()

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

`#include <CGAL/random_convex_hull_in_disc_2.h>`

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

Example: Generator/random_convex_hull_2.cpp

Show / Hide
#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;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::random_convex_hull_in_disc_2
void 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 random points in a disc centered at the origi...
CGAL::area
Kernel::FT area(const CGAL::Point_2< Kernel > &p, const CGAL::Point_2< Kernel > &q, const CGAL::Point_2< Kernel > &r)
CGAL

## ◆ random_convex_set_2()

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

`#include <CGAL/random_convex_set_2.h>`

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.

Example: Generator/random_convex_set.cpp

Show / Hide
#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;
}
CGAL::Creator_uniform_2
CGAL::Point_2
CGAL::Random_points_in_square_2
The class Random_points_in_square_2 is an input iterator creating points uniformly distributed in a h...
Definition: point_generators_2.h:221
CGAL::random_convex_set_2
OutputIterator 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 do...

Examples
  Generator/random_convex_set.cpp.

## ◆ random_polygon_2()

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

`#include <CGAL/random_polygon_2.h>`

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>`

Preconditions

- The number of unique points in the first \( n\) points generated by `pg` is at least `3`.

- The unique points in the first \( n\) points generated by `pg` do not all lie on the same line.

  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.

Example: Generator/random_polygon.cpp

Show / Hide
#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;
std::cerr << "Seed = " << rand.get_seed() << std::endl;
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;
}
CGAL::Random
The class Random is a random numbers generator.
Definition: Random.h:33
CGAL::Random::get_seed
unsigned int get_seed() const
returns the seed used for initialization.
CGAL::Random::get_int
int get_int(int lower, int upper)
returns a random int from the interval [lower,upper).
Container
CGAL::random_polygon_2
OutputIterator 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.
CGAL::Simple_cartesian

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

## ◆ random_selection()

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

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

`#include <CGAL/random_selection.h>`

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

## Variable Documentation

## ◆ default_random

CGAL::Random CGAL::default_random
| extern

`#include <CGAL/Random.h>`

Deprecated:
  The variable `default_random` was the default random numbers generator used for the generator functions and classes. Deprecated. Use `get_default_random()` instead.