Crate map_tile_toolkit

Expand description

§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

Slicer takes one geometry at a time — a line, a point or a polygon — and returns a lazy iterator over its slices: line / point / polygon for every tile the geometry reaches (even tiles holding none of its vertices), tile_line / tile_point / tile_polygon for one given tile.
Vertices may carry a payload (generic Vertex); feature-level data stays with the caller, who pairs it with each slice of the feature being sliced.
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.

Slicing is lazy: each slice is computed only when the iterator reaches it, so stopping early stops the work. A line run is never copied — it borrows the caller’s vertices, so a line with millions of vertices costs no extra memory — and a polygon piece is built in the slicer’s reused working memory. Slices come in no particular order: a tile can get several slices of one line (where it left and re-entered the tile). Nothing panics: bad input yields a TileError.

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

fn main() -> 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 slicer = Slicer::new(25, 0)?;

    // One slice per run, each in its tile's local frame.
    for slice in slicer.line(&line)? {
        for vertex in slice.run() {
            let _ = (slice.tile(), vertex); // vertex: Coord<i32>
        }
    }

    Ok(())
}

slicer.tile_line(tile, &line) clips to one tile and yields exactly the slices line yields for that tile.

§Multi-geometries

The slicer has no notion of a multi-geometry. To slice a MultiLineString, MultiPoint or MultiPolygon, call it once per element (line for each line, point for each point, polygon for each polygon). The caller has to manage the association between a feature’s attributes and each of its slices anyway, tile by tile; doing that for the elements of one multi-feature is no extra work compared with doing it for several features, and it keeps the slicer free of per-element indices, and of any state that grows with the feature. Slices of several elements that land in one tile are simply several slices in that tile, which the caller groups (the runs of a MultiLineString into one geometry in that tile, say).

§Points

slicer.point(p) yields the point in every tile whose buffered box holds it: its own tile, plus up to three neighbors when it lies within buffer of an edge (a point at a corner of four tiles lands in all four). Each item is the tile and the point in that tile’s local frame, payload unchanged; the iterator knows its length up front (one to four items). slicer.tile_point(tile, p) asks one tile and returns the local point, if the tile holds it.

use geo_types::coord;
use map_tile_toolkit::{Slicer, TileError, TileId};

fn main() -> Result<(), TileError> {
    let slicer = Slicer::new(256, 8)?;

    // One unit past the corner of tile (1, 1): within the buffer of three neighbors as well.
    let point = coord! { x: 257, y: 256 };
    let slices = slicer.point(point)?;
    assert_eq!(slices.len(), 4);
    for slice in slices {
        let _ = (slice.tile(), slice.point()); // TileId, and the point as Coord<i32> in that tile
    }

    assert_eq!(
        slicer.tile_point(TileId::new(1, 1), point)?,
        Some(coord! { x: 1, y: 0 })
    );
    assert_eq!(slicer.tile_point(TileId::new(5, 5), point)?, None);
    Ok(())
}

§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), whose own area is [0, extent) in its local frame x − tile·extent; slices come in that frame, so vertices in the buffer, a line’s first vertex past an edge, and a polygon’s synthetic corners lie outside it. 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. Rows a segment crosses between two unbuffered tiles (buffer == 0) are skipped at once. 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. Every slicing call reads the geometry once, to bound it, and returns the error from the call, so the iterators cannot fail midway. Bounding is per geometry, so a line or polygon spanning more than 2^31 units on one axis is rejected whole.
u32 indexing (GeometryTooLarge) — at most u32::MAX rings or edges per polygon, from the call, and u32::MAX vertices per piece, the one error a polygon iterator can still yield.

There is no budget on how many tiles a geometry may reach: slicing is lazy, so memory stays bounded however far it reaches, and the work is only what the caller pulls.

§Merging tiles back

Mosaic is the stateful inverse of Slicer::line: 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 std::collections::BTreeMap;

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

fn main() -> Result<(), TileError> {
    let slicer = Slicer::new(25, 0)?;
    let line = [coord!{ x: 5, y: 5 }, coord!{ x: 60, y: 40 }];

    // Gather each tile's runs, then hand each tile to the mosaic.
    let mut tiles = BTreeMap::<_, Vec<_>>::new();
    for slice in slicer.line(&line)? {
        tiles.entry(slice.tile()).or_default().push(slice.run().to_vec());
    }
    let mut mosaic = Mosaic::new(slicer.extent())?;
    for (tile, runs) in &tiles {
        mosaic.add(*tile, runs).expect("consistent tiles never conflict");
    }
    for feature in mosaic.iter_features() {
        let _ = feature; // Vec<Coord<i32>> in global coordinates
    }
    Ok(())
}

§Polygons

slicer.polygon(&rings) slices a polygon — its rings, exterior first — into every tile it reaches, and slicer.tile_polygon(tile, &rings) into one tile (its piece there, if any). A multipolygon is sliced one polygon at a time. 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.

The polygon is sliced row by row, and nothing outside the current tile row is kept: the call reads the rings once, to bound and index them, and the iterator holds one row plus a small index of the polygon’s edges by row (a polygon inside one tile skips even that, and is lent as it is). A tile gets one piece — the exterior and the holes that reach the tile — built in one reused buffer, so the iterator is lending: a piece is valid until the next next(), and the loop is while let. Each ring is closed, its first vertex repeated at the end (drop it for an MVT ClosePath). Polygons need &mut Slicer for that buffer; lines and points need only &Slicer.

