Offroad Routing Engine

This module is made for downloading, parsing and processing OSM maps, pathfinding and visibility graph building using hierarchical approach, saving and visualizing results. Main goal was to fully optimize geometry algorithms and achieve lowest computational time possible. Low-level data transfer approach has been used and a unique algorithm, created specifically for off-road routing, has been implemented. See algorithm explanation.

Installation

Install from repository:

pip install -e "git+https://github.com/Denikozub/Offroad-routing-engine.git#egg=offroad_routing"

It is recommended to install packages using conda. Pip warning: package requires GeoPandas to be installed, which can be problematic on Windows. This article may help. Dependency warning: you may additionally need to pip install cykhash==1.0.2, rtree and reinstall pyproj with pip.

Usage

You can follow by running the code in IPython notebook.

Processing and pruning data

More information available at Geometry documentation.

There are several ways to obtain OSM data:

• specify .xml (.osm) file to be parsed

• specify .osm.pbf file to be parsed (resources: parts of the world, cities, adjustable area (via mail), adjustable area (online), planet)

• specify bounding box for map data to be dowloaded and parsed

• specify region / city / country query for map data to be downloaded and parsed

import warnings
warnings.filterwarnings("ignore")

from offroad_routing import Geometry

filename = "../maps/user_area.osm.pbf"
bbox = [34, 59, 34.2, 59.1]
geom = Geometry.parse(filename=filename, bbox=bbox)

Geometry data can be explored and visualized using folium, which allows multiple maps to be combined in one layer:

print(geom.stats)
geom.plot()

Geometry can be cut to a bounding box, if needed:

geom.cut_bbox([34.01, 59.01, 34.19, 59.09])

Road network geometry can be simplified and visualized separately. Available options:

• remove small edges using edge contraction

• build minimum spanning tree

• select specific road surface types

geom.select_road_type({'path'}, exclude=True, inplace=True)
geom.minimum_spanning_tree(inplace=True)
geom.simplify_roads(200, inplace=True)
geom.plot('roads')

Polygon geometry can also be simplified and visualized separately, small polygons will be removed:

geom.simplify_polygons(15, inplace=True)
geom.plot('polygons')

Geometry can be saved to file and loaded afterwards using Geometry.load():

geom.save('new_map', '../maps')

Building visibility graph

More information available at VisibilityGraph documentation.

VisibilityGraph uses special geometry representation for maximum speed, so processed geometry needs to be exported:

from offroad_routing import VisibilityGraph

geom = Geometry.load('user_area', '../maps')
vgraph = VisibilityGraph(*geom.export())

Even though vgraph can be used to find routes without pre-building whole graph, visibility graph can be fully built and saved to memory for further use:

vgraph.build(inside_percent=1, multiprocessing=False)
print(vgraph.stats)

Visibility graph can also be visualised using folium:

vgraph.plot()

Pre-built graph can be exported to networkx.MultiGraph and used for further analysis:

import osmnx as ox

G = vgraph.graph
ox.plot_graph(G)

Pathfinding and visualization

More information available at AStar documentation.

If vgraph.build() had been run, pre-built graph is used for pathfinding. Otherwise, incident vertices are computed at runtime, which allows to explore less graph nodes (in combination with A*):

from offroad_routing import VisibilityGraph, AStar

pathfinder = AStar(vgraph)
path = pathfinder.find((34.02, 59.01), (34.12, 59.09), heuristic_multiplier=10)

Path can be viewed in coordinate format:

print(path.path())

More information available at GpxTrack documentation.

However, specialized tools can be used to save and visualize the path. The following code saves the path to a gpx file and generates a link to view it online:

from offroad_routing import GpxTrack

track = GpxTrack(path)
track.write_file("track.gpx")
track.visualize()

You can check the route here.

Path can also be visualized using folium and combibed with other maps:

track.plot()

Documentation

Geometry

Geometry types

class offroad_routing.Geometry

Class for retrieving, storing and processing OSM geometry data.

classmethod parse(*, filename=None, query=None, bbox=None, directory='.')

Parse data to get OSM data. Bounding box will always be used if specified. Either one of parameters should be set. If filename is not None, query is ignored.

Parameters

• filename (str) – .osm.pbf or .xml OSM file

• query (str) – dataset available at Geofabrik or BBBike

• bbox (Optional[Sequence[float]]) – area to be parsed in format (min_lon, min_lat, max_lon, max_lat)

• directory (str) – directory for downloaded maps to be saved

Return type

Geometry

classmethod load(package_name, directory='.')

Load saved geometry from json & geopackage files.

Parameters

• package_name (str) – saved geometry package name

• directory (str) – saved geometry package directory

Return type

Geometry

save(package_name, directory='.')

Save computed geometry to json & geopackage files.

Parameters

• package_name (str) – name for created files to share

• directory (str) – saved geometry package directory

plot(type=None, **kwargs)

Build folium map of all geometry data.

Parameters

• type (Optional[str]) – type of geometry to plot: {‘polygons’, ‘roads’, None}

• kwargs – additional gpd.GeoDataFrame.explore() parameters

Return type

folium.folium.Map

cut_bbox(bbox, *, inplace=False)

Clip geometry strictly inside bounding box. If bbox is None, nothing is changed.

Parameters

• bbox (Optional[Sequence[float]]) – bounding box in format (min_lon, min_lat, max_lon, max_lat)

