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-24a
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 to achieve random permutations for otherwise regular generators ( e.g., points on a grid or segment).

Classified Reference Pages

Concepts

Functions

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_tetrahedral_mesh_3<C3t3>
CGAL::Random_points_in_square_2<Point_2, Creator>
CGAL::Random_points_on_circle_2<Point_2, Creator>
CGAL::Random_points_in_triangle_mesh_2<Point_2, Triangulation>
CGAL::Random_points_in_triangle_mesh_3<Point_3, Mesh>
CGAL::Random_points_in_tetrahedral_mesh_boundary_3<C3t3>
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=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(); 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\).

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

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

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

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.

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

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.

Classified Reference Pages

Concepts

Functions

Classes

Traits Class

Modules

Classes

Functions

Variables

Function Documentation

◆ get_default_random()

◆ perturb_points_2()

◆ points_on_cube_grid_3()

◆ points_on_cube_grid_d()

◆ points_on_segment_2()

◆ points_on_square_grid_2()

◆ random_collinear_points_2()

◆ random_convex_hull_in_disc_2()

◆ random_convex_set_2()

◆ random_polygon_2()

◆ random_selection()

Variable Documentation

◆ default_random