lddl/osm2ch

Convert OSM-file to graph for contraction hierarchies

osm2ch

Convert *.osm.pbf files to CSV for contraction hierarchies library

• osm2ch
  • Convert *.osm.pbf files to CSV for contraction hierarchies library
  • About
  • Installation
  • Usage
  • Example
  • Dependencies
  • License

About

With this CLI tool you can convert *.osm.pbf (Compressed Open Street Map) file to CSV (Comma-Separated Values) file, which is used in our contraction hierarchies library. What it does:

• Edge expansion (single edge == single vertex);
• Handles some kind and types of restrictions:
  • Supported kind of restrictions:
    • EdgeFrom - NodeVia - EdgeTo.
  • Supported types of restrictions:
    • only_left_turn;
    • only_right_turn;
    • only_straight_on;
    • no_left_turn;
    • no_right_turn;
    • no_straight_on.
• Saves CSV file with geom in WKT format;
• Currently supports tags for 'highway' OSM entity only.

PRs are welcome!

Installation

• Via 'go get':

  go get github.com/LdDl/osm2ch
  go install github.com/LdDl/osm2ch/cmd/[email protected]

  After installation step is complete you can call 'osm2ch' from any place in your system.

• Or download prebuilt binary and make updates in yours PATH environment varibale (both Linux and Windows):

  • Windows - https://github.com/LdDl/osm2ch/releases/download/v1.5.1/windows-osm2ch.zip
  • Linux - https://github.com/LdDl/osm2ch/releases/download/v1.5.1/linux-amd64-osm2ch.tar.gz

Note: There is zlib support in OSM-pbf parser. If you do not want use it then disable CGO:

export CGO_ENABLED=0
# Then build osm2ch from source

Usage

osm2ch -h

Output:

Usage of osm2ch:
  -file string
        Filename of *.osm.pbf file (it has to be compressed) (default "my_graph.osm.pbf")
  -geomf string
        Format of output geometry. Expected values: wkt / geojson (default "wkt")
  -out string
        Filename of 'Comma-Separated Values' (CSV) formatted file (default "my_graph.csv")
        E.g.: if file name is 'map.csv' then 3 files will be produced: 'map.csv' (edges), 'map_vertices.csv', 'map_shortcuts.csv'
  -tags string
        Set of needed tags (separated by commas) (default "motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link,motorway_link")
  -units string
        Units of output weights. Expected values: km for kilometers / m for meters (default "km")
  -contract
        Prepare contraction hierarchies? (default true)

The default list of tags is this, since usually these tags are used for routing for personal cars.

Example

You can find example file of *.osm.pbf file in nested child /example_data.

If you want WKT format for output geometry:

osm2ch --file example_data/moscow_center_reduced.osm.pbf --out graph.csv --geomf wkt --units m --tags motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link,motorway_link --contract=true

If you want GeoJSON format for output geometry:

osm2ch --file example_data/moscow_center_reduced.osm.pbf --out graph.csv --geomf geojson --units m --tags motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link,motorway_link --contract=true

If you dont want to prepare contraction hierarchies then:

osm2ch --file example_data/moscow_center_reduced.osm.pbf --out graph.csv --geomf wkt --units m --tags motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link,motorway_link --contract=false

After that files 'graph.csv', 'graph_vertices.csv', 'graph_shortcuts.csv' will be created (or only 'graph.csv' and 'graph_vertices' if 'contract' flag is set to False).

Header of edges CSV-file is: from_vertex_id;to_vertex_id;weight;geom;was_one_way;edge_id;osm_way_from;osm_way_to;osm_way_from_source_node;osm_way_from_target_node;osm_way_to_source_node;osm_way_to_target_node

• from_vertex_id - Generated source vertex;
• to_vertex_id - Generated target vertex;
• weight - Traveling cost from source to target (actually length of an edge in kilometers/meters);
• geom - Geometry of edge (Linestring) in WKT or GeoJSON format.
• was_one_way - Boolean value. When source OSM way was "one way" then it's true, otherwise it's false. Might be helpfull for ignore edges with WasOneWay=true when offesting overlapping two-way geometries in some GIS viewer
• edge_id - ID of generated edge
• osm_way_from - ID of source OSM Way
• osm_way_to - ID of target OSM Way
• osm_way_from_source_node - ID of first OSM Node in source OSM Way
• osm_way_from_target_node - ID of last OSM Node in source OSM Way
• osm_way_to_source_node - ID of first OSM Node in target OSM Way
• osm_way_to_target_node - ID of last OSM Node in target OSM Way

Header of vertices CSV-file is: vertex_id;order_pos;importance;geom

• vertex_id - Vertex;
• order_pos - Order position in contraction hierarchies;
• importance - Importance of vertex with respect to contraction hierarchies
• geom - Geometry of vertex (Point) in WKT or GeoJSON format.

[Optional] Header of shortcuts CSV-file is: from_vertex_id;to_vertex_id;weight;via_vertex_id

• from_vertex_id - Source vertex;
• to_vertex_id - Target vertex;
• weight - Traveling cost from source to target (actually length of the shortcut in kilometers/meters);
• via_vertex_id - ID of vertex through which the shortcut exists

