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

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

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.

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.

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 6872 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 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 large n, it can be much smaller because boundary edits are capped to avoid quadratic running time.

Generation

The polygon starts as a small axis-aligned square. The implementation then applies local boundary edits inspired by inflate/cut operations:

• Inflate (outward tab): (~75% of steps) a rectangular protrusion is spliced onto a boundary subsegment, growing the shape outward.
• Cut (inward notch): (~25% of steps) a rectangular bite is taken out of the boundary, creating bays and concavities.

Each step picks a boundary edge (favoring longer segments and edges that were not edited recently), chooses a subsegment and depth, then splices the rectangle if validation passes. When strict is true, collinear vertices are removed.

Exceptions

std::runtime_error

if the coordinate range is too small.

Note

This operation is not uniformly random.

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 7468 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, 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.

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

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

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