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¶

point coordinates (lon, lat)
number of object where point belongs
number of point in object
object is polygon (True) or polyline (False)
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]]

Offroad Routing Engine¶

Installation¶

Usage¶

Processing and pruning data¶

Building visibility graph¶

Pathfinding and visualization¶

Documentation¶

Geometry¶

VisibilityGraph¶

AStar¶

GpxTrack¶

Geometry types¶

Indices and tables¶

Table of Contents

This Page