4. Code Documentation

gps2net.air_line_distance(source, target)

Heuristic function for A star algorithm: returns the air line distance from the source to the target.

Parameters

sourcetuple (float, float)

This is the source point. It is a tuple of the form (lng1, lat1) where lng1 is the longitude of the source and lat1 is the latitude of the source.

targettuple (float, float)

This is the source point. It is a tuple of the form (lng2, lat2) where lng2 is the longitude of the target and lat2 is the latitude of the target.

Returns

int

The air line distance between two points (source and target) in meters.

Notes

This function is only called in the following function: getShortestPathAStar()

This function is used as the heuristic function for the A Star algorithm. It calculates the air line distance between two gps points. The result is not 100% correct as the function does not consider the elipsis-like shape of the earth. Instead it just uses an earth radius of 6371000 meters for the calculation.

Examples

>>> myAirLineDist = air_line_distance((-122.115, 37.115), (-122.111, 37.111))
>>> myAirLineDist
568.8872918546489

gps2net.blockPrint()

This method is used to disable print() messages.

gps2net.caculationForOneTXTFile(filepath_shp, new_filename_solution, new_filename_statistics, new_filename_velocities, new_filename_path_length_air_line_length, filepath)

Calculates the most likely solution for one entire txt file based on the underlying street network and saves the solution.

Parameters

filepath_shpstr

The path where the shp file (which contains the street data) is stored.

new_filename_solutionstr

The filename of the new solution.

new_filename_statisticsstr

The filename of the new solution.

new_filename_velocitiesstr

The filename of the velocities histogram.

new_filename_path_length_air_line_lengthstr

The filename of the path_length_air_line_length histogram.

filepathstr

The path where the txt file (which contains the taxi mobility trace) is stored.

gps2net.calculateMostLikelyPointAndPaths(filepath, filepath_shp, minNumberOfLines=2, criticalVelocity=35.0, criticalPathLength=2.0)

Maps GPS positions to the most likely points (based on the underlying street network) and obtains the most likely paths between those points based on the underlying street network.

Parameters

filepathstr

The path where the txt file (which contains the taxi mobility trace) is stored.

filepath_shpstr

The path where the shp file (which contains the street data) is stored.

minNumberOfLinesint, optional

By default 2.

criticalVelocityfloat, optional

The critical velocity is measured in m/s. The critical velocity defines the critical threashhold. If for any found solution the calculated velocity is above this threashhold the algorithm checks if there is another solution which would lead to a lower velocity. By default 35.0 m/s. This value was chosen since cars normally do not drive that fast.

criticalPathLengthfloat, optional

The critical PathLength defines the critical threashhold. If for any found solution the pathLength devided by the airLineLength above this threashhold the algorithm checks if there is another solution which would lead to a shorter path. By default 2.0. This value was chosen since the data with which the algorithm was evaluated showed that values higher than 2.0 are often due due to erroneously mapped points (e.g. if a gps point is close to a crossing and is then mapped to the wrong street). By checking other solutiones when the threashold is exeeded, more likely paths can be found and thereby the accuracy of the algorithm is improved.

Returns

calculatedSolutionlist of dictionaries

Every line of the txt file (which was the input containing the GPS positions) yields a dictionary. This dictionary is appended to the calculatedSolution list. In the end every dictionary will be written to a new txt file as a separate line. This will yield a txt file (similar to the input file but) with additional information. The following values are taken from the input file which contains the GPS trajectories:

• yfloat

  Latitude of the GPS position in decimal degrees.

• xfloat

  Longitude of the GPS position in decimal degrees.

• passenger{0, 1}

  Occupancy shows if a cab has a fare (1 = occupied, 0 = free).

• timestampint

  Time is in UNIX epoch format.

In addition to those four values, every dictionary contains the following parameters which where computed by the algorithm (key : type):

• closest_intersection_xfloat

  Longitude of the mapped position based on underlying network topology.

• closest_intersection_yfloat

  Latitude of the mapped position based on underlying network topology.

• relative_positionfloat

  Distance along the street (where the initial point was mapped to).

• relative_position_normalizedfloat between 0 and 1

  Normalized distance along the street (where the initial point was mapped to).

• intersected_line_oneway{‘B’, ‘F’, ‘T’}

  The ‘oneway’-property of the street (LineString) which the GPS point was mapped to. The ‘oneway’-property indicates if a street is bi-directional (B), or one way heading from the from-node to the to-node (F), or one way heading from the to-node to the from-node (T).

