EverySingleStreet

AbstractSimpleMap

Abstract supertype for different map representations.

BoundedAllShortestPaths

Holds pre-computed shortest paths between nodes in a city.

Fields

• g::StaticGraphs.StaticDiGraph{Int32, Int32}: The underlying StaticDiGraph{Int32, Int32} representing the street network.
• dist_mat::SparseArrays.SparseMatrixCSC{Float64, Int32}: A SparseMatrixCSC{Float64, Int32} containing the distance matrix for the nodes in a sparse matrix.
• dist_mat_walkable::SparseArrays.SparseMatrixCSC{Float64, Int32}: Same as dist_mat but edges that are not classified as iswalkable_road have the maximum weight.
• parents::Vector{Dict{Int32, Int32}}: A vector of dictionaries, where each dictionary maps a destination node ID to its parent node on the shortest path from the source node.
• parents_walkable::Vector{Dict{Int32, Int32}}: Same as parents but based on dist_mat_walkable
• distance::Float64: The distance for which all the shortest paths are computed

Candidate

Represents a candidate point potentially lying on a walkable street segment.

Fields

• measured_point::GPSPoint: The GPS point corresponding to the candidate.
• lla::LLA: The LLA object containing the candidate's latitude and longitude.
• way::Way: The Way object representing the street segment the candidate is on
• way_is_reverse::Bool: Indicates if the candidate is positioned along the way in the reverse direction.
• dist::Float64: The distance between the measured GPS point and the candidate point on the way.
• λ::Float64: The distance along the way on which the lla sits basically the interpolation value for the way.

District

Represents a district within the city.

Fields

• name::Symbol: Symbolic name of the district.
• polygons::Vector{HolePolygon}: A vector of HolePolygon objects defining the geographical area of the district.

GPSPoint

Represents a single point with GPS coordinates and associated time.

Fields

• pos::LLA: An LLA object containing latitude and longitude coordinates as well as altitude (not used though)
• time::ZonedDateTime: The time the GPS point was recorded.

GPXFile

Represents a GPX file containing a collection of GPS points.

Fields:

• name::String: The name of the GPX file.
• gps_points::Vector{GPSPoint}: A vector of GPSPoint objects representing the GPS points stored in the file.

HolePolygon

Represents a polygon with holes used for defining districts.

Fields

• outer::Vector{Point2{Float32}}: A vector of Point2{Float32} objects defining the outer boundary of the polygon.
• holes::Vector{Vector{Point2{Float32}}}: A vector of vectors of Point2{Float32} objects defining any holes within the polygon.

Map <: AbstractSimpleMap

Represents a map containing detailed street network information and potentially pre-computed shortest paths.

Fields

• no_graph_map::NoGraphMap: A NoGraphMap instance containing core street network data.
• graph::Union{Missing, OSMGraph}): An optional OSMGraph instance representing the underlying street network graph (may be missing if shortest paths are not pre-computed).
• bounded_shortest_paths::Union{Missing, BoundedAllShortestPaths}: An optional BoundedAllShortestPaths instance containing pre-computed shortest paths within a specific area (may be missing if not pre-computed).

NoGraphMap <: AbstractSimpleMap

Represents a map where the network graph is not explicitly stored.

Fields

• osm_id_to_node_id::Dict{Int, Int}: A dictionary mapping OpenStreetMap node IDs to internal node IDs.
• osm_id_to_edge_id::Dict{Int, Int}: A dictionary mapping OpenStreetMap way (street) IDs to internal edge IDs.
• nodes_to_district_name::Vector{Symbol}: A vector associating each node with the district it belongs to (represented by a symbol).
• nodes::Vector{Node}: A vector of Node objects representing all nodes in the network.
• ways::Vector{Way}: A vector of Way objects representing all ways (streets) in the network.
• walkable_road_nodes::Vector{Bool}: A vector indicating whether each node is on a walkable road.
• osm_node_id_to_edge_ids::Dict{Int, Vector{Int}}: A dictionary mapping OpenStreetMap node IDs to a vector of edge IDs it connects to.
• districts::Vector{District}: A vector of District objects defining districts within the city.

Node

Represents a single node in the street network.

Fields

