CGAL::random_convex_set_2

Definition

The function random_convex_set_2 computes a random convex planar point set of given size where the points are drawn from a specific domain.

#include <CGAL/random_convex_set_2.h>

template < class OutputIterator, class PointGenerator, class Traits >
OutputIterator
random_convex_set_2 (
std::size_t n,
OutputIterator o,
PointGenerator pg,
Traits t = Default_traits)
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 3.

Requirements

  1. PointGenerator is a model of the concept PointGenerator
  2. Traits is a model of the concept RandomConvexSetTraits_2
  3. Point_generator::value_type is equivalent to Traits::Point_2 and OutputIterator::value_type.
  4. if Traits is not specified, Point_generator::value_type must be Point_2< R > for some representation class R,

The default traits class Default_traits is Random_convex_set_traits_2. .

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 [Sch96] and has a worst case running time of O(r n + n 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: examples/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;
}