• intersected_linelist of coordinates

  The source_line is a list of GPS coordinates. These coordinates represent the street on which the source point lies.

• linestring_adjustment_visualizationlist with two elements (GPS_position, mapped_point)

  The first element is the GPS position from the input file (x, y). The second element is the point on a street where the initial GPS position was mapped to (closest_intersection_x, closest_intersection_y). This list can be used to visualize the mapping of points.

• path_timeint

  The time from the current to the next GPS position in seconds.

• pathlist of coordinates

  The shortest – most likely – path between two data point based on the streets of the underlying network. –> For more details on how the path is calculated, see getShortestPathAStar()

• path_lengthfloat

  The length of the path in meters. This is an approximation – see distFrom(). –> For more details on how the path is calculated, see getShortestPathAStar()

• air_line_lengthfloat

  The air line length of the current position to the next position (from start to end of ‘path’) in meters. This is an approximation – see distFrom().

• path_length/air_line_lengthfloat

  ‘path_length’ devided by ‘air_line_length’

• velocity_m_sfloat

  The average velocity along the path in m/s (path_length devided by path_time).

• pathIDslist

  The path IDs of all street segments which are traversed on the path. –> For more details on how the path is calculated, see getShortestPathAStar()

• solution_idint

  The id of street where the mapped point lies on.

• solution_indexint

  The index of the chosen solution. All possible solutions are in a list which is sorted by the distance of the solution to the GPS position. 0 means that the point was mapped to the closest intersection with a street. If this solution does not seem to be probable, other (further away) solution where checked and if one of these solutions yielded a better outcome (e.g. shorter paths) than the index of this solution is taken. Consequently, solution_index=3 means that the third-closest solution was chosen.

• path_from_target_to_source{0, 1}

  1 means that the on the ‘oneway’-property was ignored. In this case the path might actually be the path from the target to the source. This is done when the algorithm detects a GPS glipse (the vehicle seems to drive a tiny bit backwards on a oneway street which is not possible) which resulted in a wrong path.

• taxi_did_not_move{0, 1}

  0 means that the taxi did move. 1 means that the taxi did not move.

• second_best_solution_yields_more_found_paths{0, 1}

  1 means that no path existed for initial solution and the second best solution lead to more found paths. In these cases the initial solution was replaced by the second best solution.

• NO_PATH_FOUND{0, 1}

  1 means that no path could be found even though the taxi moved and both source and target point are both no outliers.

• outlier{0, 1}

  1 means that the GPS position is marked as an outlier. This is done when no street could be found in a specified area.

• commentstr

  Comment which summarizes most important assumptions/results/concerns for a specific GPS position.

statisticslist

Statistics for the txt file (containing GPS positions) for which the solution is calculated. The statistics contain the following numbers (all of type int):

• outlierint

  Number of data points which where flagged as outliers.

• taxi_did_not_moveint

  Number of times when a data point’s GPS position was identical to the GPS position of the previous data point.

• no_path_foundint

  Number of times no path was found even though the taxi moved and both source and target point are both no outliers.

• cannot_compute_shortest_path_as_previous_point_is_outlierint

  Number of times the path could not be computed since the previous point was an outlier.

• path_from_target_to_sourceint

  Number of times the ‘oneway’-property was ignored. In this case the path might actually be the path from the target to the source. This is done when the algorithm detects a GPS glipse (the vehicle seems to drive a tiny bit backwards on a oneway street which is not possible) which resulted in a wrong path.

• checked_other_solution_indexint

  Number of times another solution was checked because a path either lead to a velocity of more than 35 m/s or a path length which is more than double the air line length.

• chose_other_solution_indexint

  Number of times the other solution actually lead to a shorter cummulated path (path to previous point plus path to next point) than the initial solution

• solution_already_lies_on_shortest_pathint

  Number of times when velocity was more than 35 m/s or path length was is more than double the air line length BUT the initial solution was already on the shortest path from the previous point to the next point (in this case, the solution is optimal which is why no other solution was checked).

• no_solution_lies_on_shortest_pathint

  Number of times when velocity was more than 35 m/s or path length was is more than double the air line length BUT there was no other solution which lied on the shortest path from the previous point to the next point (in this case, no other solution could b checked).

