Use std::multimap for admin and timezone polygon results #3427
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
std::unordered_multimap. This preserves the order so that polygons that are the result of state queries are tested first in GetMultiPolyId. With unordered_multipmap, the order is indeterminant and the country polygon can be checked first. This is sub-optimal since they are generally much larger, and often would then need to also check the state polygons as well. Another optimization is to avoid the country query if there is only 1 multipolygon resulting from the state query AND the bounding box is entirely contained within the state polygon. In this case it is safe to set the tile_within_one_admin flag to true which will avoid calling boost geometry covered_by for each node lat,lng within the tile.
… within the single state query result. This change led to tile size changes which may be ok but was not verified. The change without this still leads to substantial performance improvement.
gknisely
previously approved these changes
Nov 26, 2021
kevinkreiser
reviewed
Dec 6, 2021
src/mjolnir/admin.cc
Outdated
| @@ -10,6 +10,8 @@ | |||
| namespace valhalla { | |||
| namespace mjolnir { | |||
|
|
|||
| using polygon_type = boost::geometry::model::polygon<point_type>; | |||
There was a problem hiding this comment.
Thanks. I added that for an early change where I tested if the tile's bounding box was totally inside the 1 state query resulting multi-polygon. If so I was going to just return that one admin and then set tile_withing_one_admin within graphbuilder.cc. This would have removed the need to do point in poly for all other nodes within the tile. Unfortunately this led to a mismatch in tile sizes - so some admin information must have changed. I will leave this for a later (possible) update.
kevinkreiser
approved these changes
Dec 6, 2021
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Admin polygon lookup previously was using std::unordered_multimap for the polygon set returned when querying the admin database. This results in a polygon set that is unordered. It was found that often the country polygon was tested before state polygons in GetMultiPolyId. Since we always want to find a state polygon first (if one exists) this unordered list of results is sub-optimal.
this PR changes to using std::multimap for the resulting polygon list. This can now be checked in the proper order and if a state polygon is found as the first case where the lat,lng is within the admin polygon we can avoid testing the (usually) larger country polygon.
I tested this on North America OSM data. The build stage was done with 8 threads (set concurrency=8 in the config) with the following performance:
master: 2:57:55
branch: 1:32:36
The total size of tiles matches between master and the branch (which I take to mean it is likely the admin results are consistent).
Issue
What issue is this PR targeting? If there is no issue that addresses the problem, please open a corresponding issue and link it here.
Tasklist
Requirements / Relations
Link any requirements here. Other pull requests this PR is based on?