• id::Int: Unique identifier for the node.
• lat::Float64: Latitude coordinate of the node.
• lon::Float64`: Longitude coordinate of the node.

StreetPath

Represents a path through the street network defined by a sequence of connected street segments.

Fields

• name::String: A name for the path (e.g., user-defined name).
• subpath_id::Int: Unique identifier for the path within a larger context (e.g., route).
• segments::Vector{StreetSegment}: A vector of StreetSegment objects representing the connected street segments forming the path.

struct StreetSegment

A street segment contains of two candidates which have the following property: They are both on the same way and have the same direction.

Fields

• from::Candidate the start Candidate of the segment.
• to::Candidate the start Candidate of the segment.

WalkedParts

Represents a collection of walked way segments for a specific area, potentially with additional information for each way.

Fields:

• names::Dict{String, Vector{Int}}: A dictionary where keys are way names (from Way.name) and values are vectors of integers referencing corresponding WalkedWay objects in the ways field.
• ways::Dict{Int, WalkedWay}: A dictionary where keys are unique identifiers and values are WalkedWay objects representing the walked way segments.

WalkedWay

Represents a way (street) segment that has been walked along, potentially with additional information about the walked parts.

Fields

• way::Way: The Way object representing the underlying street segment.
• parts::Vector{Tuple{Float64, Float64}}: A vector of tuples where each tuple represents a portion of the way that was walked (start and end distance along the way in meters).

Way

Represents a single way (street) in the street network. Most data is coming from openstreetmap.org so for more information about the meaning of highway as an example their documentation should be checked.

Fields

• id::Int: Unique identifier for the way.
• nodes::Vector{Node}: A vector of Node objects defining the way.
• name::String: Name of the way (e.g., street name).
• highway (String): Highway type of the way (e.g., "motorway", "residential").
• foot (String): Access for pedestrians (e.g., "yes", "no").
• access (String): General access information for the way.
• meters::Float64: Total length of the way in meters.

best_route(graph_data::Dict, src::LLA, dst::LLA)

Give a dict with keys "g", "nodes" and "kd_tree" compute the shortest path from src to dst. The start and end point are first mapped to the graph and then a standard AStar is used. Return a vector of LLA including the start and end point.

bounded_all_shortest_paths(map::AbstractSimpleMap, osm_graph, distance)

Call bounded_dijkstra for all nodes and return a BoundedAllShortestPaths object.

bounded_dijkstra(graph, dist_mat, source, distance)

Compute the shortest distance and the parents on how to get there from the specified source up to distance away. Return distances as a dictionary pointing from destination to shortest distance as well as parents point from destination on how to get there.

calculate_streetpath(name, subpath_id, candidates, city_map)

Generate a StreetPath from a list of candidates obtained by map_path.

calculate_walked_parts(streetpaths::Vector{StreetPath}, city_map::AbstractSimpleMap, walked_ways=Dict{Int, WalkedWay}())

Return WalkedParts given the streetpath segments and the possible ways of the city. Can be added to already existing walked_ways. Filters everything which isn't a walkable_road inside city_ways. Calls several function to get a better approximation of what was actually walked like - add extra buffer at start and end of streets to not miss the last few meters of a dead end street as an example extend_walked_parts! - closes circles like roundabouts, parts at ends of some dead end streets

check_if_visited_node(city_map, node::Node, walked_parts)

Return whether the node was visited already.

convert_to_weighted_graph(map::NoGraphMap)

Create a SimpleWeightedGraph from an AbstractSimpleMap. Use the euclidean_distance between two points on a way as the weight.

create_gpx_document(lla_points::Vector{<:LLA})

Use a non-recursive Douglas-Peucker algorithm to simplify a polygon. Used by simplify().

douglas_peucker(pointlist::Array, start_index, last_index, epsilon)

download(place_name, filepath)

Download the road network of the given place and write it as a json file to the given filepath

draw(walked_parts::WalkedParts, gps_points::Vector{GPSPoint}, fname; color="black", gps_opacity=0.4, line_width=7)

Draw the given walked parts on a transparent background as well as the path walked (given the gps_points) as well. One can define the color as well as the opacity for the gps path and the overall line width.

extend_walked_parts_connectors!(walked_parts, city_map)

1. Find all the city ways that are shorter than 2*EXTENDWALKEDWAYUPTO
2. Check if the end of those ways is part of some already walked

extend_walked_parts_cycle!(walked_parts)

Extend the walked parts by finishing a cycle if more than MIN_FILL_CYCLE_PERC perc of a cycle of length maximum MAX_FILL_CYCLE_LENGTH is walked.

extend_walked_parts_simple!(walked_parts)

Extend the walked parts by adding up to EXTEND_WALKED_WAY_UP_TO to the start and end of a walked way. As well as to fill gaps in between parts.

filter_candidates!(candidates)

Filter out candidates which are further away than closer_dist if there is at least candidate which is closer than closer_dist.

find_in_between_candidates(city_map::AbstractSimpleMap, way_tree::KDTree, id_to_way_id, p1::GPSPoint, p2::GPSPoint, origin_lla::LLA, radius)

Return candidates that are as close as possible to p2 on the line from p1 to p2. This should be called when there are no candidates for p2 but there are for p1. In that case we want to find candidates for the last point that we still have candidates for.

get_candidate_on_way(city_map, p, way::Way, trans, rev_trans; rev=false)

Get the best candidate of point p on the given way. trans and rev_trans are transformations mapping from LLA to x,y and back. rev can be set to true to reverse the direction of way.

get_candidate_probability(candidate::Candidate)

Return the emission probability of the given candidate and the standard deviation of the gps error.

get_candidates(map, path)

Get a list of Candidate for each gps point in path given the underlying city_map

get_candidates(city_map::AbstractSimpleMap, way_tree::KDTree, id_to_way_id, p::GPSPoint, origin_lla::LLA, radius)

Get canddiates for a single point given already a kdtree which can map the point to possible candidate ways and so on. This function is used by find_in_between_candidates.

get_candidates_from_idx(vec_candidates, candidate_idxs)

Return candidates from an nested vector of candiates like [[c1,c2],[c3]] and candiate_idxs which are 1d like [1,3] would return [c1, c3].

get_dist_mat_walkable(map, osm_graph, dist_mat::SparseMatrixCSC{Tv, Ti}) where {Tv, Ti}

Set the distance for non walkable road ids to the highest value such that they will not be used.

get_districts(geojson_fpath)

Parse the districts in the given file which needs to have :geometry and :Stadtteil as properties. Return a vector of District

get_first_way_segment(sp, city_map::Map)

Return a way that includes the longest first part of the given shortest path as well as the remaining shortest path which isn't part of this way. The return format consists of:

• A named tuple describing the best way for the first segment: (way::Way, rev::Bool, from::Int, to::Int)
• The remaining shortest path nodes

get_interpolation_point(a, b, t::Float64)

Get the value of a+t*(b-a)

get_interpolation_val(p::Point2, a::Point2, b::Point2)

Get an interpolation value of point p between a line segment from a to b where a+t*(b-a) describes the point closes to p. Return p which is between 0 and 1.

get_kd_tree_from_points(points, origin_lla)

Return a KDTree given gps points or nodes and a origin_lla to as the points are transformed using ENUfromLLA.

get_lla(p, trans)

Get a LLA formatted position from a point and a Geodesy transformation.

get_matching_candidates(city_map, way_ids, p, origin_lla)

Get matching candidates for a given point p and a list of possible way ids. Only return candidates which have a maximum_dist (in m) to the way.

get_next_node_id(candidate::Candidate)

Get the next node id given a candidate. This depends on way_is_reverse of the candidate. Can be used to create a StreetSegment.

get_prev_node_id(candidate::Candidate)

Get the previous node id given a candidate. This depends on way_is_reverse of the candidate. Can be used to create a StreetSegment.

get_segments(city_map, current_candidate, next_candidate, sp)

Given two candidates which can't be directly connected and a list of ids which form the shortest path between those candidates this function returns a list of StreetSegment which connect the two candidates.

get_shortest_path(bounded_shortest_paths::BoundedAllShortestPaths, from, to; only_walkable_road=false)

Return the same output as a_star(g, from, to, dist_mat) but use the cache from BoundedAllShortestPaths

get_shortest_path(city_map::Map, sp_from_id, sp_to_id; only_walkable_road=false)

Return the shortest path from from to to. Has the same output as shortest_path from the LightOSM package but uses the BoundedAllShortestPaths cache when it exists.

get_transformed_points(points, origin_lla::LLA)

Transform a list of gps_points or nodes to a vector of Vector{Point2{Float64}}

get_way_kdtree(city_map)

Create a KDTree for all ways in the given city map. Return

1. a mapping from id to the way id
2. the kd tree
3. The radius for a reasonable in range search (51% of the longest line between two nodes)

getxy_from_lat_lon(lat, lon, trans)

Return x, y position coordinates from lat and lon given a Geodesy trensformation.

intersection(range1::Tuple{T, T}, range2::Tuple{T, T}) where T

Return the intersection of the two ranges as a Tuple{T, T} or nothing if they don't intersect.

is_walkable_road_edge(map::Map, from, to)

Return whether the edge from -> to is on a walkable road.

isfullywalked(walked_parts, way::Way)

Return whether the way is already completely walked.

map_nodes_to_district(nodes::Vector{Node}, geojson_fpath)

Return a vector of district names (as Symbol) that points each Node to its respective district

map_path(city_map, gpxfile)

Map a path of gps points to the best matching candidates for the path.

1. Filter out points on the path which are closer together than 25m
2. Compute candidates for each point in the remaining path
3. Compute emission probabilties
4. Compute transition_probabilities
5. Use the Viterbi algorithm to compute the most likely path of the candidates

Return a list of lists of candidates as a path might not continously have candidates. Then it's split up into several parts.

merge_ranges(ranges::Vector{Tuple{T, T}}) where T

Merge the given ranges together and return a new vector of merged ranges which are also sorted.

midpoint(p1::GPSPoint, p2::GPSPoint)

Calculates the midpoint between two GPS points.

This function takes two GPSPoint objects as input, each containing a position represented by LLA (Latitude, Longitude, Altitude) coordinates and a timestamp represented by ZonedDateTime. It calculates the midpoint in ECEF (Earth-Centered, Earth-Fixed) coordinates for accuracy, then converts the result back to LLA. The time of the midpoint is also interpolated linearly.

Arguments

• p1::GPSPoint: The first GPS point.
• p2::GPSPoint: The second GPS point.

Returns

A GPSPoint object representing the midpoint between p1 and p2.

node_on_way_to_candidate(idx::Int, way::Way; rev=false)
node_on_way_to_candidate(node::Node, way::Way; rev=false)

Given either the idx of a node on a way like way.nodes[idx] if not reversed or the node itself return the matching candidate by computing λ the time of the candidate is set to now in UTC.

parse_map(fpath)

Return a Map object from the given json file path that was created using the download function.

point_linesegment_distance(p::Point2, a::Point2, b::Point2)

Get the smallest distance between point p and the line segment from a to b.

pointlinedistance(p::Point2, a::Point2, b::Point2)

Find the distance between a point p and a line between two points a and b.

points2geojson(vec_candidates::Vector{Vector{Candidate}}, geojson_path)
points2geojson(points::Vector{GPSPoint}, geojson_path)
points2geojson(points::Vector{<:LLA}, geojson_path)

Debug functions to visualize candidates or simple LLA points using tools like: geojson.io/

shortest_candidate_path(from::Candidate, to::Candidate, city_map; only_walkable_road=false)

Return the shortest path as node ids from one candidate to another given a city map.

shortest_path_distance(from::Candidate, to::Candidate, city_map)

Return the shortest path distance based on equation (9) in the fmm paper

Simplify a polygon:

simplify(pointlist::Array, detail=0.1)

detail is the maximum approximation error of simplified polygon.

transition_probability(from::Candidate, to::Candidate, city_map)

Return the transitionprobability based on equation 10 in the [fmm paper](https://www.tandfonline.com/doi/pdf/10.1080/13658816.2017.1400548?casatoken=RrxNeRXfRfkAAAAA:2IA6z4Pu-tKEcSaK44AUgQxDc-XUCBs8CSZI1qGNbUj6CpUMyA8suDUpnZ1WO3lHEUFuk1lk3s4wJtM)

update_district_walked!(district_kms::AbstractDict{Symbol, Float64}, city_map::AbstractSimpleMap, walkedway::WalkedWay)

Update the total walked distance of each district after a WalkedWay is added to the map.

Arguments

• district_kms::AbstractDict{Symbol, Float64}: A dictionary mapping district names (as Symbol) to their total walked distances in kilometers.
• city_map::AbstractSimpleMap: The city map object that stores nodes and edges.
• walkedway::WalkedWay: The walked way object added to the map.

update_weights!(g::SimpleWeightedGraph, map::AbstractSimpleMap, walked_parts::WalkedParts; mul_non_walkable_road=get_preference("MUL_NON_WALKABLE_ROAD"), mul_walked_road = get_preference("MUL_WALKED_ROAD"))

Update the weights of the edges such that walked parts are "longer" in a shortest path calculation as well as ways that are not classified as iswalkable_road.

uses_any_non_walkable_road(map::Map, sp::Vector{Int})

Return whether any of the edges in the shortest path sp are along a non walkable road.