Geo Polygonize

A native Rust port of the JTS/GEOS polygonization algorithm. This crate allows you to reconstruct valid polygons from a set of lines, including handling of complex topologies like holes, nested shells, and disconnected components.

Ask DeepWiki

Features

  • Robust Polygonization: Extracts polygons from unstructured linework.
  • Robust Noding: Implements Iterated Snap Rounding (ISR) to guarantee topological correctness on dirty inputs (self-intersections, overlaps).
  • Hardware Acceleration: Uses SIMD instructions (via wide crate) for critical geometric predicates like Point-in-Polygon checks.
  • Wasm Optimized: Tailored for WebAssembly with talc allocator and Zero-Copy data support (geoarrow).
  • Performance: Competitive with GEOS/Shapely (C++), outperforming it on random sparse inputs and scaling well on dense grids.
  • Geo Ecosystem: Fully integrated with geo-types and geo crates.
  • GeoArrow Support: Zero-copy data transfer via Arrow C Data Interface and Arrow IPC (Wasm).

Engineering Roadmap

For an ambitious, prioritized plan covering performance, security, API consistency, and maintainability, see docs/roadmap.md.

Usage

Library

use geo_polygonize_core::Polygonizer;
use geo_types::LineString;

fn main() {
    let mut poly = Polygonizer::new();

    // Enable robust noding if lines might intersect
    poly.node_input = true;
    // Optional: Configure snap grid (default 1e-10)
    poly.snap_grid_size = 1e-6;

    // Add lines (e.g., a square with diagonals)
    poly.add_geometry(LineString::from(vec![
        (0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0), (0.0, 0.0)
    ]).into());
    poly.add_geometry(LineString::from(vec![
        (0.0, 0.0), (10.0, 10.0)
    ]).into());

    let polygons = poly.polygonize().expect("Polygonization failed");

    for p in polygons {
        println!("Found polygon with area: {}", p.unsigned_area());
    }
}

Choosing node_input and snap_grid_size

Polygonization quality is heavily influenced by input noding strategy.

  • node_input = false (default): Fastest path. Use this when your input linework is already noded (all intersections are explicit vertices).
  • node_input = true: Enables Iterated Snap Rounding (ISR). Use this for real-world datasets that may contain slight misalignments, overlaps, or self-intersections.
  • snap_grid_size controls how aggressively coordinates are snapped during robust noding:
    • Start with 1e-10 for high-precision projected data.
    • Increase to 1e-8 or 1e-6 when near-duplicate vertices prevent clean topology.
    • Avoid very large values unless your coordinate units are coarse; oversnapping can collapse narrow features.

Practical workflow:

  1. Run with node_input = false first on trusted data.
  2. If you observe missing polygons, sliver artifacts, or unresolved intersections, enable node_input.
  3. Tune snap_grid_size upward incrementally until topology stabilizes.

Output semantics

The polygonizer intentionally returns only valid polygonal areas that can be formed from closed cycles:

  • Dangles are removed: dead-end edges do not appear in output polygons.
  • Cut edges are excluded: edges that are connected but cannot bound a face are ignored.
  • Holes and nested shells are preserved when enough boundary information is present.

This behavior matches classical JTS/GEOS polygonization semantics and is useful for cleaning linework before area analysis.

GeoArrow Integration

The library supports ingesting data directly from Arrow arrays via the arrow_api module and ffi.

use geo_polygonize_core::arrow_api::{polygonize_arrow, PolygonizerOptions};
// ... create Arrow array ...
// let result = polygonize_arrow(&array, &field, options);

Python

The Python package is published as geo-polygonize-py and imported as geo_polygonize.

pip install geo-polygonize-py

import numpy as np
from geo_polygonize import polygonize, import_probe

# 1. Using Shapely LineStrings or coordinate lists directly
lines = [
    [(0, 0), (10, 0), (10, 10), (0, 10), (0, 0)],
    [(0, 0), (10, 10)]
]

# return_polygons=True returns a list of shapely.geometry.Polygon objects
polygons = polygonize(lines=lines, return_polygons=True)
for p in polygons:
    print(p.area)

# 2. Using High-Performance Flat Arrays
# Perfect for zero-copy integrations or massive datasets
coords = np.array([
    0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0, 0.0, 0.0,
    0.0, 0.0, 10.0, 10.0
], dtype=np.float64)

# Start indices for each line segment.
# The final closing offset is computed implicitly.
offsets = np.array([0, 5], dtype=np.uint32)

# Returns a stable dictionary with 'polygons', diagnostics, and provenance.
result_dict = polygonize(coords=coords, offsets=offsets)

