Algorithms

Classical computational-geometry algorithms.

Convex hull

class cgeom.algorithms._convexhull.ConvexHull(points)

Bases: object

Class to find the convex hull of a set of points using the Gift Wrapping algorithm””

Reference:

R.A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Information Processing Letters, Volume 2, Issue 1, 1973, Pages 18-21, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(73)90020-3.

points

Array of points

Type:

np.array

__init__(points)

Initialize the convex hull with a set of 2D points.

Parameters:

points – Collection of 2D points as a list, tuple, or numpy array with shape (n, 2).

Raises:

pydantic.ValidationError – If fewer than 3 points, all collinear, non-numeric, or wrong shape.

find_low_right()

Find the point with the lowest y-coordinate (rightmost if tied).

Returns:

list – The [x, y] coordinates of the lowest-rightmost point.

low_angle(b, c)

Find the point that makes the smallest angle from vector c->b.

Used by the Gift Wrapping algorithm to select the next hull vertex.

Parameters:

• b – Current point on the hull boundary.

• c – Previous point (defines the reference direction).

Returns:

list – The [x, y] coordinates of the point with the lowest angle.

convex_hull()

Compute the convex hull using the Gift Wrapping (Jarvis march) algorithm.

Returns:

list[list] – Ordered list of [x, y] vertices forming the convex hull.

plot(title='Convex Hull for a set of points')

Deprecated: use cgeom.visualization.plot_convex_hull() instead.

get_indexes()

Get the indices of the convex hull vertices in the original points array.

Returns:

list[int] – Indices into self.points for each hull vertex.

Delaunay triangulation

class cgeom.algorithms._delaunay.DelaunayTriangulation(points)

Bases: object

Delaunay triangulation of a 2D point set using the Bowyer-Watson algorithm.

points

Array of input points with shape (n, 2).

Type:

np.ndarray

__init__(points)

Initialize with a set of 2D points.

Parameters:

points – Collection of 2D points as a list, tuple, or numpy array with shape (n, 2).

Raises:

pydantic.ValidationError – If fewer than 3 points, all collinear, non-numeric, or wrong shape.

triangulate()

Compute the Delaunay triangulation using Bowyer-Watson.

Returns:

list[list[int]] –

List of triangles, each a sorted list of three

point indices into self.points.

get_triangles()

Return triangles as coordinate triples.

Returns:

list[list[list[float]]] – Each triangle is [[x,y], [x,y], [x,y]].

get_edges()

Return unique edges of the triangulation.

Returns:

list[list[list[float]]] – Each edge is [[x1,y1], [x2,y2]].

get_circumcircles()

Return the circumcircle for each triangle.

Returns:

list[list] – Each entry is [[cx, cy], radius].

plot(title='Delaunay Triangulation')

Deprecated: use cgeom.visualization.plot_delaunay() instead.

Voronoi diagram

class cgeom.algorithms._voronoi.VoronoiDiagram(data)

Bases: object

Construct a Voronoi diagram for a set of 2D sites using incremental insertion.

data

Array of site coordinates with shape (n, 2).

Type:

np.ndarray

cells

List of Voronoi cells, each containing a site and its edges.

Type:

list

__init__(data)

Initialize the Voronoi diagram with a set of 2D sites.

Parameters:

data – Collection of 2D points as a list, tuple, or numpy array with shape (n, 2). The first two points must have different y-coordinates.

Raises:

pydantic.ValidationError – If fewer than 2 points, first two share a y-coordinate, non-numeric, or wrong shape.

search_for_cell(point)

Find the index of the Voronoi cell whose site is nearest to point.

Parameters:

point – A 2D coordinate [x, y].

Returns:

int – Index of the nearest cell in self.cells.

search_for_cell_by_edge(edge_ref, origin_cell)

Find a neighbouring cell that shares the given edge.

Parameters:

• edge_ref – Reference edge as [[x1, y1, ...], [x2, y2, ...]].

• origin_cell – Index of the cell to exclude from the search.

Returns:

int – Index of the neighbouring cell that contains edge_ref.

adapt_cell(visited_cell, edge_added, point_added)

Update an existing cell after a new site is inserted.

Clips or removes edges that are closer to point_added than to the cell’s own site, and appends the new bisector edge.

Parameters:

• visited_cell – Index of the cell to update.

• edge_added – The new bisector edge to insert.

• point_added – The newly added site coordinates.

make_edge(cell, p)

Compute the bisector edge between a cell’s site and a new point.

The bisector is intersected with the cell’s existing edges to determine its extent.

Parameters:

• cell – Index of the existing cell.

• p – The new point [x, y].

Returns:

tuple –

(edge_endpoints, neighbour_indices) where

edge_endpoints is a list of intersection points and neighbour_indices lists the adjacent cells crossed.

construct_cell(cell, p)

Construct a new Voronoi cell for point p by traversing neighbours.

Parameters:

• cell – Index of the starting cell (the one containing p).

• p – The new site coordinates.

Returns:

list – A cell entry [site, edges] for the new site.

build_voronoi_diagram()

Build the full Voronoi diagram by incrementally inserting each site.

Returns:

