Skip to main content

Crate map_tile_toolkit

Crate map_tile_toolkit 

Source
Expand description

§map-tile-toolkit

GitHub repo crates.io version crate usage docs.rs status crates.io license CI build status Codecov

Slice integer lines, points and polygons into per-tile pieces on a square tile grid, keeping the geometry’s original vertices. A line never gets a new vertex; a polygon ring gets only synthetic corners outside the tile, to stay closed. Each tile may have a buffer (under half a tile), which widens the box a tile keeps and the geometry neighboring tiles share. Mosaic and PolygonMosaic reassemble the tiles into whole features, exactly: unlike clippers that cut new vertices at the tile edge (Sutherland–Hodgman, geo’s boolean ops), a segment crossing a border is the same original segment in both tiles.

§Usage

Slicer takes one geometry at a time and returns a lazy iterator over its slices:

  • line, point, polygon — every tile the geometry reaches, even tiles holding none of its vertices;
  • tile_line, tile_point, tile_polygon — one given tile, exactly what the first call yields there.

Each slice is computed only when the iterator reaches it, so stopping early stops the work. A line run borrows the caller’s vertices, so a line with millions of vertices costs no extra memory. Slices come in no particular order, and a line that leaves a tile and comes back gives it several runs. 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(())
}

§Lines

A vertex is kept when one of its two segments touches the tile’s buffered box, and a run breaks only where a vertex is dropped. So a run ends at the first vertex past the edge, a segment crossing the tile keeps both its outside ends, a single segment outside is bridged, and only a longer excursion splits the line into several runs:

Which line vertices a tile keeps

§Polygons

polygon(&rings) and tile_polygon(tile, &rings) take one polygon as its rings, exterior first. A tile gets one piece: the exterior and the holes reaching the tile, each ring closed (its first vertex repeated; drop it for an MVT ClosePath) and wound like the input.

A ring keeps every vertex with an edge touching the buffered box. Where it leaves the box and comes back, its outside vertices are compared with the synthetic corners a detour winding around the tile the same way would need: with more vertices, the detour replaces them (a straight chord when it needs no corner), otherwise they are kept. A tile the polygon covers gets just the four corners, and a tile inside a hole gets nothing. Synthetic corners sit one unit outside the buffered box, at tile-local -buffer - 1 or extent + buffer, so they never land in it.

Which polygon vertices a tile keeps

Each ring is clipped on its own, so a hole crossing the tile keeps its outside vertices even where the exterior was cut short: past the box, the hole can reach outside the exterior. A piece is therefore technically invalid geometry, but only outside the buffered box; what a renderer draws, clipped to the tile (as MVT renderers do), is valid. Measured on random valid polygons with holes, 11.6% of pieces fail OGC validation there: a hole outside the exterior, an exterior and a hole detouring along the same line, or two detours of one ring crossing. Making the outside valid too would need hole-aware detours and a separate route per excursion, which slow the sweep and still miss cases, for no visible gain. Consumers needing OGC-valid pieces should clip them with a general-purpose clipper.

The polygon is sliced row by row: the call reads the rings once, to bound and index them, and the iterator then holds one tile row at a time (a polygon inside one tile is lent as it is). Tiles the polygon covers entirely come as FillRun { y, x } row spans, so cost grows with the perimeter, not the area. fill_ring(&run) is the one ring each of those tiles holds: the four corners, closed. Pieces are built in the slicer’s reused buffer, so the iterator is lending (loop with while let) and polygons need &mut Slicer. Reuse one slicer per worker: it stops allocating once warmed up, and shrink_to_fit() releases what an outlier left behind.

signed_area_2x gives a ring’s exact orientation, to normalize winding once per feature. MVT wants 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(())
}

§Points

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. The iterator knows its length (one to four). tile_point(tile, p) returns the point in one tile’s frame, 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(())
}

§Unclipped

