map-tile-toolkit

Clip integer polylines and polygons into per-tile pieces on an integer tile grid, keeping the geometry's original vertices. No new vertexes are ever created on a line. The result has every vertex inside a tile, plus the first vertex just outside wherever the line crosses an edge. The tile may optionally include a buffer of [0..extent/2) size, which increases the number of vertices shared between neighboring tiles. Polygon rings are closed with synthetic corners strictly outside the buffered tile (see Polygons).

Usage

Each feature may contain feature-level and vertex-level attributes (generic).
SlicerAll accumulates every tile a polyline touches, even if there are no vertices in that tile.
SlicerOne accumulates one fixed tile.
Mosaic assembles tiles back into features, joining features that match on both sides of the edge, and rejecting inconsistent tiles. Mosaic does not require all original tiles to be added.

Add each feature (polyline), then read the pieces back through borrowed iterators — never owned Vecs. Nothing panics: bad input returns a TileError.

use geo_types::coord;
use map_tile_toolkit::{SlicerAll, TileError};

fn example() -> Result<(), TileError> {
    let line = [
        coord!{ x: 5, y: 5 },
        coord!{ x: 20, y: 20 },
        coord!{ x: 60, y: 40 },
    ];

    // `extent = 25` → 25-unit tiles;
    // `buffer = 0` = tight clip box (must be < extent / 2).
    let mut slicer = SlicerAll::new(25, 0)?;
    slicer.add_feature(&line)?;

    // tiles → features → polylines, each polyline in that tile's
    // local frame. A feature can yield several polylines
    // in one tile (the line left and re-entered).
    for tile in slicer.iter_tiles() {
        for feature in tile.iter_features() {
            for polyline in feature.iter_polylines() {
                // polyline: &[Coord<i32>]
                let _ = (tile.tile_id(), polyline);
            }
        }
    }

    Ok(())
}

SlicerOne::new(extent, buffer, tile) clips to one tile and skips the tile level (iter_features directly); it yields exactly what SlicerAll yields for that tile. add_feature is atomic — a failed polyline leaves the accumulator unchanged — and clear() resets it for reuse.

Coordinate space

The slicer is integer-only and dimensionless: extent is both the tile side and its output resolution (the vector-tile extent). A vertex x belongs to tile x.div_euclid(extent) and is emitted at x − tile·extent ∈ [0, extent); add tile · extent to recover global coordinates. Do all float/projection work up front (e.g. with geo). For web-mercator at zoom z: project, simplify, then apply one affine — scale s = 2^z · extent / circumference, translate the top-left corner to the origin, flip y, round to i32 — landing data in [0, 2^z · extent). buffer and Mosaic's extent are in these same units.

Limits

Routing walks each segment through exactly the tiles it touches, so cost follows those tiles, never a segment's bounding box: a world-spanning diagonal at z14 (extent 4096) touches ~35 000 tiles. What remains, each reported as a TileError rather than a panic:

Coordinates are i32, so 2^z · extent must fit (up to z18 at extent 4096); geometry touching a tile whose buffered box leaves the i32 range (an outermost tile, with buffer > 0) is Overflow.
2^25 tile visits per feature (TooManyTiles) — each tile a segment touches counts once, and so does each tile row it crosses without touching a tile (with buffer == 0, a segment can slip between two columns); tiles a polygon merely covers (its fill runs) are free. It bounds the time and per-tile memory one feature can demand; far above any real feature, it only rejects adversarial input.
u32 indexing (GeometryTooLarge) — at most u32::MAX vertices per polyline or polygon feature, matching the slicers' flat storage offsets.
2^28 output vertices per polygon feature (OutputTooLarge) — only rings winding around tiles many times, or many overlapping polygons, get there; they are rejected rather than exhausting memory.

Merging tiles back

