\( \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.14 - Geometric Object Generators
User Manual

Authors
Pedro M. M. de Castro, Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, Sven Schönherr, Alexandru Tifrea, and Maxime Gimeno

Introduction

A variety of generators for geometric objects are provided in CGAL. They are useful as synthetic test data sets, e.g. for testing algorithms on degenerate object sets and for performance analysis.

Two kinds of point generators are provided: first, random point generators and second deterministic point generators. Most random point generators and a few deterministic point generators are provided as input iterators. The input iterators model an infinite sequence of points. The function CGAL::copy_n() can be used to copy a finite sequence. The iterator adaptor Counting_iterator can be used to create finite iterator ranges. Other generators are provided as functions that write to output iterators. Further functions add degeneracies or random perturbations.

In 2D, we provide input iterators to generate random points in a disc (Random_points_in_disc_2), in a square (Random_points_in_square_2), on a circle (Random_points_on_circle_2), on a segment (Random_points_on_segment), in a square (Random_points_on_square_2), in a triangle (Random_points_in_triangle_2), in a range of triangles (Random_points_in_triangles_2), and in a triangle mesh (Random_points_in_triangle_mesh_2). For generating grid points we provide three functions, points_on_segment_2(), points_on_square_grid_2() that write to output iterators and an input iterator Points_on_segment_2.

For 3D points, input iterators are provided for random points uniformly distributed in a sphere (Random_points_in_sphere_3), in a triangle (Random_points_in_triangle_3), in a range of triangles (Random_points_in_triangles_3), in a tetrahedron (Random_points_in_tetrahedron_3), in a cube (Random_points_in_cube_3), on the boundary of a sphere (Random_points_on_sphere_3), in a triangle mesh (Random_points_in_triangle_mesh_3), in a tetrahedron mesh (Random_points_in_tetrahedral_mesh_3), and on the boundary of a tetrahedron mesh (Random_points_in_tetrahedral_mesh_boundary_3). For generating 3D grid points, we provide the function points_on_cube_grid_3() that writes to an output iterator.

For higher dimensions, input iterators are provided for random points uniformly distributed in a d-dimensional cube (Random_points_in_cube_d) or d-dimensional ball (Random_points_in_ball_d) or on the boundary of a sphere (Random_points_on_sphere_d). For generating grid points, we provide the function points_on_cube_grid_d() that writes to an output iterator.

We also provide two functions for generating more complex geometric objects. The function random_convex_set_2() computes a random convex planar point set of a given size where the points are drawn from a specific domain and random_polygon_2() generates a random simple polygon from points drawn from a specific domain. The function random_convex_hull_in_disc_2() computes a random polygon as a convex hull from uniformly generated random points in a disc.

Random Perturbations

Degenerate input sets like grid points can be randomly perturbed by a small amount to produce quasi-degenerate test sets. This challenges numerical stability of algorithms using inexact arithmetic and exact predicates to compute the sign of expressions slightly off from zero. For this the function perturb_points_2() is provided.

Adding Degeneracies

For a given point set certain kinds of degeneracies can be produced by adding new points. The random_selection() function is useful for generating multiple copies of identical points. The function random_collinear_points_2() adds collinearities to a point set.

Support Functions and Classes for Generators

The function random_selection() 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 class Combination_enumerator<CombinationElement> is used to enumerate all fixed-size combinations (subsets) of a range of elements. It is useful in the context of high-dimensional triangulations, e.g., for enumerating the faces of a simplex.

Example Generating Degenerate Point Sets

We want to generate a test set of 1000 points, where 60% are chosen randomly in a small disc, 20% are from a larger grid, 10% are duplicates points, and 10% collinear points. A random shuffle removes the construction order from the test set. See Figure 99.1 for the example output.


File Generator/random_degenerate_point_set.cpp

#include <CGAL/Simple_cartesian.h>
#include <cassert>
#include <vector>
#include <algorithm>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
#include <CGAL/random_selection.h>
using namespace CGAL;
typedef R::Point_2 Point;
typedef std::vector<Point> Vector;
int main() {
// Create test point set. Prepare a vector for 1000 points.
Vector points;
points.reserve(1000);
// Create 600 points within a disc of radius 150.
CGAL::cpp11::copy_n( g, 600, std::back_inserter(points));
// Create 200 points from a 15 x 15 grid.
points_on_square_grid_2( 250.0, 200, std::back_inserter(points),Creator());
// Select 100 points randomly and append them at the end of
// the current vector of points.
random_selection( points.begin(), points.end(), 100,
std::back_inserter(points));
// Create 100 points that are collinear to two randomly chosen
// points and append them to the current vector of points.
random_collinear_points_2( points.begin(), points.end(), 100,
std::back_inserter( points));
// Check that we have really created 1000 points.
assert( points.size() == 1000);
// Use a random permutation to hide the creation history
// of the point set.
CGAL::cpp98::random_shuffle( points.begin(), points.end());
// Check range of values.
for ( Vector::iterator i = points.begin(); i != points.end(); i++){
assert( i->x() <= 251);
assert( i->x() >= -251);
assert( i->y() <= 251);
assert( i->y() >= -251);
}
return 0;
}

generators_prog1.png
Figure 99.1 Output of example program for point generators.

Example Generating Grid Points

The second example demonstrates the point generators with integer points. Floating point arithmetic is sufficient to produce regular integer grids. See Figure 99.2 for the example output.


File Generator/random_grid.cpp

#include <CGAL/Simple_cartesian.h>
#include <cassert>
#include <vector>
#include <algorithm>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
using namespace CGAL;
typedef K::Point_2 Point;
int main() {
// Create test point set. Prepare a vector for 400 points.
std::vector<Point> points;
points.reserve(400);
// Create 250 points from a 16 x 16 grid. Note that the double
// arithmetic _is_ sufficient to produce exact integer grid points.
// The distance between neighbors is 34 pixel = 510 / 15.
points_on_square_grid_2( 255.0, 250, std::back_inserter(points),Creator());
// Lower, left corner.
assert( points[0].x() == -255);
assert( points[0].y() == -255);
// Upper, right corner. Note that 6 points are missing to fill the grid.
assert( points[249].x() == 255 - 6 * 34);
assert( points[249].y() == 255);
// Create 250 points within a disc of radius 150.
CGAL::cpp11::copy_n( g, 250, std::back_inserter(points));
// Check that we have really created 500 points.
assert( points.size() == 500);
return 0;
}

generators_prog2.png
Figure 99.2 Output of example program for point generators working

Example Generating Random Point Sets On a Triangle Mesh

The following example demonstrates the use of the random point generator on a triangle mesh. We want to generate 100 points uniformly chosen on a Polyhedron_3. See Figure 99.3
File Generator/random_points_on_triangle_mesh_3.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/point_generators_3.h>
#include <iostream>
#include <fstream>
using namespace CGAL;
typedef CGAL::Polyhedron_3<K> Polyhedron;
typedef K::Point_3 Point;
typedef K::FT FT;
int main()
{
// Generated points are in that vector
std::vector<Point> points;
// Create input polyhedron
Polyhedron polyhedron;
polyhedron.make_tetrahedron(Point(-1,0,0), Point(0,1,0), Point(1,0,0), Point(0,0,-1));
// Create the generator, input is the Polyhedron polyhedron
g(polyhedron);
// Get 100 random points in cdt
CGAL::cpp11::copy_n(g, 100, std::back_inserter(points));
// Check that we have really created 100 points.
assert( points.size() == 100);
// print the first point that was generated
std::cout << points[0] << std::endl;
return 0;
}

generator_mesh_3.png
Figure 99.3 Output of example program for point generator on a triangle mesh

Examples Generating Segments

The following two examples illustrate the use of the generic functions from Section Generic Algorithms like Join_input_iterator_2 to generate composed objects from other generators - here two-dimensional segments from two point generators.

We want to generate a test set of 200 segments, where one endpoint is chosen randomly from a horizontal segment of length 200, and the other endpoint is chosen randomly from a circle of radius 250. See Figure 99.4 for the example output.


File Generator/random_segments1.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <cassert>
#include <vector>
#include <algorithm>
#include <CGAL/Point_2.h>
#include <CGAL/Segment_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/function_objects.h>
#include <CGAL/Join_input_iterator.h>
#include <CGAL/algorithm.h>
using namespace CGAL;
typedef K::Point_2 Point;
typedef K::Segment_2 Segment;
typedef std::vector<Segment> Vector;
int main() {
// Create test segment set. Prepare a vector for 200 segments.
Vector segs;
segs.reserve(200);
// Prepare point generator for the horizontal segment, length 200.
P1 p1( Point(-100,0), Point(100,0));
// Prepare point generator for random points on circle, radius 250.
P2 p2( 250);
// Create 200 segments.
Seg_iterator g( p1, p2);
CGAL::cpp11::copy_n( g, 200, std::back_inserter(segs));
assert( segs.size() == 200);
for ( Vector::iterator i = segs.begin(); i != segs.end(); i++){
assert( i->source().x() <= 100);
assert( i->source().x() >= -100);
assert( i->source().y() == 0);
assert( i->target().x() * i->target().x() +
i->target().y() * i->target().y() <= 251*251);
assert( i->target().x() * i->target().x() +
i->target().y() * i->target().y() >= 249*249);
}
return 0;
}

Segment_generator_prog1.png
Figure 99.4 Output of example program for the generic segment generator.

The second example generates a regular structure of 100 segments; see Figure 99.5 for the example output. It uses the Points_on_segment_2 iterator, Join_input_iterator_2 and Counting_iterator to avoid any intermediate storage of the generated objects until they are used.


File Generator/random_segments2.cpp

// CGAL example program for the generic segment generator
// using precomputed point locations.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <algorithm>
#include <vector>
#include <CGAL/point_generators_2.h>
#include <CGAL/function_objects.h>
#include <CGAL/Join_input_iterator.h>
#include <CGAL/Counting_iterator.h>
using namespace CGAL;
typedef K::Point_2 Point;
typedef K::Segment_2 Segment;
typedef std::vector<Segment> Vector;
int main() {
// Create test segment set. Prepare a vector for 100 segments.
Vector segs;
segs.reserve(100);
// A horizontal like fan.
PG p1( Point(-250, -50), Point(-250, 50),50); // Point generator.
PG p2( Point( 250,-250), Point( 250,250),50);
Segm_iterator t1( p1, p2); // Segment generator.
Count_iterator t1_begin( t1); // Finite range.
Count_iterator t1_end( t1, 50);
std::copy( t1_begin, t1_end, std::back_inserter(segs));
// A vertical like fan.
PG p3( Point( -50,-250), Point( 50,-250),50);
PG p4( Point(-250, 250), Point( 250, 250),50);
Segm_iterator t2( p3, p4);
Count_iterator t2_begin( t2);
Count_iterator t2_end( t2, 50);
std::copy( t2_begin, t2_end, std::back_inserter(segs));
CGAL_assertion( segs.size() == 100);
for ( Vector::iterator i = segs.begin(); i != segs.end(); i++){
CGAL_assertion( i->source().x() <= 250);
CGAL_assertion( i->source().x() >= -250);
CGAL_assertion( i->source().y() <= 250);
CGAL_assertion( i->source().y() >= -250);
CGAL_assertion( i->target().x() <= 250);
CGAL_assertion( i->target().x() >= -250);
CGAL_assertion( i->target().y() <= 250);
CGAL_assertion( i->target().y() >= -250);
}
return 0;
}

Segment_generator_prog2.png
Figure 99.5 Output of example program for the generic segment generator using pre-computed point locations.

Example Generating Point Sets in d Dimensions

The following example generates points inside a cube in dimension 5 (examples for ball and sphere are available in the example directory) :


File Generator/cube_d.cpp

#include <iostream>
#include <vector>
#include <CGAL/Cartesian_d.h>
#include <CGAL/point_generators_d.h>
typedef CGAL::Cartesian_d<double> Kd;
typedef Kd::Point_d Point;
int main ()
{
int nb_points = 10;
int dim =5;
double size = 100.0;
std::cout << "Generating "<<nb_points<<" random points in a cube in "
<<dim<<"D, coordinates from "<<-size<<" to "<<size<<std::endl;
std::vector<Point> v;
v.reserve (nb_points);
for (int i = 0; i < nb_points; ++i) v.push_back (*gen++);
for (int i = 0; i < nb_points; ++i) std::cout<<" "<<v[i]<<std::endl;
return 0;
}

The output of this example looks like:

Generating 10 random points in a cube in 5D, coordinates from -100 to 100
5 32.9521 26.0403 59.3979 -99.2553 15.5102 
5 80.3731 30.809 7.32491 -90.2544 94.5635 
5 -71.3412 -31.933 -98.0734 79.6493 66.6104 
5 -78.5065 -58.2397 -33.9096 81.2196 57.2512 
5 21.4093 26.7661 57.6083 23.4958 93.1047 
5 10.5895 -21.8914 70.9726 36.756 -42.2667 
5 23.9813 54.4519 -26.0894 -85.18 -21.0775 
5 -48.7499 59.9873 6.22335 -4.16011 81.0727 
5 -11.6615 5.53147 -32.6578 -79.9283 44.5679 
5 53.0183 78.3228 -28.5665 83.3503 68.0482 

Next example generates grid points in dimension d=4. Since the required number of points, 20 is between \( 2^d\) and \( 3^d\) the supporting grid has \( 3\times 3\times 3\times 3\) points. Since the size parameter is 5, the coordinates are in \( \{-5, 0, 5\}\), but since the number of points verifies \( 20\leq 3^{d-1}\), all generated points have the same last coordinate \( -5\).


File Generator/grid_d.cpp

#include <iostream>
#include <vector>
#include <CGAL/Cartesian_d.h>
#include <CGAL/point_generators_d.h>
#include <CGAL/constructions_d.h>
typedef CGAL::Cartesian_d<double> Kd;
typedef Kd::Point_d Point;
<std::vector<double>::iterator, Point> Creator_d;
int main ()
{
int nb_points = 20;
int dim = 4;
double size = 5.0;
std::cout << "Generating "<<nb_points<<" grid points in "
<<dim<<"D" << std::endl;
std::vector<Point> v;
v.reserve(nb_points);
CGAL::points_on_cube_grid_d (dim, size, (std::size_t) nb_points,
std::back_inserter(v), Creator_d(dim) );
for (int i = 0; i < nb_points; ++i) std::cout<<" "<<v[i]<<std::endl;
return 0;
}

The output of previous example corresponds to the points of this figure depicted in red or pink (pink points are "inside" the cube). The output is:

Generating 20 grid points in 4D
4 -5 -5 -5 -5 
4 0 -5 -5 -5 
4 5 -5 -5 -5 
4 -5 0 -5 -5 
4 0 0 -5 -5 
4 5 0 -5 -5 
4 -5 5 -5 -5 
4 0 5 -5 -5 
4 5 5 -5 -5 
4 -5 -5 0 -5 
4 0 -5 0 -5 
4 5 -5 0 -5 
4 -5 0 0 -5 
4 0 0 0 -5 
4 5 0 0 -5 
4 -5 5 0 -5 
4 0 5 0 -5 
4 5 5 0 -5 
4 -5 -5 5 -5 
4 0 -5 5 -5 
hypergrid.png

Example Generating Combinations

From a Range of Integers

The following example enumerates and outputs all subsets of 3 elements from the range \( [10, 15]\). Accordingly, it outputs \( \frac{6!}{3! 3!}=20\) triples.


File Generator/combination_enumerator.cpp

#include "CGAL/Combination_enumerator.h"
#include <iostream>
using namespace std;
int main()
{
unsigned int n(0);
const int k(3), first(10), last(15);
cout << "Taking " << k << " distinct integers in the range [" <<
first << ", " << last << "]:";
CGAL::Combination_enumerator<int> combi(k, first, last + 1);
while( ! combi.finished() ) {
cout << " {";
for(int i = 0; i < k; ++i) {
cout << combi[i];
if( i < k - 1 )
cout << ' ';
}
cout << '}';
++n;
++combi;
}
cout << endl << "Enumerated " << n << " combinations." << endl;
return EXIT_SUCCESS;
}

The output of this example is:

Taking 3 distinct integers in the range [10, 15]: {10 11 12} {10 11 13} {10 11 14}
{10 11 15} {10 12 13} {10 12 14} {10 12 15} {10 13 14} {10 13 15} {10 14 15}
{11 12 13} {11 12 14} {11 12 15} {11 13 14} {11 13 15} {11 14 15} {12 13 14}
{12 13 15} {12 14 15} {13 14 15}
Enumerated 20 combinations.

From an Array of Strings

The following example generates all pairs of names from a set of names stored in an array of strings.


File Generator/name_pairs.cpp

#include "CGAL/Combination_enumerator.h"
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<string> names;
names.push_back("Sun"); names.push_back("Shannon");
names.push_back("Hurley"); names.push_back("Sawyer");
names.push_back("Kate"); names.push_back("Claire");
names.push_back("John"); names.push_back("Jack");
combi(2, names.begin(), names.end());
while( ! combi.finished() ) {
cout << " {" << *combi[0] << ' ' << *combi[1] << '}';
++combi;
}
cout << endl;
return EXIT_SUCCESS;
}