# Native-extension probes are cheap and safe for optional integrations.
ok, error = import_probe()

CFB/autograder integrations should use the versioned production profile rather than assembling caller-side knobs or using legacy polygonize(..., node=True, snap=0.5) calls:

from geo_polygonize import cfb_robust_options, polygonize_with_options

result = polygonize_with_options(
    coords=coords,
    offsets=offsets,
    options=cfb_robust_options(),
)

The default return shape is a stable dictionary with polygons as SimplePolygon values. Use return_polygons=True only when you want Shapely Polygon objects.

SnapStrategy::Grid keeps topology and output coordinates on the configured precision grid. The CFB profile uses GeosCompat: the grid establishes robust topology, then output nodes regain deterministic source coordinates to better match Shapely snap plus full-precision noding. It is not set_precision emulation, and exact parity is not guaranteed for many-to-one snaps.

For Shapely parity checks, compare report-mode outputs with the built-in mismatch helper:

from geo_polygonize import explain_mismatch, polygonize_with_options

options = cfb_robust_options()
result_a = polygonize_with_options(coords=coords_a, offsets=offsets_a, options=options)
result_b = polygonize_with_options(coords=coords_b, offsets=offsets_b, options=options)
result_a["options"] = options
result_b["options"] = options

mismatch = explain_mismatch(result_a, result_b)

For a minimal Shapely smoke comparison, use area signatures:

from shapely.ops import polygonize as shapely_polygonize

rust_polys = polygonize_with_options(lines=lines, options=cfb_robust_options(), return_polygons=True)
rust_areas = sorted(round(poly.area, 6) for poly in rust_polys)
shapely_areas = sorted(round(poly.area, 6) for poly in shapely_polygonize(lines))

WebAssembly (WASM)

This library supports WebAssembly with an ergonomic dual-build configuration that automatically utilizes SIMD instructions where available.

Installation:

npm install geo-polygonize

Standard Usage (Quick Demos): The default entry point automatically handles feature detection (SIMD) and lazy-loading of the Wasm binary. The Wasm is inlined as a Base64 Data URI, so no extra bundler configuration is needed. For app builds, prefer the slim entry point below so your bundler keeps the Wasm assets out of the JavaScript chunk.

import init, { polygonize, polygonize_geoarrow } from "geo-polygonize";

async function run() {
    await init();

    const geojson = {
        "type": "FeatureCollection",
        "features": [
            // ... your line features
        ]
    };

    // Returns a GeoJSON FeatureCollection string
    // Pass explicitly matching backend configuration if desired
    const result = polygonize(
        JSON.stringify(geojson),
        true, // node_input
        0.5   // snap_grid_size
    );
    console.log(JSON.parse(result));

    // Or use Arrow IPC bytes
    // const ipcBuffer = ...;
    // const arrowResult = polygonize_geoarrow(ipcBuffer, false, 1e-10, false);
}

Slim Usage (Apps / Manual Loading): For Vite and other app bundlers, import from geo-polygonize/slim and pass explicit Wasm asset URLs.

import { cfbRobustOptions, initBest } from "geo-polygonize/slim";
import scalarUrl from "geo-polygonize/geo_polygonize.wasm?url";
import simdUrl from "geo-polygonize/geo_polygonize_simd.wasm?url";

async function run() {
    const wasm = await initBest(
        { module_or_path: scalarUrl },
        { module_or_path: simdUrl },
    );

    const result = wasm.polygonizeWithOptions(
        JSON.stringify(geojson),
        cfbRobustOptions,
    );
}

Multithreaded Usage (Experimental): This library provides a multithreaded build powered by wasm-bindgen-rayon.

import init, { initThreadPool, polygonize } from "geo-polygonize/threads";

async function run() {
    await init();

    // Initialize thread pool (e.g., with navigator.hardwareConcurrency)
    await initThreadPool(navigator.hardwareConcurrency);

    // ... use polygonize as usual
}

Important: Multithreaded WebAssembly requires SharedArrayBuffer, which is only available in secure contexts. You must serve your page with the following headers:

Cross-Origin-Opener-Policy: same-origin
Cross-Origin-Embedder-Policy: require-corp

CLI Example

The repository includes a CLI tool to polygonize GeoJSON files.

# Build the example
cargo build -p geo-polygonize-core --example polygonize --release

# Run on input lines
cargo run -p geo-polygonize-core --release --example polygonize -- --input lines.geojson --output polygons.geojson --node

Visualization

You can visualize the results using the provided Python script (requires matplotlib and shapely).

