vibespatial.constructive.minimum_bounding_circle

GPU-accelerated minimum bounding circle and radius computation.

Uses Ritter’s bounding sphere algorithm (adapted to 2D) for an O(n) per-geometry approximation of the minimum enclosing circle. One thread per geometry computes (center_x, center_y, radius).

Two public entry points:

  • minimum_bounding_circle_owned: Returns Polygon OwnedGeometryArray (circle tessellated to N-gon).

  • minimum_bounding_radius_owned: Returns float64 array of radii.

Both share the same core NVRTC kernel. The polygon output adds a circle-to-polygon tessellation pass (also NVRTC).

Architecture (ADR-0033 tier classification):

  • Ritter’s inner loop: Tier 1 NVRTC (geometry-specific iteration)

  • Tessellation: Tier 1 NVRTC (per-geometry circle -> polygon)

  • Offset computation: Tier 2 CuPy (element-wise arange)

Precision (ADR-0002):

  • minimum_bounding_circle: CONSTRUCTIVE class – fp64 by design. Polygon vertices must be exact; no fp32 path until robustness proves safe.

  • minimum_bounding_radius: METRIC class – fp64 by design. Ritter’s distance comparisons need fp64 to guarantee containment.

Ritter’s is an approximation: the returned circle always CONTAINS all geometry points, but the radius may be up to ~5% larger than the exact minimum enclosing circle (Welzl). Shapely uses Welzl, so radius values will not match exactly – the key invariant is containment.

Algorithm (Ritter’s 2D bounding circle):

  1. Compute centroid of all coordinates.

  2. Find the point P furthest from centroid.

  3. Find the point Q furthest from P.

  4. Initial circle: center = midpoint(P, Q), radius = dist(P, Q) / 2.

  5. Scan all points: for any point outside the circle, expand: - new_radius = (old_radius + dist(center, outside_point)) / 2 - shift center toward outside_point by (new_radius - old_radius)

  6. Two expansion passes for convergence.

Attributes

cp

logger

Functions

minimum_bounding_circle_owned(...)

Compute the minimum bounding circle of each geometry (as polygon).

minimum_bounding_radius_owned(→ numpy.ndarray)

Compute the minimum bounding radius of each geometry.

Module Contents

vibespatial.constructive.minimum_bounding_circle.cp = None
vibespatial.constructive.minimum_bounding_circle.logger
vibespatial.constructive.minimum_bounding_circle.minimum_bounding_circle_owned(owned: vibespatial.geometry.owned.OwnedGeometryArray, *, dispatch_mode: vibespatial.runtime.ExecutionMode | str = ExecutionMode.AUTO, precision: vibespatial.runtime.precision.PrecisionMode | str = PrecisionMode.AUTO) → vibespatial.geometry.owned.OwnedGeometryArray

Compute the minimum bounding circle of each geometry (as polygon).

Uses Ritter’s algorithm for an O(n) per-geometry approximation. The returned circle always CONTAINS all geometry points but may be slightly larger than the exact minimum enclosing circle.

Parameters

ownedOwnedGeometryArray

Input geometries (any family).

dispatch_modeExecutionMode or str

Execution mode selection. Defaults to AUTO.

precisionPrecisionMode or str

Precision mode selection. CONSTRUCTIVE class: stays fp64.

Returns

OwnedGeometryArray

Polygon OwnedGeometryArray with one circle polygon per input row.

vibespatial.constructive.minimum_bounding_circle.minimum_bounding_radius_owned(owned: vibespatial.geometry.owned.OwnedGeometryArray, *, dispatch_mode: vibespatial.runtime.ExecutionMode | str = ExecutionMode.AUTO, precision: vibespatial.runtime.precision.PrecisionMode | str = PrecisionMode.AUTO) → numpy.ndarray

Compute the minimum bounding radius of each geometry.

Uses Ritter’s algorithm for an O(n) per-geometry approximation. Returns float64 array of radii.

Parameters

ownedOwnedGeometryArray

Input geometries (any family).

dispatch_modeExecutionMode or str

Execution mode selection. Defaults to AUTO.

precisionPrecisionMode or str

Precision mode selection. METRIC class: stays fp64.

Returns

np.ndarray

float64 array of shape (row_count,) with bounding radius per geometry.