Now you can use this graph in contraction hierarchies library.

Dependencies

Thanks to paulmach for his OSM-parser written in Go.

Paulmach's license is here (it's MIT)

License

• Please see here

osm2ch's Issues

[FEATURE REQUEST] Make graph simple as possible

Is your feature request related to a problem? Please describe.
There are too many generated edges/vertices after parsing OSM (via edge expansion). Contraction hierarchies algorithm could take very much time to process all set of vertices. I'd suggest to implement Edge contraction to reduce size of graph for further contraction hierarchies algorithm

Describe the solution you'd like and provide pseudocode examples if you can
Find all vertices with degree == 2. Then recursively:

while exists vertex v with degree 2:
    - remove v and the 2 outgoing edges
    - add a new edge between the neighbours of v
    - the weight of the new edge is the sum of the weights of the deleted edg

reference - https://stackoverflow.com/questions/54954644/algorithm-to-simplify-reduce-graph

Additional context

• Would be cool to have an optional flag for CLI (for debugging purposes) also
• Some numbers for "before" and "after" (kinda benchmark) on specific graph

[BUG] Index out of range

Describe the bug
Got next error

panic: runtime error: index out of range [2] with length 0
goroutine 1 [running]:
main.main()
        D:/hp/go/pkg/mod/github.com/!ld!dl/[email protected]/cmd/osm2ch/main.go:117 +0x1de5

To Reproduce
Just run in on random *.osm.pbf file

Expected behavior
This should not happen

Screenshots
nope

Desktop (please complete the following information):

• Win10
• 1.17
• Public OSM

Additional context
I guess the error is in https://github.com/LdDl/osm2ch/blob/master/cmd/osm2ch/main.go#L117

if _, ok := verticesGeoms[source]; !ok {
verticesGeoms[source] = osm2ch.GeoPoint{Lon: expEdge.Geom[0].Lon, Lat: expEdge.Geom[0].Lat}
}
if _, ok := verticesGeoms[target]; !ok {
verticesGeoms[target] = osm2ch.GeoPoint{Lon: expEdge.Geom[2].Lon, Lat: expEdge.Geom[2].Lat}
}

We need to handle case when .expEdge.Geom has not points in it (actually < 2)

[FEATURE REQUEST] export OSM id's

Is your feature request related to a problem? Please describe.
Current utlity doesn't export source OSM ids (way/node).

Describe the solution you'd like and provide pseudocode examples if you can
pseudocode'ish

expandedEdge{
    ID:        newEdgeID,
    Cost:      cost,
    Geom:      []geoPoint{a, b},
    WasOneWay: true,
    osm_way_id: %OSM_PARENT_WAY_ID%
    osm_node_ids: [%OSM_PARENT_NODE_ID_SOURCE%, %OSM_PARENT_NODE_ID_TARGET%]
}

And then export it into CSV as separate columns

Describe alternatives you've considered and provide pseudocode examples if you can
nope

Additional context
nope

[FEATURE REQUEST] Metadata export

Is your feature request related to a problem? Please describe.
In some situations it is needed more data from OSM tags/attributes such as: lanes number on a road, max speed restrictions, bus lanes, traffic lights and etc.

Describe the solution you'd like and provide pseudocode examples if you can

1. Add optional flag export_meta (default value is false)
2. If export_meta is true then export all processed tags/attirubutes to %filename_placeholder%_metainfo.csv
3. Proposed format:

type                    | object_id             | jsoned_tags_and_attributes

(either node or way)    | OSM object ID         | map[string]string of tag key/values pairs

Additional context
Any other suggestions are welcome

[FEATURE REQUEST] save contractions

Is your feature request related to a problem? Please describe.
Generated *.csv graph has't contraction edges actually.
I think we have to add option flag 'do_contraction=true/false' for some purposes (well, if you have really big graph you do not want to do contraction every time, just do it once and save it...)

Describe the solution you'd like and provide pseudocode examples if you can
Add flag.
If it is true => generate contraction hierarchies (call PrepareContracts())
Default value should be false.

Describe alternatives you've considered and provide pseudocode examples if you can
nope

Additional context
nope

[DOCUMENTATION] Library restrictions

While trying to run osm2ch on large datasets like europe-latest.osm.pbf, the process keeps killing itself after some time. Even on a large cloud based machine, the resources quickly reach to max and OS eventually kills the process. Are there any performance benchmarks available? Are there any recommendations for processing large files? Is there a way to limit the use of memory and work with a mix of disk, ram and cpu instead?

[BUG] Getting error while converting pbf to csv

Getting following output

[FEATURE REQUEST] Optional cost function

Is your feature request related to a problem? Please describe.
There is no way to create cost field other then distance metric (kilometers)

Describe the solution you'd like and provide pseudocode examples if you can
Provide flag to CLI called cost_type (default value could be 'kilometers').
Possible values: 'kilometers', 'minutes', 'seconds', 'meters'
'kilometers' and 'meters' are easy to do (first metric has been done already), but 'minutes' and 'seconds' should depend on speed + distance parameter

Additional context
We need to document this functionality and its restrictions properly
Would be cool to have CSV field cost_type as description for weight column also