polyline-deduper

Collapse an overlapping set of polylines into a minimal set of segments, each carrying an accumulated weight. Format-agnostic (GeoJSON, encoded polylines, or raw coordinate arrays), zero runtime dependencies, and fast enough to run client-side on large datasets.

The core never sees a string or a GeoJSON object — codecs normalize input to integer vertex IDs, the algorithm runs on those, and codecs re-encode the output. Output is canonical (deterministic, independent of input order).

Install

npm install polyline-deduper

Quick start

import { dedupe, type Feature } from 'polyline-deduper'

// GeoJSON in, GeoJSON out, weighted heatmap.
// The generic types `f` so `f.properties` is checked (see "typed groupBy/weightBy" below).
const heatmap = dedupe<Feature<{ legCount?: number }>>(featureCollection, {
  input: 'geojson',
  output: 'geojson',
  weighted: true,
  weightBy: f => f.properties?.legCount ?? 1,
})
// heatmap.features[i].properties.weight → drive a line-width / color ramp

// Encoded polylines in (Mapbox precision 6), polylines out
const compact = dedupe(['mfp_I~ps|U_ulL...', '...'], {
  input: 'polyline',
  inputPrecision: 6,
  output: 'polyline',
  outputPrecision: 6,
})

How it works

Two linear phases:

1. Accumulate. Intern each vertex to an integer ID; for every edge, weight[edge] += contribution. A pure hash add — no splitting, no findIndex.
2. Assemble. Greedily chain adjacent edges of the same (group, weight) class while the shared vertex has degree 2. Boundaries land exactly at weight/group changes and junctions → canonical output.

• Time: O(total edges) to accumulate + O(total edges) to assemble.
• Space: O(unique vertices) + O(unique edges).

API

function dedupe(data: DedupeInput, options?: DedupeOptions): DedupeOutput

interface DedupeOptions {
  /** Input codec. Inferred when omitted (string[]→polyline, FeatureCollection→geojson). */
  input?: 'geojson' | 'polyline' | 'coords'
  /** Output codec. Defaults to the input format. */
  output?: 'geojson' | 'polyline' | 'coords'

  /** Decimal digits for decoding encoded polylines. 5 = Google, 6 = Mapbox. Default 5. */
  inputPrecision?: number
  /** Decimal digits for encoding output polylines. Default = inputPrecision. */
  outputPrecision?: number

  /** Vertex-identity grid (decimal digits). Coarser than data precision merges
   *  near-coincident vertices from different sources. Default = inputPrecision. */
  snap?: number

  /** Accumulate weights and split chains where weight changes (heatmap mode).
   *  When false, merge geometry within a group regardless of weight (draw-reduction
   *  mode); reported weight is the heaviest contributing edge. Default true. */
  weighted?: boolean

  /** Edges only merge within the same group key. Use to keep colors/modalities separate. */
  groupBy?: (item: unknown) => string
  /** Weight each source line contributes to its edges. Default () => 1. */
  weightBy?: (item: unknown) => number

  /** Unwrap antimeridian crossings so segments don't draw across the whole map. Default true. */
  fixAntimeridian?: boolean
}

The return type is narrowed by options.output, so you never cast:

const fc   = dedupe(routes, { output: 'geojson' })  // FeatureCollection
const lines = dedupe(routes, { output: 'polyline' }) // PolylineFeature[]
const coords = dedupe(routes, { output: 'coords' })  // CoordFeature[]

dedupe is generic over the input item, so groupBy / weightBy are typed:

import { dedupe, type Feature } from 'polyline-deduper'
dedupe<Feature<{ legCount: number }>>(routes, {
  weightBy: f => f.properties!.legCount, // f fully typed
})

Weight classes for rendering

getClasses turns a list of weights into break thresholds for a discrete ramp; classify maps a weight to its class index.

import { getClasses, classify } from 'polyline-deduper'

const weights = segments.map(s => s.weight)
const breaks = getClasses(weights, 5, 'quantile') // 'quantile' | 'linear' | 'log'
const cls = classify(weights[0], breaks)          // 0 .. 4

Examples

• examples/basic.mjs — runnable with node examples/basic.mjs (it imports the built dist/; from a source checkout run npm run build first, an installed package already ships dist/).
• examples/mapbox-heatmap.md — Mapbox GL line-width/line-color ramp.

Advanced

The lower-level building blocks are exported for custom pipelines or incremental recompute: buildGraph, assemble, Interner, decode, encode, decodePolyline, encodePolyline, unwrap.

Modes

| Use case | weighted | groupBy | Notes | |---|---|---|---| | Total heatmap | true | const '' | weightBy = leg count; ramp line-width/line-color on properties.weight. | | Connectivity draw-reduction | false | f => f.properties.classColor | Merges shared lanes within a color; fewer/longer features, color preserved. |

import { dedupe, type Feature } from 'polyline-deduper'

// Heatmap
dedupe<Feature<{ legCount?: number }>>(featureCollection, {
  weighted: true,
  weightBy: f => f.properties?.legCount ?? 1,
})

// Modality-aware draw reduction
dedupe<Feature<{ classColor?: string }>>(featureCollection, {
  weighted: false,
  groupBy: f => f.properties?.classColor ?? '',
})

Limitations

1. Merge mode is lossy on source identity. A merged segment reports only group + weight, not which source lines crossed it.
2. snap precision is a tradeoff. Too coarse merges distinct nearby lanes; too fine fails to merge near-coincident vertices from different sources.

License

MIT