list – The list of Voronoi cells (also stored in self.cells).

plot_voronoi(cells)

Deprecated: use cgeom.visualization.plot_voronoi() instead.

Minimum enclosing circle

class cgeom.algorithms._mincircle.MinimumCircle

Bases: object

Find the minimum enclosing circle for a set of 2D points.

Provides both an exact randomized incremental algorithm and a faster heuristic approximation.

static minimum_circle_heuristic(num_points)

Heuristic algorithm to find the minimum circle that contains all the points :param num_points: list of points :return: circle

static randomized_permutation(num_points)

Randomized permutation of the points :param num_points: list of points :return: list of points

static minimum_circle_points(num_points, q1, q2)

Compute the minimum circle that contains the points in num_points and the points q1 and q2 :param num_points: list of points :param q1: point :param q2: point :return: circle

static min_circle_with_point(num_points, q)

Compute the minimum circle that contains the points in num_points and the point q :param num_points: list of points :param q: point :return: circle

minimum_circle(num_points)

Compute the minimum circle that contains all the points in num_points :param num_points: list of points :return: circle

plot_min_circle_random(sizes, path=None, show=False)

Deprecated: use cgeom.visualization.plot_min_circle_random() instead.

plot_min_circle(data, path=None, show=False)

Deprecated: use cgeom.visualization.plot_min_circle() instead.

Segment intersection

Line segment intersection using Bentley-Ottmann sweep line and brute force.

class cgeom.algorithms._intersection.SegmentIntersection(segments)

Bases: object

Find intersection points among a set of 2D line segments.

Provides both a Bentley-Ottmann sweep line method and a brute-force O(n^2) pairwise check.

segments

Array of segments with shape (n, 2, 2).

Type:

np.ndarray

__init__(segments)

Initialize with a set of 2D line segments.

Parameters:

segments – Collection of segments as a list, tuple, or numpy array. Each segment is [[x1, y1], [x2, y2]].

Raises:

pydantic.ValidationError – If fewer than 2 segments, zero-length segment, non-numeric, or wrong shape.

find_intersections()

Find all intersection points using Bentley-Ottmann sweep line.

Returns:

list[list[float]] – Unique intersection points as [[x, y], …].

find_intersections_brute_force()

Find all intersection points using O(n^2) pairwise check.

Returns:

list[list[float]] – Unique intersection points as [[x, y], …].

get_intersection_pairs()

Return intersection details with segment indices.

Returns:

list[tuple[int, int, list[float]]] –

Each entry is

(seg_i, seg_j, [x, y]).

get_segments()

Return segments as a plain list.

Returns:

list[list[list[float]]] – Segments as [[[x1,y1],[x2,y2]], …].

plot(title='Segment Intersections')

Deprecated: use cgeom.visualization.plot_intersections() instead.

Polygon triangulation

class cgeom.algorithms._triangulation.PolygonTriangulation(poly, poly_name='Polygon')

Bases: object

Triangulate a simple polygon using the ear-clipping algorithm.

poly

Array of polygon vertices with shape (n, 2).

Type:

np.ndarray

poly_name

Display name for the polygon.

Type:

str

diagonals

List of diagonals produced by the triangulation.

Type:

list

__init__(poly, poly_name='Polygon')

Initialize and triangulate a polygon.

Parameters:

• poly – Polygon vertices as a list, tuple, or numpy array with shape (n, 2). Vertices must be in counter-clockwise order.

• poly_name – Display name used in plot titles.

Raises:

pydantic.ValidationError – If fewer than 3 vertices, all collinear, non-numeric, or wrong shape.

is_ear(poly, vertex)

Determine whether the given vertex is an ear of the polygon.

A vertex is an ear if the triangle formed by it and its two neighbours is oriented counter-clockwise and contains no other polygon vertices.

Parameters:

• poly – Current polygon vertex array.

• vertex – Index of the vertex to test.

Returns:

bool – True if the vertex is an ear.

Triangulation()

Triangulate the polygon by iteratively clipping ears.

Returns:

list – List of diagonals, where each diagonal is a pair of [x, y] points.

get_diag_vertexes()

Get the vertex indices of each triangulation diagonal.

Returns:

list[list[int]] – Pairs of indices into self.poly for each diagonal.

plot_triangulation()

Deprecated: use cgeom.visualization.plot_triangulation() instead.

cgeom.algorithms._triangulation.generatePolygon(ctrX, ctrY, aveRadius, irregularity, spikeyness, numVerts)

Generate a random simple polygon.

Parameters:

• ctrX – X-coordinate of the polygon centre.

• ctrY – Y-coordinate of the polygon centre.

• aveRadius – Average radius from centre to vertices.

• irregularity – Parameter in [0, 1] controlling angular variance.

• spikeyness – Parameter in [0, 1] controlling radial variance.

• numVerts – Number of vertices.

Returns:

list[tuple[int, int]] – Vertices of the generated polygon.

cgeom.algorithms._triangulation.clip(x, min, max)

Clamp x to the range [min, max].

Parameters:

• x – Value to clamp.

• min – Lower bound.

• max – Upper bound.

Returns:

The clamped value.