Intersection Algorithm - HY-OHTUPROJ-OSRM/osrm-project GitHub Wiki
The Polygonal-Intersections repository contains an algorithm to calculate new speeds for road segments given a set of roadblocks and speed zones. The affected segments and their new speed values can then be given to OSRM as dynamic traffic data. The algorithm comes with a GUI application for testing as well as a separate CLI that's to be called from routing-api.
Build instructions
CLI
-
If you're on Windows, install a build of GCC such as MinGW-w64 and make sure the folder containing
g++is in Path. -
Run
make cli
The program will be placed bin/cli.
GUI
⚠️ Note: Building the GUI application using the provided Makefile is currently only supported on Windows.
The GUI can be built on Windows as follows:
-
Install a build of GCC for Windows such as MinGW-w64.
-
Run
make gui_dirs -
Place the C and C++ standard library binaries from the compiler in the
bin/guifolder that was created. -
The GUI uses the SFML library. Unless the compiler you use is listed on the library's download page, you will need to build it from source.
-
Place the DLLs from SFML in
bin/guiand add theincludefolder from the SFML zip file to Path. -
Make sure you have the folder containing
g++.exein Path. -
Run
make gui. (If you don't want to do the previous step, you can also runmake gui CXX=[path to g++]/g++.)
The program will be placed in bin/gui.
Testing
Components of the algorithm can be tested with unit tests using the following commands:
-
make tests: Builds the unit tests. -
make run_tests: Builds and runs the unit tests.
Coverage
A test coverage report can be generated using either LCOV or Gcovr. Generating the report with Gcovr will include branch coverage information, but since not all branches in the code are actually relevant, the simpler line and function coverage report generated by LCOV is recommended instead. The following commands are supported:
-
make coverage.info: Builds and runs the unit tests and generates a machine-readable coverage report using LCOV. -
make cov: Builds and runs the unit tests and generates a coverage report in HTML using LCOV. The report can be viewed by openinghtmlcov/index.htmlin a browser. -
make gcovr: Builds and runs the unit tests and generates a coverage report using Gcovr. The report can be viewed by openinggcovr/coverage.htmlin a browser.
The coverage report from the latest commit in the repository is on Codecov.
CLI Usage
The program Polygonal-Intersections-CLI takes no command line arguments. Instead, the roadblocks, speed zones and line segments are sent via standard input in the following format.
Input
The header of the input contains the number of polygons and paths.
| Offset | Size | Description |
|---|---|---|
| 0x00 | 8 | Number of roadblock polygons |
| 0x08 | 8 | Number of roadblock polygonal chains |
| 0x10 | 8 | Number of speed zones |
| 0x18 | 8 | Number of paths |
| 0x20 | List of roadblock polygons | |
| List of roadblock polygonal chains | ||
| List of speed zones | ||
| List of paths |
Each roadblock (both polygons and polygonal chains) on the corresponding lists are given in the following format:
| Offset | Size | Description |
|---|---|---|
| 0x00 | 8 | Number of vertices |
| 0x08 | Vertex list |
Each vertex on the vertex list is represented as a pair of 32-bit signed integers. The list of polygonal chain roadblocks immediately follows the list of polygon roadblocks without any padding in between. The latter is immediately followed by the list of speed zones. Each speed zone on that list is in given in the following format:
| Offset | Size | Description |
|---|---|---|
| 0x00 | 1 | Type |
| 0x01 | 8 | Effect value |
| 0x09 | 8 | Number of vertices |
| 0x11 | Vertex list |
The effect value is a 64-bit floating point number. The following speed zone types are supported:
| Speed zone type | Name | Description |
|---|---|---|
| 0 | Offset | The effect value is added to the speed |
| 1 | Factor | The speed is multiplied by the effect value |
| 2 | Cap | If the speed is higher than the effect value, it gets replaced with it |
| 3-255 | Constant | The speed is replaced with the effect value |
The path list immediately follows the list of speed zones. Each path on it is given in the following format:
| Offset | Size | Description |
|---|---|---|
| 0x00 | 2 | Original speed |
| 0x02 | 8 | Number of vertices |
| 0x0A | Node list |
The original speed of the path is given as an unsigned 16-bit integer. Each node on the node list is given in the following format:
| Offset | Size | Description |
|---|---|---|
| 0x00 | 8 | node ID |
| 0x08 | 4 | x-coordinate |
| 0x0C | 4 | y-coordinate |
The node ID is an unsigned 64-bit integer. It's used to identify nodes in the output. Like before, coordinates are 32-bit signed integers.
Output
The program sends its results to standard output. The output represents all of the given line segments whose speeds are affected by the roadblocks and speed zones. Each of those segments is only identified by the node IDs of its endpoints, not by their coordinates. Each affected segment is sent in the following format:
| Offset | Size | Description |
|---|---|---|
| 0x00 | 8 | start node ID |
| 0x08 | 8 | end node ID |
| 0x10 | 8 | new speed |
Once the program finishes successfully, all of the affected segments will have been sent. The node IDs in each segment are in the same order that they were in the input. The new speed is given as a 64-bit floating point number.
Algorithm
The main algorithm is contained in the function TrafficZones::for_each_intersecting_segment. It's called for a single path at once, and it receives its nodes by calling the read_node parameter. For each segment in the path whose speed is affected by the roadblocks and speed zones, it calls the write_segment parameter. This way the segments are written to standard output as soon as they're calculated, and that calculation begins as soon as the segments are read.
The algorithm first checks if the starting point of the path is inside a roadblock polygon sets the in_roadblock variable accordingly. Then it iterates all segments of the chain. On each iteration, it first checks if the segment is blocked by a roadblock, before calculating the more expensive average speed given by the speed zones. It uses the in_roadblock variable to keep track of whether the current node is inside a roadblock polygon or not.
Checking if a point is inside a polygon
The algorithm to determine if a given point is inside a polygon is in the function Polygon::contains. It casts a ray vertically downwards from the point and counts the number of times it crosses from one side of the polygon to the other modulo 2. If that number is even, the point is considered the be outside of the polygon, and otherwise it's considered to be inside. Some special cases are handled to ensure that points on the edge of the polygon are considered inside, and vertical edges overlapping with the ray are handled properly. There is a short description of this algorithm on Wikipedia.
The directional limit of the point-in-polygon function
The function Polygon::limit_of_contains computes the directional limit of Polygon::contains along a given vector. In other words, it returns true if every neighborhood of the point contains another point in the given direction, and false otherwise. It's implement similarly to Polygon::contains, but the direction of the ray is the direction of the given vector and the edge cases are different.
Checking if two line segments intersect
The algorithm to determine if two line segments intersect is in the function find_intersection. It interprets the line segments as images of linear interpolation functions $l_{1}, l_{2}: [0, 1] \cap \mathbb{Q} \rightarrow \mathbb{Q}^{2}$. First the algorithm checks if the line segments are parallel by calculating the determinant of the $2 \times 2$ matrix whose columns are the direction vectors of the segments (this operation is also known as a "wedge product").
In the case where the line segments aren't parallel, it calculates the parameters $t_{1}$ and $t_{2}$ for the corresponding extended functions $\mathbb{Q} \rightarrow \mathbb{Q}^{2}$ at the intersection point and then checks if both parameters are within $[0, 1]$. If they are, the line segments intersect and the algorithm returns the parameter $t_{1}$ of the intersection point for the first line segment, i.e. the unique value for $t_{1}$ with which $l_{1}(t_{1})$ is on the second line segment. Otherwise they don't intersect, and the function returns std::nullopt.
If the line segments are parallel, the algorithm checks if they are also collinear. If they are collinear and overlap with each other, the algorithm returns an interval of all possible values for $t_{1}$ with which $l_{1}(t_{1})$ is on the second line segment. Otherwise they don't intersect and std::nullopt is returned.
Finding the parts of a line segment that are inside different speed zones
The IntervalMap::insert_at_intersections function finds all intersections between a line segment and a polygon as parameters to the line segment and inserts them to the IntervalMap data structure which maps intervals of rational numbers to speed zones.
Calculating the new average speed for a line segment based on speed zones
The LineSegment::new_average_speed function calculates the new average speed for a line segment given its original speed and a collection of speed zones. It calls IntervalMap::insert_at_intersections repeatedly to insert the intersections with each speed zone to the same interval map. The intersections with the zone that would give the lowest speed to the segment are inserted last. This makes it so that when two or more speed zones overlap, the lowest speed given by them is used at each point.
Time complexity
Excluding logarithmic factors, the time complexity of the current algorithm is $O(nm)$ where $n$ is the total number of nodes in the paths and $m$ is the total number of vertices in the roadblocks and speed zones. However, it might be possible to improve this in the future.
Existing algorithms to look into
The following algorithms calculate all $k$ intersections of $n$ line segments:
- Bentley–Ottmann: $O((n+k)\log n)$
- Chazelle: $O(n \log n+k)$
- Balaban: $O(n \log n+k)$
There is also the Shamos–Hoey algorithm that determines if at least one intersection exists in $O(n log n)$ time. Perhaps a modified version of one of these algorithms could be used to improve the time complexity of the current algorithm?
Minimum and maximum values for coordinates
Each coordinate of a vertex needs to be within $[1-2^{30}, 2^{30}-1]$. Otherwise integer overflow may occur, and the results may not be correct. Currently the coordinates aren't validated, but this could change in the future. Another option would be receiving all coordinates in floating point and then scaling and rounding them so that the one with the largest absolute value maps to $\pm(2^{30}-1)$.
Self-intersecting polygons
If a polygon intersects itself, the notions of "inside" and "outside" become ambiguous. The current algorithm uses the even-odd rule to decide this. It would also be possible to require all polygons to be simple and validate them before running the algorithm.