• inplace (bool) – change initial geometry

Returns

None if inplace else new geometry object

Return type

Optional[Geometry]

minimum_spanning_tree(*, inplace=False)

Build minimum spanning tree of road graph.

Parameters

inplace (bool) – change initial geometry

Returns

None if inplace else new geometry object

Return type

Optional[Geometry]

simplify_roads(threshold, *, inplace=False)

Simplify road network by contracting edges shorted than threshold.

Parameters

• threshold (float) – edge contraction threshold in meters

• inplace (bool) – change initial geometry

Returns

None if inplace else new geometry object

Return type

Optional[Geometry]

select_road_type(types, *, exclude=False, inplace=False)

Select specific OSM road surface types.

Parameters

• types (Set[str]) – set of road surface OSM types to leave

• exclude (bool) – exclude specified surface types

• inplace (bool) – change initial geometry

Returns

None if inplace else new geometry object

Return type

Optional[Geometry]

simplify_polygons(bbox_comp=15, epsilon=None, *, inplace=False)

Simplify polygons by removing small objects (comparing bbox_comp) and running Ramer-Douglas-Peucker (RDP) with epsilon parameter.

Parameters

• bbox_comp (float) – scale polygon comparison parameter (to size of map bbox)

• epsilon (Optional[float]) – RPD simplification parameter. If None, computed automatically

• inplace (bool) – change initial geometry

Returns

None if inplace else new geometry object

Return type

Optional[Geometry]

to_networkx()

Build networkx weighted graph of road network. Weight measured in meters.

Return type

networkx.Graph

export(*, remove_inner=False)

Export geometry data to polygon and linestring records. Duplicate polygons removed.

Parameters

remove_inner (bool) – remove polygons which are inner for other polygons

Returns

polygon and linestring records

Return type

Tuple[TPolygonData, TSegmentData]

VisibilityGraph

Geometry types

class offroad_routing.VisibilityGraph(polygons, linestrings, default_surface='grass')

Class for building and utilizing visibility graphs. Polygons and polylines are used as obstacles on the plane.

__init__(polygons, linestrings, default_surface='grass')

Parameters

• linestrings (TSegmentData) – road segment records

• polygons (TPolygonData) – polygon records

• default_surface (str) – default surface for unfilled areas (choose prevailing surface)

incident_vertices(point_data, inside_percent=1)

Find all incident vertices in visibility graph for given point, computes without building graph.

Parameters

• point_data (PointData) – point on the map to find incident vertices from

• inside_percent (float) – (from 0 to 1) - controls the number of inner polygon edges

Returns

All visible points from given point on the map.

Return type

List[PointData]

build(inside_percent=0.4, multiprocessing=True)

Compute visibility graph for a set of polygons and polylines and store it in memory.

Parameters

• inside_percent (float) – (from 0 to 1) - controls the number of inner polygon edges

• multiprocessing (bool) – speed up computation for dense areas using multiprocessing

plot(**kwargs)

Build folium map of computed graph.

Parameters

kwargs – additional ox.folium.plot_graph_folium() parameters

Return type

folium.folium.Map

AStar

class offroad_routing.AStar(vgraph)

Find off-road routes using A* algorithm and visibility graph.

__init__(vgraph)

Parameters

vgraph (VisibilityGraph) – visibility graph with computed geometry

find(start, goal, heuristic_multiplier=10)

Find route from point start to point goal.

Parameters

• start (TPoint) – start point

• goal (TPoint) – goal point

• heuristic_multiplier (int) – multiplier to weight heuristic (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#scale)

Return type

offroad_routing.pathfinding.path.Path

GpxTrack

class offroad_routing.GpxTrack(path: offroad_routing.pathfinding.path.Path)

Save and visualize off-road path on the map.

__init__(path: offroad_routing.pathfinding.path.Path)

Parameters

path (Path) – initialised and retraced path

visualize()

Generate link to visualize path using https://nakarte.me

write_file(filename)

Save path to gpx file.

Parameters

filename (str) – name of the file to save track into (.gpx)

Geometry types

In order to speed up computation, low-level data transfer approach is used. Data about points, polylines and polygons is transferred using tuples instead of structures.

offroad_routing.geometry.geom_types.TPoint

alias of Tuple[float, float]

offroad_routing.geometry.geom_types.TPolygon

alias of Tuple[TPoint, …]

offroad_routing.geometry.geom_types.TMultiPolygon

alias of Tuple[TPolygon, …]

offroad_routing.geometry.geom_types.TSegment

alias of Tuple[TPoint, TPoint]

offroad_routing.geometry.geom_types.TAngles

alias of Tuple[float, …]

offroad_routing.geometry.geom_types.TPath

alias of List[TPoint]

offroad_routing.geometry.geom_types.TPolygonData

alias of List[offroad_routing.geometry.geom_types.TPolygonRec]

offroad_routing.geometry.geom_types.TSegmentData

alias of List[offroad_routing.geometry.geom_types.TSegmentRec]

offroad_routing.geometry.geom_types.PointData

0. point coordinates (lon, lat)

1. number of object where point belongs

2. number of point in object

3. object is polygon (True) or polyline (False)

4. surface weight

Node of the graph is unambiguously set either by its coordinates or by its position in an object.

alias of Tuple[TPoint, Optional[int], Optional[int], Optional[bool], Optional[int]]

Indices and tables

• Index

• Module Index

• Search Page