-
Notifications
You must be signed in to change notification settings - Fork 1
/
RouteBuilder.cs
172 lines (147 loc) · 7.52 KB
/
RouteBuilder.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
using System;
using System.Collections.Generic;
using System.Threading;
using Itinero.Network;
using Itinero.Network.Enumerators.Edges;
using Itinero.Profiles;
using Itinero.Routes.Paths;
namespace Itinero.Routes.Builders
{
/// <summary>
/// Default route builder implementation.
/// </summary>
public class RouteBuilder : IRouteBuilder
{
private static readonly ThreadLocal<RouteBuilder> DefaultLazy = new(() => new RouteBuilder());
/// <summary>
/// Gets the default instance (for the local thread).
/// </summary>
public static RouteBuilder Default => DefaultLazy.Value;
/// <inheritdoc />
public Result<Route> Build(RoutingNetwork routingNetwork, Profile profile, Path path)
{
var edgeEnumerator = routingNetwork.GetEdgeEnumerator();
// SpareEnumerator is used in the branch-calculation. IT offers no guarantees about the state
var spareEnumerator = routingNetwork.GetEdgeEnumerator();
var route = new Route {Profile = profile.Name};
var branches = new List<Route.Branch>();
var seenEdges = 0;
var allEdgeIds = new HashSet<EdgeId>();
foreach (var edge in path.Edges) {
allEdgeIds.Add(edge.edge);
}
foreach (var (edge, direction, offset1, offset2) in path) {
if (route.Shape.Count == 0) {
// This is the first edge of the route - we have to check for branches at the start loction
bool firstEdgeIsFullyContained;
if (direction) {
// Forward: we look to offset1
firstEdgeIsFullyContained = offset1 == 0;
}
else {
firstEdgeIsFullyContained = offset2 == ushort.MaxValue;
}
if (firstEdgeIsFullyContained) {
// We check for branches
edgeEnumerator.MoveToEdge(edge, direction);
AddBranches(edgeEnumerator.From, edgeEnumerator, spareEnumerator, 0, branches, allEdgeIds);
}
}
edgeEnumerator.MoveToEdge(edge, direction);
var attributes = edgeEnumerator.Attributes;
var factor = profile.Factor(attributes);
var distance = edgeEnumerator.EdgeLength() / 100.0;
distance = (offset2 - offset1) / (double) ushort.MaxValue * distance;
route.TotalDistance += distance;
var speed = factor.ForwardSpeedMeterPerSecond;
if (speed <= 0) {
// Something is wrong here
throw new ArgumentException("Speed is zero! Did you pass a wrong profile to the route builder?");
}
var time = distance / speed;
route.TotalTime += time;
// add shape points to route.
using var shapeBetween = edgeEnumerator.GetShapeBetween(offset1, offset2).GetEnumerator();
// skip first coordinate if there are already previous edges.
if (route.Shape.Count > 0 && offset1 == 0) {
shapeBetween.MoveNext();
}
while (shapeBetween.MoveNext()) {
route.Shape.Add(shapeBetween.Current);
}
route.ShapeMeta.Add(new Route.Meta {
Shape = route.Shape.Count - 1,
Attributes = attributes,
AttributesAreForward = direction,
Distance = distance,
Profile = profile.Name,
Time = time
});
// Intermediate points of an edge will never have branches
// So, to calculate branches, it is enough to only look at the last point of the edge
// (and the first point of the first edge - a true edge case)
// (Also note that the first and last edge might not be needed entirely, so that means we possible can ignore those branches)
// What is the end vertex? Add its branches...
if (seenEdges + 1 == path.Count) {
// Hmm, this is the last edge
// We should add the branches of it, but only if the edge is completely contained
bool lastEdgeIsFullyContained;
if (!direction) {
// Backward: we look to offset1
lastEdgeIsFullyContained = offset1 == 0;
}
else {
lastEdgeIsFullyContained = offset2 == ushort.MaxValue;
}
if (lastEdgeIsFullyContained) {
AddBranches(edgeEnumerator.To,
edgeEnumerator, spareEnumerator, route.Shape.Count - 1, branches, allEdgeIds);
}
}
else {
AddBranches(edgeEnumerator.To, edgeEnumerator, spareEnumerator, route.Shape.Count - 1, branches,
allEdgeIds);
}
seenEdges++;
}
route.Branches = branches.ToArray();
return route;
}
/// <summary>
/// Calculate all the branches of 'centralVertexid'
/// </summary>
/// <param name="edgeEnumerator">The edge enumerator, moved to the point of which the branches should be added</param>
/// <param name="spareEnumerator">An extra enumerator to use. Will be moved during the call</param>
/// <param name="centralVertexId">The vertex id of the point under consideration</param>
/// <param name="shapeIndex">The index of the shape of the current vertex</param>
/// <param name="addTo">All the branches are collected into this collection</param>
/// <param name="branchBlacklist">Edges in this list won't be used as branches</param>
private void AddBranches(VertexId centralVertexId, RoutingNetworkEdgeEnumerator edgeEnumerator,
RoutingNetworkEdgeEnumerator spareEnumerator, int shapeIndex,
ICollection<Route.Branch> addTo, HashSet<EdgeId> branchBlacklist)
{
edgeEnumerator.MoveTo(centralVertexId);
while (edgeEnumerator.MoveNext()) {
// Iterates over all edges of the endvertex
if (branchBlacklist.Contains(edgeEnumerator.Id)) {
// We make sure not to pick the current nor the next edge of the path
// This is simple as we have a hashset containing _all_ the edge ids ¯\_(ツ)_/¯
continue;
}
// If the vertex of the crossroads are the same as the from, we would walk forward over the branch if we would take it
var isForward = edgeEnumerator.Forward;
spareEnumerator.MoveToEdge(edgeEnumerator.Id, isForward);
using var shapeEnum = spareEnumerator.GetShapeBetween(includeVertices: false).GetEnumerator();
shapeEnum.MoveNext(); // Init enumerator at first value
shapeEnum.MoveNext();
var branch = new Route.Branch {
Attributes = edgeEnumerator.Attributes,
Shape = shapeIndex,
AttributesAreForward = isForward,
Coordinate = shapeEnum.Current
};
addTo.Add(branch);
}
}
}
}