• other_solution_is_worseint

  Number of times when another solution was checked, but since this new solution was worse than the initial solution it wasn’t taken.

• other_solution_no_path_foundint

  Number of times when another solution was checked, but since there was no valid path for this new solution it wasn’t taken.

• checked_if_path_exists_for_second_best_solution_indexint

  Number of times no path existed for initial solution. In these cases the secont best solution (if it existed) was checked.

• second_best_solution_yields_more_found_pathsint

  Number of times no path existed for initial solution and the second best solution lead to more found paths. In these cases the initial solution was replaced by the second best solution.

Notes

Every txt input file contains the mobility trace of a taxi. The format of each mobility trace file is the following - each line contains [latitude, longitude, occupancy, time], e.g.: [37.75134 -122.39488 0 1213084687], where latitude and longitude are in decimal degrees, occupancy shows if a cab has a fare (1 = occupied, 0 = free) and time is in UNIX epoch format. The output ‘linestring_adjustment_visualization’ can be used to visualize the mapping of points, e.g. by adding it as a layer in GQIS (Layer > Add Layer > Add delimited text layer –> Choose WKT as geometry definition and ‘linestring_adjustment_visualization’ as geometry field).

gps2net.createGraphFromSHPInput(filepath_shp)

Creates a directed graph from a shp file.

Parameters

filepath_shpstr

The path where the shp file (which contains the street data) is stored.

Returns

Directed Graph

The Directed Graph which contains all linesegments of the shapefiles as edges is returned.

Notes

This graph is only initialized once in the beginning of the script. The DiGraph contains all linesegment of the shp file (i.e. streetsegments) as directed edges. The start and end node of each edge are tuples containing the coordinates of the position. The weight of an edge is the air_line_distance from the start to the end of the linesegment. Each edge containes the following attributes:

• idint

  The id of the street (LineString) which the linesegment belongs to according to the shapefile.

• oneway{‘B’, ‘F’, ‘T’}

  The ‘oneway’-property of the street (LineString) which the linesegment belongs to according to the shapefile. The ‘oneway’-property indicates if a street is bi-directional (B), or one way heading from the from-node to the to-node (F), or one way heading from the to-node to the from-node (T).

Depending on the ‘oneway’-property of the street either one or two edges are added to the graph. For ‘B’, two directed edges (from-node –> to-node AND to-node –> from-node) are added. For ‘F’ or ‘T’, only one directed edge is added to the graph.

gps2net.cut(line, distance, point)

Cuts a line in two at a distance from its starting point.

Parameters

lineShapely ‘LineString’ object

[description]

distancefloat

[description]

pointShapely Point object

[description]

Returns

list with LineStrings

Two LineStrings are returned. ‘point’ is the end point of the first LineString and the start point of the second LineString.

Notes

‘line.interpolate(distance)’ should be equal to the parameter ‘point’. However, due to precision errors ‘point’ is used.

gps2net.distFrom(lng1, lat1, lng2, lat2)

Returns the distance between two points in meters.

Parameters

lng1float

This float is the longitude of the source.

lat1float

This float is the latitude of the source.

lng2float

This float is the longitude of the target.

lat2float

This float is the latitude of the target.

Returns

distint

The distance between two points in meters.

Notes

This function calculates the distance between two gps points. The result is not 100% correct as the function does not consider the elipsis-like shape of the earth. Instead it just uses an earth radius of 6371000 meters for the calculation.

A more accurate calculation of the distance can be done in QGIS. For more details, please visit: http://www.qgistutorials.com/en/docs/calculating_line_lengths.html However, this function was used to be able to run the code independently of QGIS.

Examples

>>> myDist = distFrom(-122.115, 37.115, -122.111, 37.111)
>>> myDist
568.8872918546489
>>> distFrom(-122.115, 37.115, -122.111, 37.111)
568.8872918546489

gps2net.enablePrint()

This method restores print() messages.

gps2net.getFilename(path)

Returns the name of a file from a specific path (excluding directories and extension).

Parameters

pathstr

The path of a specific data file.

Returns

str

The name of the file. Namely, the last part of the path (excluding the extgension).

Examples

>>> myPath = 'dir1/dir2/ThisIsMyFilename.txt'
>>> filename = getFilename(myPath)
>>> filename
'ThisIsMyFilename'

gps2net.getPathFromUnmappedGpsPositions(filepath, new_filename)

