Geometry

Geometry utilities. More...

Classes
struct	tgen::geometry::point< T >
	Point on the plane. More...

Functions
std::vector< point< long long > >	tgen::geometry::random_points_general_position (int n, long long min_coord, long long max_coord)
	Generates random points in general position inside a coordinate box.
std::vector< point< long long > >	tgen::geometry::random_simple_polygon_through_points (const std::vector< point< long long > > &points)
	Generates a random simple polygon through given points.
std::vector< point< long long > >	tgen::geometry::random_simple_polygon (int n, long long min_coord, long long max_coord)
	Generates a random simple polygon given coordinate range.
std::vector< point< long long > >	tgen::geometry::random_convex_polygon (int n, long long min_coord, long long max_coord, bool strict=false)
	Generates a random convex polygon with given bounding box.

Detailed Description

Geometry utilities.

Examples

Vector operations on integer coordinates.

tgen::geometry::point<int> a(1, 2), b(3, 4);
std::cout << a + b << std::endl;
std::cout << (a * b) << " " << (a ^ b) << std::endl;

4 6
11 -2

Floating-point coordinates use epsilon-based equality (1e-9).

tgen::geometry::point<double> p(1.5, 2.5);
std::cout << p << std::endl;

1.5 2.5

Generates points in general position (no three collinear) inside a box.

auto pts = tgen::geometry::random_points_general_position(5000, 0, 50000);
std::cout << tgen::print(pts, '\n') << std::endl;

18815 25522
19859 26244
...

Example generated point set

Generates convex polygon.

auto pts = tgen::geometry::random_convex_polygon(150, 0, 1500);
std::cout << tgen::print(pts, '\n') << std::endl;

1433 1182
1428 1190
...

Example generated polygon

Generates a simple polygon.

auto poly = tgen::geometry::random_simple_polygon(200, 0, 2000);
std::cout << tgen::print(poly, '\n') << std::endl;

842 368
847 379
...

Example generated polygon

Simple polygon through a grid of points.

std::vector<tgen::geometry::point<long long>> pts;
for (int y = 0; y < 10; ++y)
    for (int x = 0; x < 10; ++x)
        pts.emplace_back(x, y);
auto poly = tgen::geometry::random_simple_polygon_through_points(pts);
std::cout << tgen::print(poly, '\n') << std::endl;

0 1
0 2
...

Example grid polygon

Function Documentation

random_convex_polygon()

std::vector< point< long long > > tgen::geometry::random_convex_polygon ( int n, long long min_coord, long long max_coord, bool strict = false )

inline

Generates a random convex polygon with given bounding box.

Parameters

n	Number of vertices.
min_coord	Minimum allowed coordinate on each axis.
max_coord	Maximum allowed coordinate on each axis.
strict	If true, the polygon is strictly convex. If false, collinear boundary vertices may occur.

Precondition

n >= 3.

Returns

n distinct vertices of a convex polygon with integer coordinates in the inclusive square [min_coord, max_coord]^2, listed in boundary order (clockwise or counterclockwise). The polygon touches all four sides of that square (its axis-aligned bounding box equals the requested box). When strict is true, the polygon is strictly convex.

Uses Valtr's classical construction: choose n distinct sorted x and y coordinates spanning [0, width] via tgen::distinct_range, build monotone signed edge components, shuffle the y-components, pair with the x-components, and sort by polar angle without floating point, then prefix-sum and translate so the bouding box minimum is min_coord on each axis. The grid uses endpoints 0 and width, so the polygon span is exactly width on each axis and fills the box after translation.

Exceptions

std::runtime_error

if the coordinate range is not large enough.

Warning

When strict is true, the implementation retries y-component shuffles a bounded number of times (fewer when n is large or the coordinate range is tight). Fails if no strictly convex polygon is found; use a larger coordinate range in that case.
When strict is false, a convex polygon is always found as long as max_coord - min_coord >= n - 1.

Note

This operation is not uniformly random.

Complexity

O(n log n).

Examples

auto poly = tgen::geometry::random_convex_polygon(10, 0, 100);
std::cout << tgen::print(poly, '\n') << std::endl;

Definition at line 6774 of file tgen.h.

random_points_general_position()

std::vector< point< long long > > tgen::geometry::random_points_general_position ( int n, long long min_coord, long long max_coord )

inline

Generates random points in general position inside a coordinate box.

Parameters

n	Number of points to generate.
min_coord	Minimum allowed coordinate on each axis.
max_coord	Maximum allowed coordinate on each axis.

Returns

n distinct point<long long> values with integer coordinates in the inclusive square [min_coord, max_coord]^2 such that no three points are collinear.

The construction samples n distinct values (x, x^-1) from F_p then applies several random invertible shears over F_p, then translates the result into [min_coord, max_coord]^2. Affine maps preserve (non-)collinearity, and the graph of inversion over F_p meets any line in at most two points.

Exceptions

std::runtime_error

if the coordinate range is not large enough.

Note

This operation is not uniformly random.

Complexity

O(n).

Examples

std::vector<tgen::geometry::point<long long>> pts = tgen::geometry::random_points_general_position(10, 0, 100);
std::cout << tgen::print(pts, '\n') << std::endl;

Definition at line 6474 of file tgen.h.

random_simple_polygon()

std::vector< point< long long > > tgen::geometry::random_simple_polygon ( int n, long long min_coord, long long max_coord )

inline

Generates a random simple polygon given coordinate range.

Parameters

n	Number of vertices to generate.
min_coord	Minimum allowed coordinate on each axis.
max_coord	Maximum allowed coordinate on each axis.

Precondition

n >= 3.

Returns

n distinct vertices listed in boundary order of a simple (non-self-intersecting) polygon. Coordinates lie in the inclusive square [min_coord, max_coord]^2. There will be no 3 collinear points.

The point set is built with random_points_general_position, then polygonized by random_simple_polygon_through_points.

Exceptions

std::runtime_error

if the coordinate range is not large enough for random_points_general_position.

Note

This operation is not uniformly random.

Complexity

O(n log n) expected.

Examples

std::vector<tgen::geometry::point<long long>> poly = tgen::geometry::random_simple_polygon(10, 0, 100);
std::cout << tgen::print(poly, '\n') << std::endl;

Definition at line 6960 of file tgen.h.

random_simple_polygon_through_points()

std::vector< point< long long > > tgen::geometry::random_simple_polygon_through_points ( const std::vector< point< long long > > & points )

inline

Generates a random simple polygon through given points.

Parameters

points

Distinct points.

Precondition

points.size() >= 3, all points are distinct, and they are not all collinear.

Returns

The same points listed in boundary order of a simple (non-self-intersecting) polygon.

Uses a randomized divide-and-conquer Hamiltonian-path construction on the leftmost and rightmost vertices.

Note

This operation is not uniformly random.

Complexity

O(|points| log|points|) expected (if points are "random"), O(|points|^2) worst case.

Examples

auto pts = tgen::geometry::random_points_general_position(10, 0, 100);
auto poly = tgen::geometry::random_simple_polygon_through_points(pts);
std::cout << tgen::print(poly, '\n') << std::endl;

Definition at line 6888 of file tgen.h.