python3 scripts/visualize.py --input lines.geojson --output polygons.geojson --save result.png

Examples

Below are some examples of what the polygonizer can do.

Nested Holes and Islands

The algorithm correctly identifies nested structures (Island inside a Hole inside a Shell).

Nested Holes

Incomplete Grid / Dangles

The algorithm prunes dangles (dead-end lines) and extracts only closed cycles.

Incomplete Grid

Touching Polygons (Shared Edges)

Using robust noding (--node), it can reconstruct adjacent polygons that share boundaries, even if the input lines are not perfectly noded.

Touching Polygons

Self-Intersecting Geometry (Bowtie)

Self-intersecting lines are split at intersection points, and valid cycles are extracted.

Bowtie

Complex Geometries

The polygonizer can handle complex, curved inputs (approximated by LineStrings) such as overlapping circles and shapes with multiple holes.

Overlapping Circles: Note how the intersection regions are correctly identified as separate polygons.

Overlapping Circles

Curved Holes: A complex polygon with multiple circular holes.

Curved Holes

Benchmarks

This library includes a "severe" comparison suite against shapely (GEOS).

See BENCHMARKS.md for detailed results and instructions on how to run them.

Architecture

This implementation moves away from the pointer-based graph structures of JTS/GEOS to a Rust-idiomatic Index Graph (Arena) approach.

See ARCHITECTURE.md for a deep dive into the optimization strategies.

Key optimizations include:

  1. Robust Noding: Iterated Snap Rounding (ISR) using rstar for intersection detection and grid snapping.
  2. Vectorization: SIMD-accelerated Ray Casting for efficient Hole Assignment.
  3. Memory Layout: Structure of Arrays (SoA) for graph nodes and talc allocator for Wasm.

License

MIT/Apache-2.0

Key dates

PyPI data
Data sourced directly from PyPI's database.
  • Released:
Newer release available (1.1.0)

1 maintainer

PyPI data
Data sourced directly from PyPI's database.
Avatar for graydonpleasants from gravatar.com graydonpleasants

License

MIT OR Apache-2.0

Requires

Python >=3.8

Classifiers

Report project as malware

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

