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, bool strict=false)
	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 coordinate range.
std::vector< point< long long > >	tgen::geometry::random_orthogonal_polygon (int n, long long min_coord, long long max_coord, bool strict=false)
	Generates a random orthogonal simple polygon.

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

Coordinate equality is exact, including for floating-point types.

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

Generates a random orthogonal (axis-aligned) simple polygon.

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

1164 1866
1164 1862
...

Example generated orthogonal 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 coordinate range.

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 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 counterclockwise order. When strict is true, the polygon is strictly convex.

Uses Valtr's classical construction: choose m distinct sorted x and y coordinates in [min_coord, max_coord] via tgen::distinct_range (with m = n when strict is false, and m > n when strict is true), build monotone signed edge components, shuffle the y-components, pair with the x-components, and sort by polar angle, then prefix-sum to obtain vertex coordinates. When strict is true, collinear boundary vertices are removed and the walk is subsampled to n vertices. The polygon is then translated by a random amount so it lies inside the requested box.

Exceptions

std::runtime_error

if the coordinate range is not large enough, or the prime-sized sampling pool would exceed INT_MAX elements.

Warning

When strict is true, the implementation retries a bounded number of times. Use a larger coordinate range if generation fails.
When strict is false, generation succeeds as long as max_coord - min_coord + 1 >= n.

Note

This operation is not uniformly random.

Time 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 7449 of file tgen.h.

random_orthogonal_polygon()

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

inline

Generates a random orthogonal simple polygon.

Parameters

n	Target number of boundary vertices.
min_coord	Minimum allowed coordinate on each axis.
max_coord	Maximum allowed coordinate on each axis.
strict	If true, every vertex turns 90 degrees (no three consecutive collinear vertices). If false, collinear vertices may appear on straight horizontal or vertical edges.

Precondition

n >= 4.

Returns

Vertices of a fully simple orthogonal polygon with axis-aligned edges, listed in counterclockwise order. When strict is false, the vertex count is exactly n. When strict is true, the count is at most n; for n <= 1000 it is often smaller because only boundary bumps are used; for n > 1000 it is near n.

The polygon is built in local steps that each preserve full simplicity (no edge crossings, overlaps, or boundary self-contact).

n <= 1000 bump on a square whose side is about sqrt(n):

• Start from a small axis-aligned square.
• Apply random inflate (outward tab, ~75% of accepted steps) and cut (inward notch, ~25%) operations on boundary subsegments. Each edit is accepted only if it keeps the boundary simple.
• When strict is true, remove collinear vertices.
• Loose: insert collinear vertices along straight edges until the count reaches n.
• Strict: stop once the count is at most n (often below n).

n > 1000 scale-up macro shape, then fill:

• Start from a small square (side between 8 and 64).
• Apply outward bumps only to obtain an irregular macro silhouette.
• Multiply all coordinates by an integer factor so the shape spans about (n+3)/4 per side.
• Loose: insert collinear vertices along edges until the count reaches n.
• Strict: insert outward depth-1 corrugation tabs along long edges until the count is near n (no collinear triples).

Finally, the polygon is translated into [min_coord, max_coord] (retrying up to 8 times if the bounding box is too large for the coordinate range) and cyclically shifted.

Exceptions

std::runtime_error

if the coordinate range is too small or no attempt fits inside the box.

Note

This operation is not uniformly random.

Time complexity

O(n^2) for n <= 1000;
O(n) otherwise.

Examples

auto poly = tgen::geometry::random_orthogonal_polygon(40, 0, 400);
std::cout << tgen::print(poly, '\n') << std::endl;
 
// Strict: only 90-degree corners.
auto strict_poly = tgen::geometry::random_orthogonal_polygon(40, 0, 400, true);

Definition at line 8175 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, or the prime-sized sampling pool would exceed INT_MAX elements.

Note

This operation is not uniformly random.

Warning

Modulo p, all generated points lie on one conic, an affine image of xy = 1. The random shears obscure the visual pattern but do not remove this structure. Combine this generator with other test families when that structure might make the tested problem easier.

Time 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 6998 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, bool strict = false )

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.
strict	If true, the vertex set has no three collinear points. If false, there might be collinear triplets and three consecutive collinear points in the polygon.

Precondition

n >= 3.

Returns

n distinct vertices listed in counterclockwise boundary order of a simple (non-self-intersecting) polygon. Coordinates lie in the inclusive square [min_coord, max_coord]^2.

When strict is true, the point set is built with random_points_general_position, othwerwise randomly generated. Points are polygonized by random_simple_polygon_through_points.

Exceptions

std::runtime_error

if the coordinate range is not large enough, or the prime-sized sampling pool would exceed INT_MAX elements.

Note

This operation is not uniformly random.

Time 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;
 
// Strict: no three collinear vertices.
auto strict_poly = tgen::geometry::random_simple_polygon(10, 0, 100, true);

Definition at line 8153 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 counterclockwise 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.

Time complexity

O(|points| log|points|) expected for every valid fixed input, including inputs with collinear triples. The expectation is over the algorithm's random choices; the input need not be randomly distributed. O(|points|^2) worst case.

The expected bound follows by tracking each point while it remains a non-endpoint point. Even with collinear points and discrete split weights, within at most two recursive splits there is a constant probability that its subproblem shrinks by a constant factor or terminates. Each point is therefore processed in O(log n) calls in expectation. Sorting the entirely collinear terminal subproblems costs O(n log n) in total, so the overall expected work is O(n log n), where n is the input size.

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 7517 of file tgen.h.