A slicer built with_clip_mode(ClipMode::Unclipped) gives each tile a line or polygon reaches (exactly the tiles the default Clipped mode gives anything) the whole geometry once, in that tile’s frame, for renderers that clip themselves. The calls and items are the same, so one consumer loop serves both modes: a line comes as one LineSlice per tile holding all of it, and a polygon as one PolygonPiece per tile with all its rings, in covered tiles too (no FillRun). Slices borrow the input, so the slicer’s cost is finding the tiles; to give a line’s tile just once it keeps a set of the tiles found so far. The consumer pays the whole geometry per tile. Points are unaffected.

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

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

    // Tiles (0, 0), (1, 0) and (2, 0), each holding the whole line in its own frame.
    let mut tiles: Vec<_> = slicer
        .line(&line)?
        .map(|slice| (slice.tile(), slice.run().to_vec()))
        .collect();
    tiles.sort_unstable_by_key(|(tile, _)| *tile);
    assert_eq!(tiles.len(), 3);
    assert_eq!(
        tiles[1],
        (TileId::new(1, 0), vec![coord! { x: -20, y: 5 }, coord! { x: 35, y: 10 }])
    );
    Ok(())
}

§Multi-geometries and attributes

The slicer has no multi-geometries and no feature attributes. Slice a MultiLineString, MultiPoint or MultiPolygon one element at a time, and pair every slice with its feature’s id and properties: the caller does that per tile anyway, and it keeps the slicer free of state that grows with the feature. Slices of several elements landing in one tile are several slices there, which the caller groups (into one MultiLineString per tile, say). See examples/mvt_features.rs for a round trip emitting per-tile GeoJSON with ids and properties.

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(())
}

Per-vertex data is the Vertex type instead (default Coord<i32>): Measured<M> pairs a position with any Copy + PartialEq payload (an M value, an id), which rides through slicing and merging unchanged. A polygon’s synthetic corners carry M::default().

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(())
}

§Coordinate space

The slicer is integer-only: extent is both the tile side and its output resolution (the vector-tile extent). Vertex x belongs to tile x.div_euclid(extent), whose own area is [0, extent) in its local frame x − tile · extent; buffer vertices, a line’s first vertex past an edge and synthetic corners lie outside it. Add tile · extent to get global coordinates back. Do float and projection work up front (e.g. with geo); for web mercator at zoom z, project, simplify, then scale by 2^z · extent / circumference, move the top-left corner to the origin, flip y, and round, landing in [0, 2^z · extent).

§Limits

A segment is walked through exactly the tiles it touches, so cost follows those tiles, not its bounding box: a world-spanning diagonal at z14 (extent 4096) touches about 35,000 tiles. Each call bounds the geometry first and returns any error then, so the iterators cannot fail midway (except as noted):

  • i32 coordinates (Overflow): 2^z · extent must fit (up to z18 at extent 4096), and so must the buffered box of every tile the geometry reaches. 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, and u32::MAX vertices per piece; the last is the one error a polygon iterator can yield.

There is no limit on how many tiles a geometry reaches: memory stays bounded, and the work is only what the caller pulls.

§Merging tiles back

Mosaic is the inverse of Slicer::line: add each tile’s runs, in its local frame, and it reassembles whole features across tile borders, in the global frame. Not every tile is needed. It rejects a tile inconsistent with those already added (a shared segment that differs, or a tile that owns a vertex but lacks its segment), names the conflicting tiles, and stays unchanged. purge drops a tile, and iter_features walks the features. PolygonMosaic does the same for polygon pieces: it keeps only the ring edges touching each tile’s buffered box (so it needs the buffer too), which drops every synthetic edge, since those lie strictly outside it.

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(())
}

§Development

This project uses just: just lists the commands, just test runs the tests, and just bless regenerates the snapshots. Tests are data-driven: every fixture in tests/{polylines,polygons,points}/fixtures/ is sliced by both the all-tiles and the one-tile calls, which must agree, also clipped and unclipped. The results are snapshotted as GeoJSON that renders on a map; just visualize-tests builds tests/visualize.qgz to inspect them all in QGIS, over the tile grid in tests/grid.geojson.

§License

Licensed under either of

§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 (all of them, and each whole, when unclipped).
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§

ClipMode
How a Slicer cuts lines and polygons into the tiles they reach (points are never cut, so they ignore it).
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.