Mosaic is the stateful inverse of SlicerAll: add tiles (each tile's runs, in its local frame) and it reassembles whole features across borders in the global frame. It rejects a tile that is inconsistent with those already added — a shared segment that disagrees (coordinates or payload), or a tile that owns an endpoint's cell yet fails to carry its edge (e.g. a line spanning into a neighbor the neighbor never corroborates) — naming the conflicting tile ids and leaving the mosaic unchanged. purge drops a tile; iter_features walks every reassembled feature.

use geo_types::coord;
use map_tile_toolkit::{Mosaic, SlicerAll, TileError};

fn example() -> Result<(), TileError> {
    let mut slicer = SlicerAll::new(25, 0)?;
    slicer.add_feature([
        coord!{ x: 5, y: 5 },
        coord!{ x: 60, y: 40 }
    ])?;

    let mut mosaic = Mosaic::new(slicer.extent())?;
    for tile in slicer.iter_tiles() {
        let runs: Vec<_> = tile.iter_features().flat_map(|f| f.iter_polylines()).collect();
        mosaic.add(tile.tile_id(), &runs).expect("consistent tiles never conflict");
    }
    for feature in mosaic.iter_features() {
        let _ = feature; // Vec<Coord<i32>> in global coordinates
    }
    Ok(())
}

Polygons

PolygonSlicerOne::new(extent, buffer, tile) clips polygons (an exterior ring plus holes) to one tile. PolygonSlicerAll::new(extent, buffer) slices whole multipolygon features into every tile they reach, and yields for each tile exactly what PolygonSlicerOne yields there. Original vertices are kept; where a ring leaves the tile, the gap is bridged by synthetic corners just outside the buffered box, so each ring stays closed and correctly wound but is valid only inside the box — fine for renderers that clip to the tile (MVT), not for consumers that need OGC-valid output. PolygonMosaic reassembles the tiles, dropping the synthetic parts.

Tiles a feature covers entirely are never materialized: PolygonSlicerAll reports them as FillRun { y, x: Range<i32>, polygon } row spans, so a polygon covering 10⁸ tiles costs one run per row, and time and memory grow with its perimeter rather than its area. fill_ring(&run) gives the one ring PolygonSlicerOne yields for that polygon in each of the run's tiles (a box just outside the buffered tile, wound like the polygon), so expanding the runs reproduces its output exactly.

Slicing preserves each ring's winding. signed_area_2x gives a ring's exact orientation, so normalize it once per feature if the output needs a fixed convention. MVT needs exteriors with a positive area in its y-down tile coordinates, and holes with a negative one.

use geo_types::coord;
use map_tile_toolkit::{PolygonSlicerAll, TileError, signed_area_2x};

fn example() -> Result<(), TileError> {
    let mut exterior = vec![
        coord! { x: 5, y: 5 }, coord! { x: 120, y: 5 },
        coord! { x: 120, y: 120 }, coord! { x: 5, y: 120 },
    ];
    let mut hole = vec![
        coord! { x: 40, y: 40 }, coord! { x: 40, y: 60 },
        coord! { x: 60, y: 60 }, coord! { x: 60, y: 40 },
    ];
    // MVT winding: exterior positive, holes negative.
    if signed_area_2x(&exterior) < 0 { exterior.reverse(); }
    if signed_area_2x(&hole) > 0 { hole.reverse(); }

    let mut slicer = PolygonSlicerAll::new(25, 2)?;
    // One feature is a multipolygon: each polygon is its rings, exterior first.
    slicer.add_feature([[exterior.as_slice(), hole.as_slice()]])?;
    for feature in slicer.iter_features() {
        // Tiles a ring edge touches: tile → polygons → rings
        // (each ring closed, in the tile's local frame).
        for tile in feature.iter_tiles() {
            for polygon in tile.iter_polygons() {
                for ring in polygon.iter_rings() {
                    let _ = (tile.tile_id(), ring.is_hole(), ring.vertices());
                }
            }
        }
        // Tiles entirely inside one of its polygons, as row spans: in each tile (x, y)
        // for x in run.x, that polygon is the single ring `fill_ring` (tile-local).
        for run in feature.iter_fill_runs() {
            let _ = (run.y, &run.x, run.polygon, feature.fill_ring(&run));
        }
    }
    Ok(())
}

A per-worker slicer can be reused across features: clear() keeps every buffer's capacity, so it stops allocating once warmed up, and shrink_to_fit() releases what an outlier feature left behind. add_feature is atomic, like the polyline slicers.

Payloads

The slicers carry data on two independent axes: a per-vertex payload (the Vertex type) and a per-feature attribute (the A type). Use either, both, or neither.

Per-vertex payload

The slicers are generic over a Vertex (default Coord<i32>); Measured<M> pairs a position with any Copy + PartialEq payload (an M value, an id) that rides through slicing and merging unchanged — nothing is interpolated, since no new vertices are cut.

use map_tile_toolkit::{Measured, SlicerAll, TileError};

fn example() -> Result<(), TileError> {
    // Each vertex carries a payload (here an id); it survives slicing untouched.
    let mut slicer = SlicerAll::new(25, 0)?;
    slicer.add_feature([
        Measured::new(5, 5, 100),
        Measured::new(20, 20, 200),
        Measured::new(60, 40, 300),
    ])?;
    for tile in slicer.iter_tiles() {
        for feature in tile.iter_features() {
            for run in feature.iter_polylines() {
                let _ = run.iter().map(|v| (v.position, v.m)).collect::<Vec<_>>();
            }
        }
    }
    Ok(())
}

Per-feature attributes (MVT-style)

Data that belongs to a whole feature — an optional id, a key/value property map — is not per-vertex, so it rides on the slicer's second generic axis A (default (), a zero-sized type that costs nothing) rather than in the vertex payload. Attach it with add_feature_with(line, attr) and read it back per tile-piece with feature.attr() — no side table, no per-vertex handles. A only needs to be Clone.

use geo_types::{Coord, coord};
use map_tile_toolkit::{SlicerAll, TileError};

#[derive(Clone)]
struct Attrs {
    id: Option<u64>,
    name: &'static str
}

fn example() -> Result<(), TileError> {
    let mut slicer = SlicerAll::new(25, 0)?;
    slicer.add_feature_with(
        [coord! { x: 5, y: 5 }, coord! { x: 60, y: 40 }],
        Attrs { id: Some(1), name: "Main St" },
    )?;
    for tile in slicer.iter_tiles() {
        for feature in tile.iter_features() {
            let attrs = feature.attr(); // &Attrs, duplicated onto every tile the feature touches
            let _ = (attrs.id, attrs.name);
        }
    }
    Ok(())
}

A feature that is split comes out two ways — within one tile its runs stay grouped as a single feature (render a MultiLineString); across tiles its attributes are duplicated onto each tile's piece. The two axes are orthogonal, so SlicerAll<Measured<M>, Attrs> carries per-vertex M and per-feature attributes at once. See examples/mvt_features.rs for the full round-trip emitting per-tile GeoJSON with ids and properties preserved.

Development

This project uses just (cargo install just); run just for the command list and just test to test. Tests are data-driven: each tests/polylines/fixtures/*.geojson polyline is sliced by both paths (asserted byte-identical) and snapshotted as a .geojson FeatureCollection (original line plus every per-tile piece) that renders on a map. Polygon fixtures in tests/polygons/fixtures/ are snapshotted per tile (snapshots*/); PolygonSlicerOne and PolygonSlicerAll (its fill runs expanded into fill rings) must produce identical output, and every PolygonSlicerAll tile is also checked against PolygonSlicerOne on finer grids. Run just bless to regenerate snapshots. To inspect them, load tests/polylines/fixtures/grid.geojson (the tile grid, offset 0.5px to sit between integer coordinates) and the tests/polylines/snapshots/*.geojson files in QGIS or any GeoJSON viewer.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT) at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual-licensed as above, without any additional terms or conditions.

map-tile-toolkit 0.2.0