Tiles a polygon covers entirely are never materialized: they come as FillRun { y, x } 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. slices.fill_ring(&run) (or slicer.fill_ring(&run), once the iterator is done) is the one ring tile_polygon yields for that polygon in each of the run’s tiles — five tile-local vertices, a box just outside the buffered tile, wound like the polygon — so expanding the runs reproduces it 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::{PolygonSlice, Slicer, TileError, signed_area_2x};

fn main() -> 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 = Slicer::new(25, 2)?;
    // A polygon is its rings, exterior first.
    let rings = [exterior, hole];
    let mut slices = slicer.polygon(&rings)?;
    while let Some(slice) = slices.next() {
        match slice? {
            // The polygon in one tile: its rings, exterior first, each closed and tile-local.
            PolygonSlice::Piece(piece) => {
                for ring in piece.rings() {
                    let _ = (piece.tile(), ring.to_vec());
                }
            }
            // Tiles (x, y) for x in run.x, entirely inside the polygon: each holds it as the
            // single ring `slices.fill_ring(&run)`.
            PolygonSlice::Run(run) => {
                let _ = (run.y, &run.x, slices.fill_ring(&run));
            }
        }
    }
    Ok(())
}

One slicer per worker can be reused across polygons: it keeps its working memory’s capacity, so it stops allocating once warmed up, and shrink_to_fit() releases what an outlier polygon left behind.

§Payloads

Data rides along on two independent axes: a per-vertex payload (the Vertex type), and per-feature attributes, which the caller pairs with each slice. Use either, both, or neither.

§Per-vertex payload

The slicer is 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, Slicer, TileError};

fn main() -> Result<(), TileError> {
    // Each vertex carries a payload (here an id); it survives slicing untouched.
    let slicer = Slicer::new(25, 0)?;
    let line = [
        Measured::new(5, 5, 100),
        Measured::new(20, 20, 200),
        Measured::new(60, 40, 300),
    ];
    for slice in slicer.line(&line)? {
        let _ = slice.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. The slicer takes one geometry at a time, so the caller pairs every slice with the data of the feature it came from: no side table, no per-vertex handles, nothing for the slicer to carry. For a multi-feature that means the same loop over its elements (see Multi-geometries).

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

struct Attrs {
    id: Option<u64>,
    name: &'static str
}

fn main() -> Result<(), TileError> {
    let slicer = Slicer::new(25, 0)?;
    let attrs = Attrs { id: Some(1), name: "Main St" };
    let line = [coord! { x: 5, y: 5 }, coord! { x: 60, y: 40 }];
    for slice in slicer.line(&line)? {
        // Every slice of this feature goes with `attrs`, in whichever tile it lands.
        let _ = (slice.tile(), attrs.id, attrs.name);
    }
    Ok(())
}

A line that is split comes out in pieces: within one tile, each run is its own slice (group them by tile to render a MultiLineString); across tiles, the feature’s attributes go with each tile’s piece. Slicer<Measured<M>> carries per-vertex M alongside. 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*/); tile_polygon and polygon (its fill runs expanded into fill rings) must produce identical output, also checked on finer grids and under every rotation and mirror image. Point fixtures in tests/points/fixtures/ are snapshotted the same way; point, tile_point, and the closed buffered box rule must agree. The fixtures’ multi-geometries are sliced one element at a time, as a caller would. Run just bless to regenerate snapshots. To inspect them, run just visualize-tests and open tests/visualize.qgz in QGIS (every fixture and snapshot as a layer, over tests/grid.geojson, the tile grid offset 0.5px to sit between integer coordinates), or load the .geojson files in 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.

Structs§

FillRun: A horizontal run of tiles lying entirely inside the polygon: row y, columns x.start..x.end.
LineSlice: One run of a line in one tile: a contiguous piece of it, in the tile’s local frame.
LineSlices: Lazy iterator over the runs of a line in every tile it touches; see Slicer::line.
Local: Vertices in a tile’s local frame — v − origin, computed as they are read — every position checked to fit i32 before the slice is handed out.
LocalIter: Iterator over a Local’s vertices.
Measured: A Vertex carrying a measure/payload m (e.g. an M value) alongside its integer position.
Mosaic: Reassembles tiled polyline features back into whole features as tiles are added.
PointSlice: A point in one tile, in the tile’s local frame.
PointSlices: The tiles a point lands in, with the point in each; see Slicer::point. One to four items, columns first, computed with a single division per axis.
PolygonMosaic: Reassembles tiled polygon features back into whole rings as tiles are added — the accumulating inverse of the polygon slicer.
PolygonPiece: One polygon’s rings in one tile: exterior first, then its holes that reach the tile.
PolygonSlices: Lazy iterator over the slices of a polygon in every tile it reaches; see Slicer::polygon.
Slicer: Slices one geometry at a time into per-tile pieces on an integer grid, lazily.
TileId: A tile address on the integer grid. Coordinates may be negative.
TileLines: Lazy iterator over the runs of a line in one tile; see Slicer::tile_line.

Enums§

PolygonSlice: One slice of a polygon.
TileError: Something the slicer or combiner cannot process. Returned in place of a panic or a silently-wrong result.

Traits§

PolyVertex: A Vertex the polygon slicer can also synthesize at a chosen position, for the clip-boundary corner vertices it must insert to keep a clipped ring closed.
Vertex: A polyline vertex the slicer can clip: an integer position plus an opaque Copy + PartialEq payload that is preserved verbatim through slicing and merging.

Functions§

signed_area_2x: Twice the signed area of ring (the shoelace sum Σ xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ), exact for any i32 ring. Works whether or not the ring repeats its first vertex, and is 0 for a degenerate ring.