1 #include "engine/guidance/post_processing.hpp"
2 #include "guidance/constants.hpp"
3 #include "guidance/turn_instruction.hpp"
4
5 #include "engine/guidance/assemble_steps.hpp"
6 #include "engine/guidance/lane_processing.hpp"
7
8 #include "engine/guidance/collapsing_utility.hpp"
9 #include "util/bearing.hpp"
10 #include "util/group_by.hpp"
11 #include "util/guidance/name_announcements.hpp"
12 #include "util/guidance/turn_lanes.hpp"
13
14 #include <boost/assert.hpp>
15 #include <boost/numeric/conversion/cast.hpp>
16 #include <boost/range/iterator_range.hpp>
17
18 #include "engine/guidance/collapsing_utility.hpp"
19
20 #include <algorithm>
21 #include <cmath>
22 #include <cstddef>
23 #include <limits>
24 #include <utility>
25
26 namespace osrm
27 {
28 namespace engine
29 {
30 namespace guidance
31 {
32 using namespace osrm::guidance;
33
34 using RouteStepIterator = std::vector<osrm::engine::guidance::RouteStep>::iterator;
35
36 namespace
37 {
38
39 // Ensure that after we are done with the roundabout, only the roundabout instructions themselves
40 // remain
compressRange(const RouteStepIterator begin,const RouteStepIterator end)41 void compressRange(const RouteStepIterator begin, const RouteStepIterator end)
42 {
43 if (begin == end)
44 return;
45
46 for (auto itr = begin + 1; itr != end; ++itr)
47 {
48 // ensure not to invalidate the final arrive
49 if (!hasWaypointType(*itr))
50 {
51 begin->ElongateBy(*itr);
52 itr->Invalidate();
53 }
54 }
55 }
56
57 // this function handles a single roundabout between enter (which might be missing) to exit (which
58 // might be missing as well)
processRoundaboutExits(const RouteStepIterator begin,const RouteStepIterator end)59 void processRoundaboutExits(const RouteStepIterator begin, const RouteStepIterator end)
60 {
61 auto const last = end - 1;
62 // If we do not exit the roundabout, there is no exit to report. All good here
63 if (!leavesRoundabout(last->maneuver.instruction))
64 {
65 // first we do some clean-up
66 if (begin->maneuver.instruction.type == TurnType::EnterRotary ||
67 begin->maneuver.instruction.type == TurnType::EnterRotaryAtExit)
68 {
69 begin->rotary_name = begin->name;
70 begin->rotary_pronunciation = begin->pronunciation;
71 }
72 // roundabout turns don't make sense without an exit, update the type
73 else if (entersRoundabout(begin->maneuver.instruction) &&
74 (begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersection ||
75 begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersectionAtExit))
76 {
77 begin->maneuver.instruction.type = TurnType::EnterRoundabout;
78 }
79
80 // We are doing a roundtrip on the roundabout, Nothing to do here but to remove the
81 // instructions
82 compressRange(begin, end);
83 return;
84 }
85
86 const auto passes_exit_or_leaves_roundabout = [](auto const &step) {
87 return staysOnRoundabout(step.maneuver.instruction) ||
88 leavesRoundabout(step.maneuver.instruction);
89 };
90
91 // exit count
92 const auto exit = std::count_if(begin, end, passes_exit_or_leaves_roundabout);
93
94 // removes all intermediate instructions, assigns names and exit numbers
95 BOOST_ASSERT(leavesRoundabout(last->maneuver.instruction));
96 BOOST_ASSERT(std::distance(begin, end) >= 1);
97 last->maneuver.exit = exit;
98
99 // when we actually have an enter instruction, we can store all the information on it that we
100 // need, otherwise we only provide the exit instruciton. In case of re-routing on the
101 // roundabout, this might result in strange behaviour, but this way we are more resiliant and we
102 // do provide exit after all
103 if (entersRoundabout(begin->maneuver.instruction))
104 {
105 begin->maneuver.exit = exit;
106 // special handling for rotaries: remember the name (legacy feature, due to
107 // adapt-step-signage)
108 if (begin->maneuver.instruction.type == TurnType::EnterRotary ||
109 begin->maneuver.instruction.type == TurnType::EnterRotaryAtExit)
110 {
111 begin->rotary_name = begin->name;
112 begin->rotary_pronunciation = begin->pronunciation;
113 }
114 // compute the total direction modifier for roundabout turns
115 else if (begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersection ||
116 begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersectionAtExit)
117 {
118 const auto entry_intersection = begin->intersections.front();
119
120 const auto exit_intersection = last->intersections.front();
121 const auto exit_bearing = exit_intersection.bearings[exit_intersection.out];
122
123 BOOST_ASSERT(!begin->intersections.empty());
124 const double angle = util::bearing::angleBetween(
125 util::bearing::reverse(entry_intersection.bearings[entry_intersection.in]),
126 exit_bearing);
127
128 begin->maneuver.instruction.direction_modifier = getTurnDirection(angle);
129 }
130 begin->AdaptStepSignage(*last);
131 }
132
133 // in case of a roundabout turn, we do not emit an exit as long as the mode remains the same
134 if ((begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersection ||
135 begin->maneuver.instruction.type == TurnType::EnterRoundaboutIntersectionAtExit) &&
136 begin->mode == last->mode)
137 {
138 compressRange(begin, end);
139 }
140 else
141 {
142 // do not remove last (the exit instruction)
143 compressRange(begin, last);
144 }
145 }
146
147 // roundabout groups are a sequence of roundabout instructions. This can contain enter/exit
148 // instructions in between
processRoundaboutGroups(const std::pair<RouteStepIterator,RouteStepIterator> & range)149 void processRoundaboutGroups(const std::pair<RouteStepIterator, RouteStepIterator> &range)
150 {
151 const auto leaves_roundabout = [](auto const &step) {
152 return leavesRoundabout(step.maneuver.instruction);
153 };
154
155 auto itr = range.first;
156 while (itr != range.second)
157 {
158 auto exit = std::find_if(itr, range.second, leaves_roundabout);
159 if (exit == range.second)
160 {
161 processRoundaboutExits(itr, exit);
162 itr = exit;
163 }
164 else
165 {
166 processRoundaboutExits(itr, exit + 1);
167 itr = exit + 1;
168 }
169 }
170 }
171
172 } // namespace
173
174 // Every Step Maneuver consists of the information until the turn.
175 // This list contains a set of instructions, called silent, which should
176 // not be part of the final output.
177 // They are required for maintenance purposes. We can calculate the number
178 // of exits to pass in a roundabout and the number of intersections
179 // that we come across.
handleRoundabouts(std::vector<RouteStep> steps)180 std::vector<RouteStep> handleRoundabouts(std::vector<RouteStep> steps)
181 {
182 // check if a step has roundabout type
183 const auto has_roundabout_type = [](auto const &step) {
184 return hasRoundaboutType(step.maneuver.instruction);
185 };
186 const auto first_roundabout_type =
187 std::find_if(steps.begin(), steps.end(), has_roundabout_type);
188
189 // no roundabout to process?
190 if (first_roundabout_type == steps.end())
191 return steps;
192
193 // unless the first instruction enters the roundabout, we are currently on a roundabout. This is
194 // a special case that happens if the route starts on a roundabout. It is a border case, but
195 // could happen during re-routing. In the case of re-routing, exit counting might be confusing,
196 // but it is the best we can do
197 bool currently_on_roundabout = !entersRoundabout(first_roundabout_type->maneuver.instruction);
198
199 // this group by paradigm does might contain intermediate roundabout instructions, when they are
200 // directly connected. Otherwise it will be a sequence containing everything from enter to exit.
201 // If we already start on the roundabout, the first valid place will be steps.begin().
202 const auto is_on_roundabout = [¤tly_on_roundabout](const auto &step) {
203 if (currently_on_roundabout)
204 {
205 if (leavesRoundabout(step.maneuver.instruction))
206 currently_on_roundabout = false;
207
208 return true;
209 }
210 else
211 {
212 currently_on_roundabout = entersRoundabout(step.maneuver.instruction);
213 auto result = currently_on_roundabout;
214 // cases that immediately exit the roundabout
215 if (currently_on_roundabout)
216 currently_on_roundabout = !leavesRoundabout(step.maneuver.instruction);
217 return result;
218 }
219 };
220
221 // for each range of instructions between begin/end of a roundabout assign
222 util::group_by(steps.begin(), steps.end(), is_on_roundabout, processRoundaboutGroups);
223
224 BOOST_ASSERT(steps.front().intersections.size() >= 1);
225 BOOST_ASSERT(steps.front().intersections.front().bearings.size() == 1);
226 BOOST_ASSERT(steps.front().intersections.front().entry.size() == 1);
227 BOOST_ASSERT(steps.front().maneuver.waypoint_type == WaypointType::Depart);
228
229 BOOST_ASSERT(steps.back().intersections.size() == 1);
230 BOOST_ASSERT(steps.back().intersections.front().bearings.size() == 1);
231 BOOST_ASSERT(steps.back().intersections.front().entry.size() == 1);
232 BOOST_ASSERT(steps.back().maneuver.waypoint_type == WaypointType::Arrive);
233
234 return removeNoTurnInstructions(std::move(steps));
235 }
236
237 // Doing this step in post-processing provides a few challenges we cannot overcome.
238 // The removal of an initial step imposes some copy overhead in the steps, moving all later
239 // steps to the front. In addition, we cannot reduce the travel time that is accumulated at a
240 // different location.
241 // As a direct implication, we have to keep the time of the initial/final turns (which adds a
242 // few seconds of inaccuracy at both ends. This is acceptable, however, since the turn should
243 // usually not be as relevant.
trimShortSegments(std::vector<RouteStep> & steps,LegGeometry & geometry)244 void trimShortSegments(std::vector<RouteStep> &steps, LegGeometry &geometry)
245 {
246 if (steps.size() < 2 || geometry.locations.size() <= 2)
247 return;
248
249 // if phantom node is located at the connection of two segments, either one can be selected
250 // as turn
251 //
252 // a --- b
253 // |
254 // c
255 //
256 // If a route from b to c is requested, both a--b and b--c could be selected as start
257 // segment.
258 // In case of a--b, we end up with an unwanted turn saying turn-right onto b-c.
259 // These cases start off with an initial segment which is of zero length.
260 // We have to be careful though, since routing that starts in a roundabout has a valid.
261 // To catch these cases correctly, we have to perform trimming prior to the post-processing
262
263 BOOST_ASSERT(geometry.locations.size() >= steps.size());
264 // Look for distances under 1m
265 const bool zero_length_step = steps.front().distance <= 1 && steps.size() > 2;
266 const bool duplicated_coordinate = util::coordinate_calculation::haversineDistance(
267 geometry.locations[0], geometry.locations[1]) <= 1;
268 if (zero_length_step || duplicated_coordinate)
269 {
270
271 // remove the initial distance value
272 geometry.segment_distances.erase(geometry.segment_distances.begin());
273
274 const auto offset = zero_length_step ? geometry.segment_offsets[1] : 1;
275 if (offset > 0)
276 {
277 // fixup the coordinates/annotations/ids
278 geometry.locations.erase(geometry.locations.begin(),
279 geometry.locations.begin() + offset);
280 geometry.annotations.erase(geometry.annotations.begin(),
281 geometry.annotations.begin() + offset);
282 geometry.osm_node_ids.erase(geometry.osm_node_ids.begin(),
283 geometry.osm_node_ids.begin() + offset);
284 }
285
286 auto const first_bearing = steps.front().maneuver.bearing_after;
287 // We have to adjust the first step both for its name and the bearings
288 if (zero_length_step)
289 {
290 // since we are not only checking for epsilon but for a full meter, we can have multiple
291 // coordinates here. Move all offsets to the front and reduce by one. (This is an
292 // inplace forward one and reduce by one)
293 std::transform(geometry.segment_offsets.begin() + 1,
294 geometry.segment_offsets.end(),
295 geometry.segment_offsets.begin(),
296 [offset](const std::size_t val) { return val - offset; });
297
298 geometry.segment_offsets.pop_back();
299 const auto ¤t_depart = steps.front();
300 auto &designated_depart = *(steps.begin() + 1);
301
302 // FIXME this is required to be consistent with the route durations. The initial
303 // turn is not actually part of the route, though
304 designated_depart.duration += current_depart.duration;
305
306 // update initial turn direction/bearings. Due to the duplicated first coordinate,
307 // the initial bearing is invalid
308 designated_depart.maneuver.waypoint_type = WaypointType::Depart;
309 designated_depart.maneuver.bearing_before = 0;
310 designated_depart.maneuver.instruction = TurnInstruction::NO_TURN();
311 // we need to make this conform with the intersection format for the first intersection
312 auto &first_intersection = designated_depart.intersections.front();
313 designated_depart.intersections.front().lanes = util::guidance::LaneTuple();
314 designated_depart.intersections.front().lane_description.clear();
315 first_intersection.bearings = {first_intersection.bearings[first_intersection.out]};
316 first_intersection.entry = {true};
317 first_intersection.in = IntermediateIntersection::NO_INDEX;
318 first_intersection.out = 0;
319
320 // finally remove the initial (now duplicated move)
321 steps.erase(steps.begin());
322 }
323 else
324 {
325 // we need to make this at least 1 because we will substract 1
326 // from all offsets at the end of the loop.
327 steps.front().geometry_begin = 1;
328
329 // reduce all offsets by one (inplace)
330 std::transform(geometry.segment_offsets.begin(),
331 geometry.segment_offsets.end(),
332 geometry.segment_offsets.begin(),
333 [](const std::size_t val) { return val - 1; });
334 }
335
336 // and update the leg geometry indices for the removed entry
337 std::for_each(steps.begin(), steps.end(), [offset](RouteStep &step) {
338 step.geometry_begin -= offset;
339 step.geometry_end -= offset;
340 });
341
342 auto &first_step = steps.front();
343 auto bearing = first_bearing;
344 // we changed the geometry, we need to recalculate the bearing
345 if (geometry.locations[first_step.geometry_begin] !=
346 geometry.locations[first_step.geometry_begin + 1])
347 {
348 bearing = std::round(util::coordinate_calculation::bearing(
349 geometry.locations[first_step.geometry_begin],
350 geometry.locations[first_step.geometry_begin + 1]));
351 }
352 first_step.maneuver.bearing_after = bearing;
353 first_step.intersections.front().bearings.front() = bearing;
354 }
355
356 BOOST_ASSERT(steps.front().intersections.size() >= 1);
357 BOOST_ASSERT(steps.front().intersections.front().bearings.size() == 1);
358 BOOST_ASSERT(steps.front().intersections.front().entry.size() == 1);
359 BOOST_ASSERT(steps.front().maneuver.waypoint_type == WaypointType::Depart);
360
361 BOOST_ASSERT(steps.back().intersections.size() == 1);
362 BOOST_ASSERT(steps.back().intersections.front().bearings.size() == 1);
363 BOOST_ASSERT(steps.back().intersections.front().entry.size() == 1);
364 BOOST_ASSERT(steps.back().maneuver.waypoint_type == WaypointType::Arrive);
365
366 // make sure we still have enough segments
367 if (steps.size() < 2 || geometry.locations.size() == 2)
368 return;
369
370 BOOST_ASSERT(geometry.locations.size() >= steps.size());
371 auto &next_to_last_step = *(steps.end() - 2);
372 // in the end, the situation with the roundabout cannot occur. As a result, we can remove
373 // all zero-length instructions
374 if (next_to_last_step.distance <= 1 && steps.size() > 2)
375 {
376 geometry.segment_offsets.pop_back();
377 // remove all the last coordinates from the geometry
378 geometry.locations.resize(geometry.segment_offsets.back() + 1);
379 geometry.annotations.resize(geometry.segment_offsets.back());
380 geometry.osm_node_ids.resize(geometry.segment_offsets.back() + 1);
381
382 BOOST_ASSERT(geometry.segment_distances.back() <= 1);
383 geometry.segment_distances.pop_back();
384
385 next_to_last_step.maneuver.waypoint_type = WaypointType::Arrive;
386 next_to_last_step.maneuver.instruction = TurnInstruction::NO_TURN();
387 next_to_last_step.maneuver.bearing_after = 0;
388 next_to_last_step.intersections.front().lanes = util::guidance::LaneTuple();
389 next_to_last_step.intersections.front().lane_description.clear();
390 next_to_last_step.geometry_end = next_to_last_step.geometry_begin + 1;
391 BOOST_ASSERT(next_to_last_step.intersections.size() == 1);
392 auto &last_intersection = next_to_last_step.intersections.back();
393 last_intersection.bearings = {last_intersection.bearings[last_intersection.in]};
394 last_intersection.entry = {true};
395 last_intersection.out = IntermediateIntersection::NO_INDEX;
396 last_intersection.in = 0;
397 steps.pop_back();
398
399 // Because we eliminated a really short segment, it was probably
400 // near an intersection. The convention is *not* to make the
401 // turn, so the `arrive` instruction should be on the same road
402 // as the segment before it. Thus, we have to copy the names
403 // and travel modes from the new next_to_last step.
404 auto &new_next_to_last = *(steps.end() - 2);
405 next_to_last_step.AdaptStepSignage(new_next_to_last);
406 next_to_last_step.mode = new_next_to_last.mode;
407 // the geometry indices of the last step are already correct;
408 }
409 else if (util::coordinate_calculation::haversineDistance(
410 geometry.locations[geometry.locations.size() - 2],
411 geometry.locations[geometry.locations.size() - 1]) <= 1)
412 {
413 // correct steps but duplicated coordinate in the end.
414 // This can happen if the last coordinate snaps to a node in the unpacked geometry
415 geometry.locations.pop_back();
416 geometry.annotations.pop_back();
417 geometry.osm_node_ids.pop_back();
418 geometry.segment_offsets.back()--;
419 // since the last geometry includes the location of arrival, the arrival instruction
420 // geometry overlaps with the previous segment
421 BOOST_ASSERT(next_to_last_step.geometry_end == steps.back().geometry_begin + 1);
422 BOOST_ASSERT(next_to_last_step.geometry_begin < next_to_last_step.geometry_end);
423 next_to_last_step.geometry_end--;
424 auto &last_step = steps.back();
425 last_step.geometry_begin--;
426 last_step.geometry_end--;
427 BOOST_ASSERT(next_to_last_step.geometry_end == last_step.geometry_begin + 1);
428 BOOST_ASSERT(last_step.geometry_begin == last_step.geometry_end - 1);
429 BOOST_ASSERT(next_to_last_step.geometry_end >= 2);
430 // we changed the geometry, we need to recalculate the bearing
431 auto bearing = std::round(util::coordinate_calculation::bearing(
432 geometry.locations[next_to_last_step.geometry_end - 2],
433 geometry.locations[last_step.geometry_begin]));
434 last_step.maneuver.bearing_before = bearing;
435 last_step.intersections.front().bearings.front() = util::bearing::reverse(bearing);
436 }
437
438 BOOST_ASSERT(geometry.segment_offsets.back() + 1 == geometry.locations.size());
439 BOOST_ASSERT(geometry.segment_offsets.back() + 1 == geometry.osm_node_ids.size());
440 BOOST_ASSERT(geometry.segment_offsets.back() == geometry.annotations.size());
441
442 BOOST_ASSERT(steps.back().geometry_end == geometry.locations.size());
443
444 BOOST_ASSERT(steps.front().intersections.size() >= 1);
445 BOOST_ASSERT(steps.front().intersections.front().bearings.size() == 1);
446 BOOST_ASSERT(steps.front().intersections.front().entry.size() == 1);
447 BOOST_ASSERT(steps.front().maneuver.waypoint_type == WaypointType::Depart);
448
449 BOOST_ASSERT(steps.back().intersections.size() == 1);
450 BOOST_ASSERT(steps.back().intersections.front().bearings.size() == 1);
451 BOOST_ASSERT(steps.back().intersections.front().entry.size() == 1);
452 BOOST_ASSERT(steps.back().maneuver.waypoint_type == WaypointType::Arrive);
453 }
454
455 // assign relative locations to depart/arrive instructions
assignRelativeLocations(std::vector<RouteStep> steps,const LegGeometry & leg_geometry,const PhantomNode & source_node,const PhantomNode & target_node)456 std::vector<RouteStep> assignRelativeLocations(std::vector<RouteStep> steps,
457 const LegGeometry &leg_geometry,
458 const PhantomNode &source_node,
459 const PhantomNode &target_node)
460 {
461 // We report the relative position of source/target to the road only within a range that is
462 // sufficiently different but not full of the path
463 BOOST_ASSERT(steps.size() >= 2);
464 BOOST_ASSERT(leg_geometry.locations.size() >= 2);
465 const constexpr double MINIMAL_RELATIVE_DISTANCE = 5., MAXIMAL_RELATIVE_DISTANCE = 300.;
466 const auto distance_to_start = util::coordinate_calculation::haversineDistance(
467 source_node.input_location, leg_geometry.locations[0]);
468 const auto initial_modifier =
469 distance_to_start >= MINIMAL_RELATIVE_DISTANCE &&
470 distance_to_start <= MAXIMAL_RELATIVE_DISTANCE
471 ? bearingToDirectionModifier(util::coordinate_calculation::computeAngle(
472 source_node.input_location, leg_geometry.locations[0], leg_geometry.locations[1]))
473 : DirectionModifier::UTurn;
474
475 steps.front().maneuver.instruction.direction_modifier = initial_modifier;
476
477 const auto distance_from_end = util::coordinate_calculation::haversineDistance(
478 target_node.input_location, leg_geometry.locations.back());
479 const auto final_modifier =
480 distance_from_end >= MINIMAL_RELATIVE_DISTANCE &&
481 distance_from_end <= MAXIMAL_RELATIVE_DISTANCE
482 ? bearingToDirectionModifier(util::coordinate_calculation::computeAngle(
483 leg_geometry.locations[leg_geometry.locations.size() - 2],
484 leg_geometry.locations[leg_geometry.locations.size() - 1],
485 target_node.input_location))
486 : DirectionModifier::UTurn;
487
488 steps.back().maneuver.instruction.direction_modifier = final_modifier;
489
490 BOOST_ASSERT(steps.front().intersections.size() >= 1);
491 BOOST_ASSERT(steps.front().intersections.front().bearings.size() == 1);
492 BOOST_ASSERT(steps.front().intersections.front().entry.size() == 1);
493 BOOST_ASSERT(steps.front().maneuver.waypoint_type == WaypointType::Depart);
494
495 BOOST_ASSERT(steps.back().intersections.size() == 1);
496 BOOST_ASSERT(steps.back().intersections.front().bearings.size() == 1);
497 BOOST_ASSERT(steps.back().intersections.front().entry.size() == 1);
498 BOOST_ASSERT(steps.back().maneuver.waypoint_type == WaypointType::Arrive);
499 return steps;
500 }
501
resyncGeometry(LegGeometry leg_geometry,const std::vector<RouteStep> & steps)502 LegGeometry resyncGeometry(LegGeometry leg_geometry, const std::vector<RouteStep> &steps)
503 {
504 // The geometry uses an adjacency array-like structure for representation.
505 // To sync it back up with the steps, we cann add a segment for every step.
506 leg_geometry.segment_offsets.clear();
507 leg_geometry.segment_distances.clear();
508 leg_geometry.segment_offsets.push_back(0);
509
510 for (const auto &step : steps)
511 {
512 leg_geometry.segment_distances.push_back(step.distance);
513 // the leg geometry does not follow the begin/end-convetion. So we have to subtract one
514 // to get the back-index.
515 leg_geometry.segment_offsets.push_back(step.geometry_end - 1);
516 }
517
518 // remove the data from the reached-target step again
519 leg_geometry.segment_offsets.pop_back();
520 leg_geometry.segment_distances.pop_back();
521
522 return leg_geometry;
523 }
524
buildIntersections(std::vector<RouteStep> steps)525 std::vector<RouteStep> buildIntersections(std::vector<RouteStep> steps)
526 {
527 std::size_t last_valid_instruction = 0;
528 for (std::size_t step_index = 0; step_index < steps.size(); ++step_index)
529 {
530 auto &step = steps[step_index];
531 const auto instruction = step.maneuver.instruction;
532 if (instruction.type == TurnType::Suppressed)
533 {
534 BOOST_ASSERT(steps[last_valid_instruction].mode == step.mode);
535 // count intersections. We cannot use exit, since intersections can follow directly
536 // after a roundabout
537 steps[last_valid_instruction].ElongateBy(step);
538 steps[step_index].Invalidate();
539 }
540 else if (!isSilent(instruction))
541 {
542
543 // End of road is a turn that helps to identify the location of a turn. If the turn does
544 // not pass by any oter intersections, the end-of-road characteristic does not improve
545 // the instructions.
546 // Here we reduce the verbosity of our output by reducing end-of-road emissions in cases
547 // where no intersections have been passed in between.
548 // Since the instruction is located at the beginning of a step, we need to check the
549 // previous instruction.
550 if (instruction.type == TurnType::EndOfRoad)
551 {
552 BOOST_ASSERT(step_index > 0);
553 const auto &previous_step = steps[last_valid_instruction];
554 if (previous_step.intersections.size() < MIN_END_OF_ROAD_INTERSECTIONS)
555 {
556 bool same_name =
557 !(step.name.empty() && step.ref.empty()) &&
558 !util::guidance::requiresNameAnnounced(previous_step.name,
559 previous_step.ref,
560 previous_step.pronunciation,
561 previous_step.exits,
562 step.name,
563 step.ref,
564 step.pronunciation,
565 step.exits);
566
567 step.maneuver.instruction.type =
568 same_name ? TurnType::Continue : TurnType::Turn;
569 }
570 }
571
572 // Remember the last non silent instruction
573 last_valid_instruction = step_index;
574 }
575 }
576 return removeNoTurnInstructions(std::move(steps));
577 }
578
applyOverrides(const datafacade::BaseDataFacade & facade,std::vector<RouteStep> & steps,const LegGeometry & leg_geometry)579 void applyOverrides(const datafacade::BaseDataFacade &facade,
580 std::vector<RouteStep> &steps,
581 const LegGeometry &leg_geometry)
582 {
583 // Find overrides that match, and apply them
584 // The +/-1 here are to remove the depart and arrive steps, which
585 // we don't allow updates to
586 for (auto current_step_it = steps.begin(); current_step_it != steps.end(); ++current_step_it)
587 {
588 util::Log(logDEBUG) << "Searching for " << current_step_it->from_id << std::endl;
589 const auto overrides = facade.GetOverridesThatStartAt(current_step_it->from_id);
590 if (overrides.empty())
591 continue;
592 util::Log(logDEBUG) << "~~~~ GOT A HIT, checking the rest ~~~" << std::endl;
593 for (const extractor::ManeuverOverride &maneuver_relation : overrides)
594 {
595 util::Log(logDEBUG) << "Override sequence is ";
596 for (auto &n : maneuver_relation.node_sequence)
597 {
598 util::Log(logDEBUG) << n << " ";
599 }
600 util::Log(logDEBUG) << std::endl;
601 util::Log(logDEBUG) << "Override type is "
602 << osrm::guidance::internalInstructionTypeToString(
603 maneuver_relation.override_type)
604 << std::endl;
605 util::Log(logDEBUG) << "Override direction is "
606 << osrm::guidance::instructionModifierToString(
607 maneuver_relation.direction)
608 << std::endl;
609
610 util::Log(logDEBUG) << "Route sequence is ";
611 for (auto it = current_step_it; it != steps.end(); ++it)
612 {
613 util::Log(logDEBUG) << it->from_id << " ";
614 }
615 util::Log(logDEBUG) << std::endl;
616
617 auto search_iter = maneuver_relation.node_sequence.begin();
618 auto route_iter = current_step_it;
619 while (search_iter != maneuver_relation.node_sequence.end())
620 {
621 if (route_iter == steps.end())
622 break;
623
624 if (*search_iter == route_iter->from_id)
625 {
626 ++search_iter;
627 ++route_iter;
628 continue;
629 }
630 // Skip over duplicated EBNs in the step array
631 // EBNs are sometime duplicated because guidance code inserts
632 // "fake" steps that it later removes. This hasn't happened yet
633 // at this point, but we can safely just skip past the dupes.
634 if ((route_iter - 1)->from_id == route_iter->from_id)
635 {
636 ++route_iter;
637 continue;
638 }
639 // If we get here, the values got out of sync so it's not
640 // a match.
641 break;
642 }
643
644 // We got a match, update using the instruction_node
645 if (search_iter == maneuver_relation.node_sequence.end())
646 {
647 util::Log(logDEBUG) << "Node sequence matched, looking for the step "
648 << "that has the via node" << std::endl;
649 const auto via_node_coords =
650 facade.GetCoordinateOfNode(maneuver_relation.instruction_node);
651 // Find the step that has the instruction_node at the intersection point
652 auto step_to_update = std::find_if(
653 current_step_it,
654 route_iter,
655 [&leg_geometry, &via_node_coords](const auto &step) {
656 util::Log(logDEBUG) << "Leg geom from " << step.geometry_begin << " to "
657 << step.geometry_end << std::endl;
658
659 // iterators over geometry of current step
660 auto begin = leg_geometry.locations.begin() + step.geometry_begin;
661 auto end = leg_geometry.locations.begin() + step.geometry_end;
662 auto via_match = std::find_if(begin, end, [&](const auto &location) {
663 return location == via_node_coords;
664 });
665 if (via_match != end)
666 {
667 util::Log(logDEBUG)
668 << "Found geometry match at "
669 << (std::distance(begin, end) - std::distance(via_match, end))
670 << std::endl;
671 }
672 util::Log(logDEBUG)
673 << ((*(leg_geometry.locations.begin() + step.geometry_begin) ==
674 via_node_coords)
675 ? "true"
676 : "false")
677 << std::endl;
678 return *(leg_geometry.locations.begin() + step.geometry_begin) ==
679 via_node_coords;
680 // return via_match != end;
681 });
682 // We found a step that had the intersection_node coordinate
683 // in its geometry
684 if (step_to_update != route_iter)
685 {
686 // Don't update the last step (it's an arrive instruction)
687 util::Log(logDEBUG) << "Updating step "
688 << std::distance(steps.begin(), steps.end()) -
689 std::distance(step_to_update, steps.end())
690 << std::endl;
691 if (maneuver_relation.override_type != osrm::guidance::TurnType::MaxTurnType)
692 {
693 util::Log(logDEBUG) << " instruction was "
694 << osrm::guidance::internalInstructionTypeToString(
695 step_to_update->maneuver.instruction.type)
696 << " now "
697 << osrm::guidance::internalInstructionTypeToString(
698 maneuver_relation.override_type)
699 << std::endl;
700 step_to_update->maneuver.instruction.type = maneuver_relation.override_type;
701 }
702 if (maneuver_relation.direction !=
703 osrm::guidance::DirectionModifier::MaxDirectionModifier)
704 {
705 util::Log(logDEBUG)
706 << " direction was "
707 << osrm::guidance::instructionModifierToString(
708 step_to_update->maneuver.instruction.direction_modifier)
709 << " now "
710 << osrm::guidance::instructionModifierToString(
711 maneuver_relation.direction)
712 << std::endl;
713 step_to_update->maneuver.instruction.direction_modifier =
714 maneuver_relation.direction;
715 }
716 // step_to_update->is_overridden = true;
717 }
718 }
719 }
720 util::Log(logDEBUG) << "Done tweaking steps" << std::endl;
721 }
722 }
723
724 } // namespace guidance
725 } // namespace engine
726 } // namespace osrm
727