-
Notifications
You must be signed in to change notification settings - Fork 68
SGRE configuration
Simple GeoJSON-based routing engine provides a routing engine specially designed for blueprints/graphs defined via GeoJSON input. The routing engine supports different routing profiles (speeds, restrictions), supports height/3D routing (by utilizing Z coordinate). Both line and polygon geometry (both non-convex polygons and polygons with holes) can be used, including mixed line and polygon geometry.
All units should be metric (SI units). Thus all speeds should be given in m/s or degrees/s (for angular speeds). The following GeoJSON coordinates [24.3, 58.6, 10.0] should be interpreted as follows: longitute 24.3 degrees, latitude 58.6 degrees, height 10 meters. The third spatial coordinate is always optional and is 0 by default.
GeoJSON files should consist of features or feature collections. Feature properties are entirely user-defined but can be used to create customized routing profiles based on simple rule system (described below).
Both linestring and polygon geometry is supported, including linestring and polygon multigeometry. Points are ignored as they do not provide any meaningful information for routing. Linestring vertices and polygon edges are automatically connected based on their spatial coordinates. In order to make routing possible between two features, connected coordinates must be exactly equal. The opposite is also true, to disconnect two linestrings with a shared vertex, one instances of the shared vertices should be simply moved around. By offsetting X coordinate by 1.0e-8, for example. The same applies for disconnecting polygons.
Mixing linestrings with polygons is supported and should work in intuitive way. Linestring vertices within polygons are connected automatically to the polygons when routing graph is being built. Polygons within polygons are NOT supported.
Routing configuration can be specified via JSON object that has several optional parameters:
{
"tesselationdistance": 5.0,
"pathstraightening": true,
"zsensitivity": 1000.0,
"min_turnangle": 5.0,
"min_updownangle": 45.0,
"rules": [
{ "speed": 1.0 }
]
}
This example configuration can be used as a starting configuration in most cases. It specifies two parameters relevant to route finder ('tesselationdistance' and 'pathstraightening') and a rule list containing a single rule (rule lists are described in detail below). Here 'tesselationdistance' is an important parameter if polygon-based routing is used (it has no effect for linestring-based routing). It is a tradeoff parameter between runtime performance and result quality. The parameter 'pathstraightening' should be always left on, unless working in debugging mode. It has no effect for linestring-only routing. 'zsensitivity' affects graph matching. Its default values is 1, which means that Z coordinate has equal weight to planar coordinates when matching routing graph. If set to a larger value, then Z coordinate (floor) is given respectively more weight. If set to 0, then Z coordinate is effectively not used when matching underlying graph. 'min_turnangle' is a threshold value (in degrees) for deciding between turn and 'go straight' instructions. 'min_updownangle' is a vertical movement threshold value (in degrees) for deciding between normal movement and 'go up' or 'go down' instructions.
Routing profiles specify routing related attributes like moving speeds, one-way moving restrictions, delays and route endpoint searching methods.
Profiles are configured using rule lists. An example of a single rule in a rule list:
{
"profiles": ["wheelchair"],
"filters": [{ "type": "room", "subtype": "hallway" }, { "type": "corridor" }],
"delay": 0.0,
"speed": 5.0,
"zspeed": 1.0,
"turnspeed": 180
}
This rule applies to 'wheelchair' profile and only to GeoJSON features that have both 'type=room' and 'subtype='hallway' set or 'type=corridor' set in their properties. No delay is applied, speed is 5m/s for horizontal movement and 1m/s for vertical movement. Note that speed and zspeed are additive - if we need to move 5m horizontally and 1m vertically, then the time will be 5/5 + 1/1 = 1 + 1 = 2s. Turnspeed defines extra penalty for required turns and is equal to 180deg/s in this example. Delay is a constant time penalty added for moving from one node to another node. In practice this should be rarely used but could be useful for modelling security checks in airports, for example. If 'profiles' list is not specified, then the rule applies to all routing profiles. Likewise, if 'filters' is not specified, the rule is applied to all features.
For linestring geometry, optional backward speed attributes may also be specified. For example:
{
"speed": 2.0,
"backward_speed": 2.0,
"backward_zspeed": 0.0
}
For backwards movement, the speed is 2m/s horizontally and 0m/s vertically defined by the rule, which means that vertical movement is simply not allowed. Thus speed or zspeed value 0 can be used to make movement unidirectional or even remove a feature from the routing graph. If backward speed is not specified, original speed value is used by default. The default values for parameters are as follows speed = 1.38 (approx 5km/h), zspeed = 0.5, turnSpeed = 180 (degrees/s), delay = 0.
Several rules can be combined using rule lists. The lists are applied in order. For example:
[
{ "filters": [{"type": "room"}], "speed": 2.0, "zspeed": 1.0 },
{ "filters": [{"type": "room", "subtype": "hallway"}], "speed": 3.0 }
]
This example defines two rules. If input data contains a feature with both 'type=room' and 'subtype=hallway', then speed=3.0 and zspeed=1.0 values are used for routing for this feature.
For more complex use cases, two additional rule parameters 'search' and 'link' can be specified. 'search' may be one of the following:
- "none" - this feature will be ignored when matching nearest features to the routing query endpoints
- "vertex" - only the vertices of the feature are used when matching nearest features to the routing query endpoints
- "firstlastvertex" - can be only used with linestrings. only the first and last vertex of the feature are used when matching nearest features to the routing query endpoints.
- "edge" - the edges of the feature are used when matching nearest features to the routing query endpoints. Default for linestrings.
- "surface" - the whole surface of the feature is used when matching nearest features to the routing query endpoints. Default for polygons.
'link' parameter can be used with linegeometry to customize the linking of line vertices to polygons:
- "none" - line vertices will not be connected to intersecting polygons.
- "endpoints" - only line endpoints will be connected to intersecting polygons.
- "all" - all line vertices will be connected to intersecting polygons.
It is possible to parametrize routing rules and set the parameters at runtime. For example:
{
"profiles": ["wheelchair"],
"filters": [{ "type": "room", "subtype": "hallway" }, { "type": "corridor" }],
"delay": "$delay",
"speed": "$speedX"
}
In this example both 'delay' and 'speed' can be set after the rules are parsed and routing graph is constructed, thus making changes in delay and speed values basically instant. SGRE supports setting the following parameters: 'speed', 'zspeed', 'turnspeed', 'delay'. A potentially useful trick that allows disabling rule is to set 'delay' parameter to infinity.
Routing engine uses local planar approximation for the geometry. It is very well suited for indoor routing, as the distances are close and the approximation does not result in noticable errors. The errors get somewhat bigger if geometry is near the poles.
Routing engine accepts longitude coordinates outside of -180..180 range. If geometry crosses -180 or 180 longitude, then this extended range should be used (use 179.9 -> 180.1, instead of 179.9 -> -179.9, for example).
'Turn speed' routing parameter is not taken into account when searching for the optimal route. It is used in the final routing instructions for calculating routing time. 'Delay' routing parameter is supported only for linestring geometry.
For polygon areas, routing engine does not guarantee optimal results. Due to postprocessing, most routes look at least reasonable or even optimal. The engine has 'tesselation distance' parameter that can be tweaked to generate better results but at the expense of performance. Though the error can be up to min(tesselation_distance, max_polygon_edge_length) * num_edges, in practice it seems to be approximately min(tesselation_distance, max_polygon_edge_length). So setting 'tesselation distance' parameter to 5 seems to be good compromise for indoor routing.