random_convex_set

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

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

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,

The default traits class Default_traits is Random_convex_set_traits_2. .

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

Next: random_polygon_2