@mapbox/graph-normalizer

Graph-normalizer

graph-normalizer is a Command Line Interface that pipes in a geojson file of ways (usually at the z7 level), and outputs normalized pieces of graph at a given zoom level.

This package is intended as a utility for graph-tiler, but can be used on its own.

Installation

npm install @mapbox/graph-normalizer

Usage

node_modules/graph-normalizer/bin/normalize-ways \
  --waysFile <geojson line-delimited ways file> \
  --outputPath <output path> \
  --zoomLevel <output zoom level - default 14> \
  --mergeHighways <optional - merge ways with different highway tags - default false> \
  --mergeTunnels <optional - merge ways with different tunnel tags - default false> \
  --mergeBridges <optional - merge ways with different bridge tags - default false>

The output is a number of files, named <quadkey>.json, of line-delimited geojson way features.

It satisfies the following constraints:

• All way geometries in the original road network have an equivalent in the normalized graph.
• No intersection ever lies within a normalized way, only at its ends.
• Normalized way ids keep track of the history of transformations that led to it.
• highway, oneway, bridge and tunnel tags are conserved from the original graph by default.
• highway, bridge and tunnel tags can be merged using optional arguments. When merging different tags:
  • highway tag is set as unclassified
  • tunnel tag is set to yes i.e. we keep the info that there is a tunnel in the merged way
  • bridge tag is set to yes i.e. we keep the info that there is a bridge in the merged way

Edges that are shared by multiple tiles are conserved in all of them.

It is recommended to keep the output zoom level high, as performance might drop when trying to normalize at a larger scale.

Algorithm

graph-normalizer expects geojson LineString features that have a refs property, each ref corresponding to the node id of the matching coordinates in the geometry.coordinates array.

Any way that does not respect this constraint will be dropped.

The algorithm follows this workflow:

• Indexing - It loads the ways into memory and indexes their segments into the quadkey(s) of the target zoom level in which they land.

• Tiling - For each quadkey, it reconstructs each way from its segments. The segments of the original way that do not intersect with the tile are effectively dropped from this tile. Conversely, any segment that overlaps multiple tiles will be duplicated in all tiles.

• Splitting - Having the ways from each quadkey, graph-normalizer then splits the ways that traverse an intersection into two. !<i> is appended to the way id where i is the index of the split way in the original geometry.

• Merging - Ways that share a node which is not an intersection (only 2 way owners) are merged together. The resulting id is <wayOne>,<wayTwo>.

Tests

npm test

Benchmarks

npm run bench