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§
- Density
Weight - 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’sSimplifyAlgorithmenum (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
pointsis ≤epsilon(a BFS finds the fewest hops from the first to the last point over the graph of “shortcut” segments that stay withinepsilonof every skipped point). - imai_
iri_ w imai_iri()with per-vertex multipliers: the deviation atpoints[i]stays ≤epsilon * weights[i]. AboveII_MAXpoints the RDP prefilter composes per point, so that bound is exact only whereweightsis locally ~constant across a prefilter shortcut (a negligible caveat for weights sampled from a coarse grid through a smooth map); the globalepsilon * 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 atpoints[i]stays ≤epsilon * weights[i].- simplify
- Dispatches on
Simplify. - simplify_
weighted simplify()with per-vertex tolerance multipliers: the effective parameter atpoints[i]isparam * weights[i](for Visvalingam,min_area * weights[i]²). Callers pass one strictly positive weight per point; all-ones weights reproducesimplify().- 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²).