Obtain edge ids in a rectangle or polygon

Open Source Routing Engine
1

I am using a weather API to change the speed value of streets based on if a certain geographic area is experiencing harsh climate. While I already am getting the values, I need to affect only the edges/streets that are contained in a polygon or bounding box.

Is it possible to obtain all edge ids that happen to be contained in between a bound box delimited by a northeast, southwest coordinate system?

Thanks in advance for any tips.

2

You could use BreadthFirstSearch and explore the graph through this with a bounding box as limit. Use the LocationIndex to get a first entry node. Then you can mark all the nodes or edges.

Another approach would be on runtime: use a custom Weighting class to modify the edge weights and check if the edges are in some of your hazard regions. Here it is important to make the bounding box check very efficient, see into this discussion for some hints and links.

3

I faced the same problem and already implemented a solution. It sure is not as efficient as the mentioned quadtree, but it gets the job done. The implementation was part of my thesis.
You can find the code here https://github.com/lamemate/graphhopper/tree/pstar

The important parts are:


For the mapping of edges to bounding boxes I iterate over all the nodes and save the adjacent edges of those that are in the bounding box.

In my custom weighting class I use the saved information to determine the edge speed.
This and the data structure to save the weather information can be found in

This still needs work to optimize the query speeds. They are very slow when querying a route through Germany. In my test case I used a single federal state and it ran in viable time.

4

Thanks, this is nice!

I’ll publish an import module next week, where one can apply changes to the graph after import (not yet on the fly due to threading issues): for now just access and speed changes. The file format will be simple Geojson and we can hopefully develop a common pipe for these kind of tasks.

Regarding the slowdown on routing: you should avoid expensive calls in the calcWeight method (probably getClosestSourcesForDateAndValueType?)

5

That import module sounds promising! I will be looking forward to that.

You were right about the expensive call of getClosestSourcesForDateAndValueType. I switched the datatype and implemented a simple cache. That improved query times by more than 50%.

There still is an overhead of about 50% compared to a pure fastest weighting, but that is fine for now. I can probably speed it up further by tweaking some of my data types to provide iterations in O(1). Those necessary iterations are probably the main slowdown right now.

1 Like
6

See this new pull request

1 Like
7

Thanks for the responses, and sorry for the delay. Are these changes, inserted via geojson, able to be made while the graphhopper instance is running or can only be made during initialization?

8

This is now possible (with some limitations) to be applied

  • while import
  • while running (permanent; only non-CH)
  • while running (temporary; only non-CH)

See also https://github.com/graphhopper/graphhopper/pull/890