Creates a new file which includes path, path length, path time, and velocity without considering the underlying street network.

Parameters

filepathstr

The path where the txt file (which contains the taxi mobility trace) is stored.

new_filenamestr

The filename of the new solution.

Notes

This function created a txt file which (in addition to the input values) contains additional parameters which are NOT based on the underlying street network, such as:

• pathLinestring

  Linear path with start=current_position and end=next_position.

• path lengthfloat

  Distance between current and next position in meters.

• path timefloat

  Time between measurement at current and next position in seconds.

• velocityfloat

  Velocity in meters/second.

gps2net.getShortestPathAStar(source, target, source_line, target_line, source_line_oneway, target_line_oneway, filepath_shp, ignore_oneway=False)

Calculates the shortest – most likely – path between two GPS positions (on a street segment) based on the streets of the underlying network.

Parameters

sourcetuple of float

GPS position (float, float). The start node of the path.

targettuple of float

GPS position (float, float). The end node of the path.

source_linelist of coordinates

The source_line is a list of GPS coordinates. These coordinates represent the street on which the source point lies.

target_linelist of coordinates

The target_line is a list of GPS coordinates. These coordinates represent the street on which the target point lies.

source_line_oneway{‘B’, ‘F’, ‘T’}

The ‘oneway’-property of the source_line. The ‘oneway’-property indicates if a street is bi-directional (B), or one way heading from the from-node to the to-node (F), or one way heading from the to-node to the from-node (T).

target_line_oneway{‘B’, ‘F’, ‘T’}

The ‘oneway’-property of the target_line. The ‘oneway’-property indicates if a street is bi-directional (B), or one way heading from the from-node to the to-node (F), or one way heading from the to-node to the from-node (T).

filepath_shpstr

The path where the shp file (which contains the street data) is stored.

ignore_onewaybool, optional

By default False. If True the oneway-property will be ignored when adding edges to the graph. This is set to True when the algorithm detects a GPS glipse (the vehicle seems to drive a tiny bit backwards on a oneway street which is not possible) which resulted in a wrong path. In this case the path might actually be the path from the target to the source.

Returns

pathlist of coordinates

The shortest – most likely – path between two data point based on the streets of the underlying network.

path_lengthfloat

The length of the path in meters. This is an approximation – see distFrom().

path_IDslist

The path IDs of all street segments which are traversed on the path.

gps2net.getTimeDifferences(filepath, timestampPosition)

Get the time differences of taxi mobility traces in a txt file.

Parameters

filepathstr

The path where the txt file (which contains the taxi mobility trace) is stored.

timestampPositionint

The position on which the timestamp is (assuming that each line contains one measured GPS position and that values in each line are seperated by a space).

Returns

list

Time differences in seconds.

Notes

This method assumes that each line contains one measured GPS position and that values in each line are seperated by a space. Further, it assumes that time is in UNIX epoch format. .. rubric:: Examples

>>> myPath = '/Users/Joechi/Google Drive/gps2net/Data/testData/testTaxi.txt'
>>> myTimeDifferences = getTimeDifferences(myPath, 3)
>>> myTimeDifferences
[28, 119]

gps2net.plotAndSaveHistogram(input, minXLabel, maxXLabel, binSize, filename, title, xlabel)

Plots a histogram with a specified max x-value. Values bigger that the max x-value are clipped to the interval edge.

Parameters

inputlist of int or float

Values which should be plottet in a histogram.

minXLabelint or float

The min x-value of the plot.

maxXLabel[type]

The max x-value of the plot.

binSizeint

The size of the plotted bins.

filenamestr

Path and filename of the plot –> this specifies where and under which name the plot should be saved.

titlestr

Title of the plot.

xlabelstr

X axis label of the plot.

Notes

The plot is saved in PNG format.

gps2net.printProgressBar(iteration, total, prefix='', suffix='', decimals=1, length=100, fill='█', printEnd='r')

Call in a loop to create terminal progress bar.

Parameters

iterationint

current iteration

totalInt

total iterations

prefixstr, optional

prefix str, by default ‘’

suffixstr, optional

suffix str, by default ‘’

decimalsint, optional

positive number of decimals in percent complete, by default 1

lengthint, optional

character length of bar, by default 100

fillstr, optional

bar fill character, by default ‘█’

printEndstr, optional

end character (e.g. ‘\r’, ‘\r\n’), by default ‘\r’