MaxInscribedCircle

Finds the largest circle that fits inside a polygon.

The maximum inscribed circle is the largest circle that fits inside a polygon. Holes act as boundary, so the circle must clear interior rings as well as the exterior. This is the dual of the largest empty circle, which sits between obstacles instead of inside them. The reported radius is measured at the returned centre, so a returned circle fits the polygon. A zero-area ring or a non-finite coordinate fails fast instead of returning a meaningless circle. The full API reference and the algorithm detail are in the crate documentation: cargo doc --open, no feature needed.

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, so above 1 means this crate wins. 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, so the C ABI needs no feature. Build with cargo build --release.

coords is flat [x0, y0, ...] exterior ring data. Holes arrive as an array of HoleInput, each holding its own flat coordinate pointer. The multipolygon call takes an array of MicPolyInput, each holding one exterior and its holes. MicResultC, MicOptionsC, HoleInput, and MicPolyInput are #[repr(C)].

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.

Features

rayon is an unconditional dependency. The batch entry point maximum_inscribed_circle_slice and the C ABI need no feature.

License

Apache-2.0