CGAL 4.11.3 - Geometric Object 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).
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()
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>
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. 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=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) . 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... | |
Random & | CGAL::get_default_random () |
The global function get_default_random() returns the default random numbers generator used for the generator functions and classes. 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=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. More... | |
Variables | |
CGAL::Random | CGAL::default_random |
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... | |
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.
1 <= k <= beyond - first
#include <CGAL/Combination_enumerator.h>
Random& CGAL::get_default_random | ( | ) |
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.
#include <CGAL/Random.h>
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>
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>
const CombinationElement& CGAL::Combination_enumerator< CombinationElement >::operator[] | ( | int | i) |
Returns the i
-th element of the current combination.
0 <= i < number_of_elements()
#include <CGAL/Combination_enumerator.h>
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.
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.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.to_double((*first).x())
and to_double((*first).y())
must result in the respective coordinate values.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>
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.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.#include <CGAL/point_generators_3.h>
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}\).
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\). OutputIterator
must accept values of type P
. #include <CGAL/point_generators_d.h>
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.
CGAL::points_on_segment_2()
CGAL::points_on_square_grid_2()
CGAL::random_collinear_points_2()
#include <CGAL/point_generators_2.h>
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.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.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>
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)
.
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.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.to_double((*first).x())
and to_double((*first).y())
must result in the respective coordinate values.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>
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))\).
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
.OutputIterator
must accept values of type Traits::Point_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/random_convex_hull_in_disc_2.h>
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.
Requirements
PointGenerator
is a model of the concept PointGeneratorTraits
is a model of the concept RandomConvexSetTraits_2Point_generator::value_type
is equivalent to Traits::Point_2
and OutputIterator::value_type
.Traits
is not specified, Point_generator::value_type
must be Point_2< R >
for some representation class R
,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/random_convex_set_2.h>
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_2PointGenerator::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.
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/random_polygon_2.h>
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.
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.
CGAL::perturb_points_2()
#include <CGAL/random_selection.h>
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>
CGAL::Random CGAL::default_random |
default_random
was the default random numbers generator used for the generator functions and classes. Deprecated. Use get_default_random()
instead. #include <CGAL/Random.h>