MaxInscribedCircle

Finds the largest circle that fits inside a polygon. Holes act as boundary, so the circle must clear them too.

The maximum inscribed circle is the largest circle that fits inside a polygon. Every boundary segment limits it, so an interior ring limits it as well.

API

MicResult reports the centre and the radius. It also reports the squared radius, the indices of the segments the circle touches, and the candidate count. used_engine and approach name the stage that answered. component_index names the multipolygon component.

The batch entry point needs no feature, because rayon is a plain dependency.

Run cargo run --example quickstart for a complete program.

How it solves

The crate runs two stages.

The first stage handles a single ring of four or five vertices. It solves the triangle incenter, the axis-aligned rectangle, and the convex quad in closed form. It then measures each result against the segment table. A result that misses by more than 1e-9 relative falls through to the second stage.

The second stage is a grid solver. It runs branch and bound over the bounding box and orders cells by the 1-Lipschitz bound on boundary distance. It refines to diag * 1e-7. A compass hill climb then sharpens the incumbent. The search pops at most 50,000 cells, and the climb finishes a long thin shape that the budget cannot resolve.

The reported radius is always measured, never inferred. The crate measures the distance from the centre to the nearest boundary segment at the end of the solve, so a returned circle fits the polygon.

Correctness

tests/corpus_invariants.rs checks two properties.

The first property is fit. The reported radius must equal the measured clearance at the reported centre.

The second property is reach. No dense interior sample may clear more than the returned circle.

The workflow in .github/workflows/ci.yml runs the suite on every push and pull request. It runs four feature sets, the 1.88 MSRV check, and a clippy, fmt, and rustdoc job. No check needs an external solver.

Performance

The corpus holds 290 Polish cadastral parcels in benches/data/realworld_290.geojson. Both solvers receive the same polygon and the same tolerance. The timer covers the solve only, because both sides build their indexes before the clock starts. Ratio is GEOS divided by native. Both sides run serially, so the table measures the solver and not the threading.

The ratio varies by case. Across the 290 parcels:

The margin narrows as vertex count grows.

Pinned to one core the ratio holds at 7.9x. The batch entry point is separate. maximum_inscribed_circle_slice returns bit-identical results in input order and runs 6.1x faster on 12 cores.

Repeat runs of the same tree land between 8.39x and 8.78x, so the second digit is noise. Regenerate before quoting a new figure.

Regenerate with cargo run --release --features bench-geos --example compare_apples. The build needs the GEOS C library. The GEOS dependency reads GEOS_LIB_DIR and GEOS_VERSION when pkg-config cannot find an install.

Integration with the geo ecosystem

Enable geo-traits to accept a foreign polygon directly. WKB views, GeoArrow arrays, and GeoZero streams then need no conversion.

The dispatch function rejects every other variant with MicError::InvalidInput and names the variant in the message.

Python bindings

The python feature builds the extension module max_inscribed_circle. Build it with maturin, or with cargo build --features python,extension-module.

The result class reports center_x, center_y, radius, radius_sq, used_engine, candidate_count, and component_index. Rings arrive as (x, y) tuples. A rejected input raises ValueError, and so does a solver panic.

C API

src/ffi.rs is always compiled. It exposes mic_solve, mic_solve_multipolygon, and mic_options_default. Flat [x0, y0, ...] coordinate arrays go in, and #[repr(C)] structs come out.

Each function returns 0 on success and -1 on failure. A panic becomes -1, and a null or short buffer is rejected instead of crashing. MicOptionsC carries no tunable field yet. It exists so the ABI has a stable options pointer.

Features

License

Apache-2.0