Skip to main content

Crate utz_simplify

Crate utz_simplify 

Source
Expand description

Open-polyline simplification algorithms, shared between the builder (utz_build, whose per-arc pass is topology-aware) and the tuning-viewer HTML (compiled to WASM so the browser preview runs the exact code the builder runs, with no JS reimplementation drift).

All functions take an open polyline, always keep both endpoints, and return ≥ 2 points. Units are the caller’s (the builder works in degrees; convert meters with ~111 320 m/deg and areas with its square). Three algorithms are on the menu:

  • rdp() is Ramer–Douglas–Peucker (Ramer 1972; Douglas & Peucker 1973), which guarantees a max perpendicular deviation ≤ ε. It is the default.
  • visvalingam() is Visvalingam–Whyatt (1993), which iteratively drops the point spanning the smallest triangle. Its parameter is an area, not a distance: there is no ε-style deviation bound, but the result is often a cartographically nicer caricature at the same vertex budget.
  • imai_iri() is Imai–Iri (1988), which finds the provably minimum number of vertices for a given deviation bound ε (the shortest path over the shortcut graph). It gives the same guarantee as RDP with fewer-or-equal points and more build time.

Corridor/streaming algorithms (Reumann–Witkam, Opheim, Lang, Zhao–Saalfeld) were considered and rejected: they trade quality-per-vertex for single-pass speed, which is worthless at build time.

Each algorithm also has a weighted variant (simplify_weighted(), *_w): a per-vertex tolerance multiplier weights[i] makes the effective parameter epsilon * weights[i] (for Visvalingam it is min_area * weights[i]², because areas scale as distance²). The builder uses this for population-density-aware refinement: denser areas get smaller multipliers, so boundaries stay precise where people live. weights[i] = 1.0 everywhere reproduces the scalar functions exactly.

Structs§

DensityWeight
The map from population density to tolerance multiplier: the weight() method takes a density in people/km² and returns the multiplier to apply to the simplification tolerance there. The map is shared by the builder and the live viewer (it is compiled into the WASM module so the browser’s weighting slider runs the same code).

Enums§

Simplify
The algorithm choice and its parameter, for callers that thread the choice through knobs.

Constants§

ALGORITHM_IMAI_IRI
ALGORITHM_NONE
The algorithm codes Simplify::from_code() accepts, which are also the WASM exports’ ABI ids. They match the header bytes of the asset format’s SimplifyAlgorithm enum (utz_common), pinned by a dev-dependency test rather than a real dependency: this crate stays dependency-free.
ALGORITHM_RDP
ALGORITHM_VISVALINGAM

Functions§

imai_iri
Runs Imai–Iri: it returns the minimum-vertex polyline whose deviation from points is ≤ epsilon (a BFS finds the fewest hops from the first to the last point over the graph of “shortcut” segments that stay within epsilon of every skipped point).
imai_iri_w
imai_iri() with per-vertex multipliers: the deviation at points[i] stays ≤ epsilon * weights[i]. Above II_MAX points the RDP prefilter composes per point, so that bound is exact only where weights is locally ~constant across a prefilter shortcut (a negligible caveat for weights sampled from a coarse grid through a smooth map); the global epsilon * max(weights) bound always holds.
rdp
Runs Ramer–Douglas–Peucker, keeping both endpoints; the result has ≥ 2 points.
rdp_w
rdp() with per-vertex multipliers: the deviation at points[i] stays ≤ epsilon * weights[i].
simplify
Dispatches on Simplify.
simplify_weighted
simplify() with per-vertex tolerance multipliers: the effective parameter at points[i] is param * weights[i] (for Visvalingam, min_area * weights[i]²). Callers pass one strictly positive weight per point; all-ones weights reproduce simplify().
visvalingam
Runs Visvalingam–Whyatt: it repeatedly removes the interior point whose triangle (prev, point, next) has the smallest area, while that area is < min_area. Ties break on the lower index for reproducible builds.
visvalingam_w
visvalingam() with per-vertex multipliers: points[i] is dropped while its triangle area is < min_area * weights[i]² (areas scale as distance²).