geo_polygonize_py-0.39.1.tar.gz (141.0 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

geo_polygonize_py-0.39.1-cp38-abi3-win_amd64.whl (854.5 kB view details)

Uploaded CPython 3.8+Windows x86-64

geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_35_x86_64.whl (986.5 kB view details)

Uploaded CPython 3.8+manylinux: glibc 2.35+ x86-64

geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (939.1 kB view details)

Uploaded CPython 3.8+manylinux: glibc 2.17+ ARM64

geo_polygonize_py-0.39.1-cp38-abi3-macosx_11_0_arm64.whl (854.8 kB view details)

Uploaded CPython 3.8+macOS 11.0+ ARM64

File details

Details for the file geo_polygonize_py-0.39.1.tar.gz.

File metadata

  • Download URL: geo_polygonize_py-0.39.1.tar.gz
  • Upload date:
  • Size: 141.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for geo_polygonize_py-0.39.1.tar.gz
Algorithm Hash digest
SHA256 b35faa479e19addffd33e327244dff483ea61b939fc4df8375428a8252dbc182
MD5 d3283afae94386555f3a2686ec0b32d1
BLAKE2b-256 7355e6910c01977193202c4298a238485d99232ae43dafa370070be7950c46bf

See more details on using hashes here.

Provenance

The following attestation bundles were made for geo_polygonize_py-0.39.1.tar.gz:

Publisher: publish-python.yml on graydonpleasants/geo-polygonize

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file geo_polygonize_py-0.39.1-cp38-abi3-win_amd64.whl.

File metadata

File hashes

Hashes for geo_polygonize_py-0.39.1-cp38-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 e8104cf5cf1b4ee5ba64e187a6293edca6ff202fd4352f90c87f7ed1c1848fc6
MD5 2cdc07da9b081eead9c64de847745bf7
BLAKE2b-256 6222fae907c7920e9eeea1159691c3df428b50d5e7ca1d40738064b066ccbf93

See more details on using hashes here.

Provenance

The following attestation bundles were made for geo_polygonize_py-0.39.1-cp38-abi3-win_amd64.whl:

Publisher: publish-python.yml on graydonpleasants/geo-polygonize

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 50a5d70d1590eb4cb84dc0e734f1de9af9ed1af37b24a821c9c444b2ffefe1e0
MD5 0e2f500ad79c0e0f3b94046bbfb9d796
BLAKE2b-256 0bbc2d63a9ed2cfca4961a48f4d8dbf0a29ce9ce89706a440184bfeaead114f1

See more details on using hashes here.

Provenance

The following attestation bundles were made for geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_35_x86_64.whl:

Publisher: publish-python.yml on graydonpleasants/geo-polygonize

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 d5a48a950befe90a1f6624761af44af62c5191e9d4a3ecc7eaa60b1bf001e7f7
MD5 06961de7e8d8da7edaf55d170c86c63e
BLAKE2b-256 2c37b577b2f314d7b565fe7aa66a71c7d2413e43a043e2e47b3b992263f3cda0

See more details on using hashes here.

Provenance

The following attestation bundles were made for geo_polygonize_py-0.39.1-cp38-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl:

Publisher: publish-python.yml on graydonpleasants/geo-polygonize

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file geo_polygonize_py-0.39.1-cp38-abi3-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for geo_polygonize_py-0.39.1-cp38-abi3-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 de540401ac35b421e8d767e648aed385aead95c7a7e3492c5bb17f711f609405
MD5 ddedd6284ee046a6ed3a127319e0c574
BLAKE2b-256 159a6aa69ad0746ba0d712307ef4981d62a0af2be9bdef359b1d876b8f6f589d

See more details on using hashes here.

Provenance

The following attestation bundles were made for geo_polygonize_py-0.39.1-cp38-abi3-macosx_11_0_arm64.whl:

Publisher: publish-python.yml on graydonpleasants/geo-polygonize

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Release history Release notifications | RSS feed

1.1.0

5 files

1.0.0

5 files

0.76.2

5 files

0.76.1

5 files

0.76.0

5 files

0.75.0

5 files

0.74.0

5 files

0.73.0

5 files

0.72.0

5 files

0.71.0

5 files

0.70.0

5 files

0.69.0

5 files

0.68.0

5 files

0.67.0

5 files

0.66.0

5 files

0.65.0

5 files

0.64.0

5 files

0.63.0

5 files

0.62.0

5 files

0.61.0

5 files

0.60.0

5 files

0.59.0

5 files

0.58.1

5 files

0.58.0

5 files

0.57.0

5 files

0.56.0

5 files

0.55.0

5 files

0.54.0

5 files

0.53.0

5 files

0.52.0

5 files

0.51.2

5 files

0.51.1

5 files

0.51.0

5 files

0.50.0

5 files

0.49.0

5 files

0.48.0

5 files

0.47.1

5 files

0.47.0

5 files

0.46.2

5 files

0.46.1

5 files

0.46.0

5 files

0.45.1

5 files

0.45.0

5 files

0.44.0

5 files

0.43.0

5 files

0.42.0

5 files

0.41.0

5 files

0.40.1

5 files

0.40.0

5 files

0.39.13

5 files

0.39.12

5 files

0.39.11

5 files

0.39.10

5 files

0.39.9

5 files

0.39.8

5 files

0.39.7

5 files

0.39.6

5 files

0.39.5

5 files

0.39.4

5 files

0.39.3

5 files

0.39.2

5 files

This release

0.39.1 This release

5 files

0.39.0

5 files

0.38.1

5 files

0.38.0

5 files

0.37.8

5 files

0.37.7

5 files

0.37.6

5 files

0.37.5

5 files

0.37.4

5 files

0.37.3

5 files

0.37.2

5 files

0.37.1

5 files

0.37.0

5 files

0.36.2

5 files

0.36.1

5 files

0.36.0

5 files

0.35.2

5 files

0.35.1

4 files

0.35.0

4 files

0.34.0

3 files

0.33.1

3 files

0.33.0

3 files

0.23.1

3 files

0.23.0

3 files

0.22.1

3 files

0.22.0

3 files

0.21.0

3 files

0.20.0

3 files

0.19.0

3 files

0.18.1

3 files

0.18.0

3 files

0.17.4

3 files

0.17.3

3 files

0.17.2

3 files

0.17.1

3 files

0.17.0

3 files

0.16.0

3 files

0.15.0

3 files

0.14.1

3 files

0.14.0

3 files

0.13.0

3 files

0.12.1

3 files

0.12.0

3 files

0.11.0

3 files

0.10.0

3 files

0.9.0

3 files

0.8.1

3 files

0.8.0

3 files

0.7.0

3 files

0.6.3

3 files

0.6.2

3 files

0.6.1

3 files

0.6.0

3 files

0.5.0

3 files

0.4.2

3 files

0.4.1

3 files

Yanked

0.1.0

5 files

Yanked reason: wrong version number

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page