\( \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.8.1 - Geometric Object Generators
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Classes | Functions | Variables
Geometric Object Generators Reference

dice.png
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-16a
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

Functions

Variables

Classes

Traits Class

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

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

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