Computing a Dirty Tile List from an .osc File

Re-cutting every tile after a minutely diff is impossible and re-cutting only the tiles containing the new geometry is wrong, because a feature that moved is still drawn where it used to be.

Prerequisites

Conceptual minimum

A dirty tile list is the set of tile coordinates whose rendered content would differ if re-cut now. Deriving it involves three expansions, each of which is a common place to stop too early.

Expand over both geometries. The union of the pre-edit and post-edit geometry is what changed visually. A building demolished in place has no post-edit geometry at all, and a shop that moved two streets away dirties both streets. Using only the new geometry is the single most common cause of a tile cache that slowly accumulates ghosts.

Expand over zooms. A feature rendered from zoom 6 to zoom 14 dirties tiles at every one of those zooms. That is not eight tiles; a way spanning several zoom-14 tiles occupies fewer tiles as zoom decreases, so the count is dominated by the highest zoom, and the total for a long motorway can be in the thousands.

Expand by buffer. Tile cutting usually includes a buffer beyond the tile edge so that labels and lines crossing the boundary render correctly. A feature just outside a tile can therefore affect it, so the invalidation must grow the geometry by the same buffer the cutter uses, expressed in the tile’s own units.

The counterweight to all this expansion is collapse. A list of a million dirty zoom-14 tiles in one metropolitan area is better expressed as the handful of zoom-10 tiles containing them, and re-cutting at the parent level costs less than servicing each child. A threshold on children per parent gives that collapse cheaply.

The three expansions, and what stopping early costs Three panels. Expanding over both the old and new geometry catches features that moved or were deleted, and stopping at the new geometry alone leaves the old rendering in place indefinitely, which is the ghost-building failure. Expanding over every rendered zoom catches the whole column of tiles a feature appears in, and stopping at the maximum zoom leaves lower zooms showing the previous state. Expanding by the cutter's buffer catches tiles a feature affects without entering, and stopping at strict containment leaves clipped labels and broken lines at tile edges. Three expansions, three failures Old and new Catches moves and deletes Stop early: ghosts remain Deleted features persist The commonest bug Every zoom A column, not one tile Stop early: low zooms stale Overviews lag for weeks Rarely noticed quickly Plus buffer Neighbours are affected Stop early: edge artefacts Labels clipped at seams Lines break across tiles Each failure is visually subtle and geographically local, so it is reported by users long before it is caught by monitoring.
All three expansions grow the list; the collapse step is what keeps it usable.

Runnable solution

python 
from __future__ import annotations

import logging
from collections import Counter
from collections.abc import Iterable, Iterator
from dataclasses import dataclass

from shapely.geometry import base as shapely_base

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.tiles.dirty")

MIN_ZOOM, MAX_ZOOM = 6, 14
BUFFER_PX = 64          # must match the cutter's buffer, not merely resemble it
TILE_PX = 4096
COLLAPSE_AT = 12        # children dirty under one parent -> dirty the parent


@dataclass(frozen=True)
class Tile:
    z: int
    x: int
    y: int


@dataclass(frozen=True)
class ChangedFeature:
    osm_type: str
    osm_id: int
    old_geom: shapely_base.BaseGeometry | None   # None only for a create
    new_geom: shapely_base.BaseGeometry | None   # None only for a delete
    min_zoom: int = MIN_ZOOM                      # from the layer's schema


def _lonlat_to_tile(lon: float, lat: float, z: int) -> tuple[int, int]:
    import math
    n = 2 ** z
    x = int((lon + 180.0) / 360.0 * n)
    lat_r = math.radians(max(-85.05112878, min(85.05112878, lat)))
    y = int((1.0 - math.asinh(math.tan(lat_r)) / math.pi) / 2.0 * n)
    return max(0, min(n - 1, x)), max(0, min(n - 1, y))


def tiles_for_bounds(bounds: tuple[float, float, float, float],
                     z: int) -> Iterator[Tile]:
    west, south, east, north = bounds
    x0, y0 = _lonlat_to_tile(west, north, z)
    x1, y1 = _lonlat_to_tile(east, south, z)
    for x in range(min(x0, x1), max(x0, x1) + 1):
        for y in range(min(y0, y1), max(y0, y1) + 1):
            yield Tile(z, x, y)