Design and Implementation History

Lutz Kettner coded generators in 2D and 3D For points in and on sphere, points are generated in a cube up to the moment the point is inside the sphere, then it is normalized to go on the boundary if needed.

Sven Schönherr implemented the Random class.

Michael Hoffmann coded the random convex polygon,

Geert-Jan Giezeman and Susan Hert coded the random simple polygon.

Olivier Devillers coded generators in high dimensions. For points in ball and on sphere, points are generated on a sphere/ball boundary as a product of normal distributions, then it is normalized. If needed a random radius (with relevant distribution) is used to put the point inside the ball.

Remy Thomasse coded the random convex hull in a disc.

During Google Summer of Code 2013, Pedro M. M. de Castro and Alexandru Tifrea coded generators for points in triangle (2D and 3D) and in tetrahedra (3D). Basically, in order to generate a random point in a \(N\)-simplex (a triangle for \(N = 2\), and tetrahedron for \(N = 3\)), we generate numbers \(a_1,a_2,\ldots,a_N\) identically and independently uniformly distributed in \((0,1)\), we sort them, we let \(a_0 = 0\) and \(a_{N+1} = 1\), and then \(a_{i+1}-a_i\), for \(i = 1,\ldots,N\) becomes its barycentric coordinates with respect to the simplex.

Maxime Gimemo introduced the random generators on 2D and 3D triangle meshes.