def buffered_bounds(geom: shapely_base.BaseGeometry, z: int
                    ) -> tuple[float, float, float, float]:
    """Grow by the cutter's buffer, expressed in degrees at this zoom.

    A feature outside a tile still affects it when the cutter reads a margin
    beyond the tile edge, which every renderer does for labels and joins.
    """
    degrees_per_tile = 360.0 / (2 ** z)
    pad = degrees_per_tile * BUFFER_PX / TILE_PX
    west, south, east, north = geom.bounds
    return (west - pad, south - pad, east + pad, north + pad)


def dirty_tiles(features: Iterable[ChangedFeature]) -> set[Tile]:
    dirty: set[Tile] = set()
    for feature in features:
        # BOTH geometries. Where it was and where it is are both now wrong.
        for geom in (feature.old_geom, feature.new_geom):
            if geom is None or geom.is_empty:
                continue
            for z in range(feature.min_zoom, MAX_ZOOM + 1):
                dirty.update(tiles_for_bounds(buffered_bounds(geom, z), z))
    logger.info("expanded to %d dirty tile(s)", len(dirty))
    return dirty


def collapse(dirty: set[Tile], threshold: int = COLLAPSE_AT) -> set[Tile]:
    """Replace many dirty children with their parent.

    Re-cutting one parent costs less than servicing a dozen children, and a
    metropolitan edit session otherwise produces a list nobody can drain.
    """
    result = set(dirty)
    for z in range(MAX_ZOOM, MIN_ZOOM, -1):
        level = [t for t in result if t.z == z]
        parents = Counter(Tile(z - 1, t.x // 2, t.y // 2) for t in level)
        for parent, count in parents.items():
            if count < threshold:
                continue
            result -= {t for t in level
                       if t.x // 2 == parent.x and t.y // 2 == parent.y}
            result.add(parent)
    logger.info("collapsed to %d tile(s)", len(result))
    return result


def queue(dirty: Iterable[Tile], store, sequence: int) -> int:
    """Record, do not re-cut. Popularity decides what is worth the work."""
    count = 0
    for tile in sorted(dirty, key=lambda t: (t.z, t.x, t.y)):
        store.mark_dirty(tile.z, tile.x, tile.y, sequence)
        count += 1
    logger.info("queued %d dirty tile(s) at sequence %d", count, sequence)
    return count


if __name__ == "__main__":
    logger.info("expand over both geometries, all zooms, plus buffer; collapse")

Step-by-step walkthrough

  1. Capture the old geometry before applying. Once the diff lands, a deleted feature’s geometry is gone and its tiles can never be identified. This is an ordering requirement on the whole loop, not a detail of this function.
  2. Iterate both geometries. A create has no old geometry and a delete has no new one; a modification usually has both and they may be far apart.
  3. Respect the layer’s minimum zoom. A footpath rendered only from zoom 15 should not dirty zoom 6, and the schema already states this.
  4. Match the cutter’s buffer exactly. Approximating it produces edge artefacts that appear only at tile seams and are miserable to diagnose.
  5. Use bounds rather than exact coverage, at first. Bounds over-invalidate for diagonal linework, and the extra tiles cost less than the exact computation for all but the largest features.
  6. Collapse upward from the deepest zoom. Working downward lets a collapse at one level feed the next, which is what turns a metropolitan edit session into a tractable list.
  7. Queue rather than re-cut. Marking a tile dirty and letting requests or a background drainer service it means unvisited tiles cost nothing, which across a pyramid is most of them.
  8. Record the sequence with each mark. A tile dirtied at sequence N and re-cut afterwards is clean; without the sequence you cannot tell re-cut from never-dirty.
Tile count by zoom for one motorway edit, before collapse A bar chart of how many tiles a single edited motorway segment dirties at each rendered zoom. At zoom six the feature falls within about two tiles. At zoom eight it spans roughly six. At zoom ten around twenty. At zoom twelve around eighty. At zoom fourteen around three hundred and twenty. The count roughly quadruples with each zoom level, so the deepest zoom dominates the total and is where an upward collapse repays most. Tiles dirtied per zoom, one motorway edit Zoom 6 (overview) 2 tiles Zoom 8 (regional) 6 tiles Zoom 10 (metro) 20 tiles Zoom 12 (district) 80 tiles Zoom 14 (street) 320 tiles Roughly ninety percent of the list lives at the deepest two zooms, which is exactly where a parent collapse removes the most work.
One edit, four hundred and twenty-eight tiles, before any buffer expansion is applied.
From change file to a queued dirty list Four steps. The change file is filtered against the tile schema so edits touching keys no layer reads are discarded before any geometric work. Each surviving feature is expanded over the union of its old and new geometry, across every zoom the layer renders at, padded by the cutter buffer. The expanded set is collapsed upward, replacing a parent tile coordinate whenever enough of its children are dirty, which is what keeps a dense urban editing session tractable. The collapsed set is queued with the upstream sequence recorded against each mark, and a drainer or an incoming request services it later. Filter, expand, collapse, queue filter schema keys only most edits discarded expand both geoms, all zooms plus cutter buffer collapse children to parents deepest zoom first queue sequence per mark serviced on demand Expansion and collapse pull in opposite directions on purpose: correctness first, then a list somebody can actually drain.
Skipping the first step makes the second one do geometric work for edits that change no pixel.

Verification

  • A move dirties both locations. Relocate a test feature and confirm tiles at the old position appear in the list.
  • A delete dirties anything at all. A pipeline deriving after the apply produces an empty list here, which is the diagnostic.
  • Zoom coverage matches the schema. Confirm no tiles below the layer’s minimum zoom are marked.
  • Collapse reduces the count. Feed a dense urban diff and confirm the collapsed list is materially smaller.
  • Re-cut tiles come back clean. Render a dirtied tile and confirm the output differs from the cached version.

Common errors and fixes

Symptom Root cause One-line fix
Demolished buildings still rendered Only new geometry expanded Union the old and new geometry
Deletes dirty nothing Derivation runs after the apply Capture old geometry before applying
Low-zoom tiles show old data Expansion limited to maximum zoom Iterate the full rendered zoom range
Broken lines at tile seams Buffer not matched to the cutter Expand bounds by the cutter’s exact buffer
Dirty list grows faster than it drains No upward collapse Collapse children to parents past a threshold
Footpaths dirty continental tiles Layer minimum zoom ignored Start expansion at the layer’s own minimum zoom
Cannot tell re-cut from never-dirty No sequence recorded per mark Store the sequence alongside each dirty mark

Specification reference

In the Web Mercator tiling scheme, zoom level z divides the world into 2^z by 2^z tiles, with tile x increasing eastward from the antimeridian and tile y increasing southward from approximately 85.0511 degrees north. Vector tile cutters typically extend geometry beyond the tile envelope by a buffer, expressed in tile-local units, so that features crossing the boundary render without visible seams. See the Mapbox Vector Tile specification and the Slippy Map tilenames convention.

Frequently Asked Questions

Should the dirty list use exact geometry coverage rather than bounds?

Only where bounds are badly wasteful, which in practice means very long diagonal features. A coastline or a trunk road’s bounding box covers a great deal of sea or countryside it never enters, and at deep zooms that is thousands of tiles invalidated for nothing. For everything else the exact computation costs more than the tiles it saves. A reasonable rule is to use bounds by default and exact coverage above a bounding-box area threshold.

How is a dirty tile actually re-cut?

Either on request, when a viewer asks for a tile marked dirty and the server re-cuts before responding, or by a background worker draining the list in priority order. The first gives correctness with a latency spike on the first request; the second gives consistent latency at the cost of rendering tiles nobody wants. Most production setups do both, with the background drainer working through recently requested tiles first.

What about tiles that no longer contain anything?

They still need re-cutting, and they are the case people forget. A tile whose only feature was deleted must be regenerated as empty, because the cached version still shows the feature. An empty tile is cheap to store and cheap to serve, but it has to exist — serving a 404 for a tile that was previously populated makes clients fall back to the last successful response in some implementations.

Does a tag-only edit dirty tiles?

If the tag participates in the tile schema, yes, and with the same geometric extent as a geometry edit. If it does not, the edit should be filtered out before any expansion, which is usually the largest available saving because most tag edits touch keys no renderer reads. That filter needs the schema’s key list, which is one more reason for the schema to be data rather than code.

Up one level: Incremental Updates for Derived Datasets.