1 #ifndef GEOSPATIAL_QUERY_HPP
2 #define GEOSPATIAL_QUERY_HPP
3
4 #include "engine/approach.hpp"
5 #include "engine/phantom_node.hpp"
6 #include "util/bearing.hpp"
7 #include "util/coordinate_calculation.hpp"
8 #include "util/rectangle.hpp"
9 #include "util/typedefs.hpp"
10 #include "util/web_mercator.hpp"
11
12 #include "osrm/coordinate.hpp"
13
14 #include <algorithm>
15 #include <cmath>
16 #include <iterator>
17 #include <memory>
18 #include <vector>
19
20 namespace osrm
21 {
22 namespace engine
23 {
24
boolPairAnd(const std::pair<bool,bool> & A,const std::pair<bool,bool> & B)25 inline std::pair<bool, bool> boolPairAnd(const std::pair<bool, bool> &A,
26 const std::pair<bool, bool> &B)
27 {
28 return std::make_pair(A.first && B.first, A.second && B.second);
29 }
30
31 // Implements complex queries on top of an RTree and builds PhantomNodes from it.
32 //
33 // Only holds a weak reference on the RTree and coordinates!
34 template <typename RTreeT, typename DataFacadeT> class GeospatialQuery
35 {
36 using EdgeData = typename RTreeT::EdgeData;
37 using CoordinateList = typename RTreeT::CoordinateList;
38 using CandidateSegment = typename RTreeT::CandidateSegment;
39
40 public:
GeospatialQuery(RTreeT & rtree_,const CoordinateList & coordinates_,DataFacadeT & datafacade_)41 GeospatialQuery(RTreeT &rtree_, const CoordinateList &coordinates_, DataFacadeT &datafacade_)
42 : rtree(rtree_), coordinates(coordinates_), datafacade(datafacade_)
43 {
44 }
45
Search(const util::RectangleInt2D & bbox)46 std::vector<EdgeData> Search(const util::RectangleInt2D &bbox)
47 {
48 return rtree.SearchInBox(bbox);
49 }
50
51 // Returns nearest PhantomNodes in the given bearing range within max_distance.
52 // Does not filter by small/big component!
53 std::vector<PhantomNodeWithDistance>
NearestPhantomNodesInRange(const util::Coordinate input_coordinate,const double max_distance,const Approach approach,const bool use_all_edges) const54 NearestPhantomNodesInRange(const util::Coordinate input_coordinate,
55 const double max_distance,
56 const Approach approach,
57 const bool use_all_edges) const
58 {
59 auto results = rtree.Nearest(
60 input_coordinate,
61 [this, approach, &input_coordinate, use_all_edges](const CandidateSegment &segment) {
62 return boolPairAnd(
63 boolPairAnd(HasValidEdge(segment, use_all_edges), CheckSegmentExclude(segment)),
64 CheckApproach(input_coordinate, segment, approach));
65 },
66 [this, max_distance, input_coordinate](const std::size_t,
67 const CandidateSegment &segment) {
68 return CheckSegmentDistance(input_coordinate, segment, max_distance);
69 });
70
71 return MakePhantomNodes(input_coordinate, results);
72 }
73
74 // Returns nearest PhantomNodes in the given bearing range within max_distance.
75 // Does not filter by small/big component!
76 std::vector<PhantomNodeWithDistance>
NearestPhantomNodesInRange(const util::Coordinate input_coordinate,const double max_distance,const int bearing,const int bearing_range,const Approach approach,const bool use_all_edges) const77 NearestPhantomNodesInRange(const util::Coordinate input_coordinate,
78 const double max_distance,
79 const int bearing,
80 const int bearing_range,
81 const Approach approach,
82 const bool use_all_edges) const
83 {
84 auto results = rtree.Nearest(
85 input_coordinate,
86 [this, approach, &input_coordinate, bearing, bearing_range, use_all_edges](
87 const CandidateSegment &segment) {
88 auto use_direction =
89 boolPairAnd(CheckSegmentBearing(segment, bearing, bearing_range),
90 boolPairAnd(HasValidEdge(segment, use_all_edges),
91 CheckSegmentExclude(segment)));
92 use_direction =
93 boolPairAnd(use_direction, CheckApproach(input_coordinate, segment, approach));
94 return use_direction;
95 },
96 [this, max_distance, input_coordinate](const std::size_t,
97 const CandidateSegment &segment) {
98 return CheckSegmentDistance(input_coordinate, segment, max_distance);
99 });
100
101 return MakePhantomNodes(input_coordinate, results);
102 }
103
104 // Returns max_results nearest PhantomNodes in the given bearing range.
105 // Does not filter by small/big component!
106 std::vector<PhantomNodeWithDistance>
NearestPhantomNodes(const util::Coordinate input_coordinate,const unsigned max_results,const int bearing,const int bearing_range,const Approach approach) const107 NearestPhantomNodes(const util::Coordinate input_coordinate,
108 const unsigned max_results,
109 const int bearing,
110 const int bearing_range,
111 const Approach approach) const
112 {
113 auto results = rtree.Nearest(
114 input_coordinate,
115 [this, approach, &input_coordinate, bearing, bearing_range](
116 const CandidateSegment &segment) {
117 auto use_direction =
118 boolPairAnd(CheckSegmentBearing(segment, bearing, bearing_range),
119 boolPairAnd(HasValidEdge(segment), CheckSegmentExclude(segment)));
120 return boolPairAnd(use_direction,
121 CheckApproach(input_coordinate, segment, approach));
122 },
123 [max_results](const std::size_t num_results, const CandidateSegment &) {
124 return num_results >= max_results;
125 });
126
127 return MakePhantomNodes(input_coordinate, results);
128 }
129
130 // Returns max_results nearest PhantomNodes in the given bearing range within the maximum
131 // distance.
132 // Does not filter by small/big component!
133 std::vector<PhantomNodeWithDistance>
NearestPhantomNodes(const util::Coordinate input_coordinate,const unsigned max_results,const double max_distance,const int bearing,const int bearing_range,const Approach approach) const134 NearestPhantomNodes(const util::Coordinate input_coordinate,
135 const unsigned max_results,
136 const double max_distance,
137 const int bearing,
138 const int bearing_range,
139 const Approach approach) const
140 {
141 auto results = rtree.Nearest(
142 input_coordinate,
143 [this, approach, &input_coordinate, bearing, bearing_range](
144 const CandidateSegment &segment) {
145 auto use_direction =
146 boolPairAnd(CheckSegmentBearing(segment, bearing, bearing_range),
147 boolPairAnd(HasValidEdge(segment), CheckSegmentExclude(segment)));
148 return boolPairAnd(use_direction,
149 CheckApproach(input_coordinate, segment, approach));
150 },
151 [this, max_distance, max_results, input_coordinate](const std::size_t num_results,
152 const CandidateSegment &segment) {
153 return num_results >= max_results ||
154 CheckSegmentDistance(input_coordinate, segment, max_distance);
155 });
156
157 return MakePhantomNodes(input_coordinate, results);
158 }
159
160 // Returns max_results nearest PhantomNodes.
161 // Does not filter by small/big component!
162 std::vector<PhantomNodeWithDistance>
NearestPhantomNodes(const util::Coordinate input_coordinate,const unsigned max_results,const Approach approach) const163 NearestPhantomNodes(const util::Coordinate input_coordinate,
164 const unsigned max_results,
165 const Approach approach) const
166 {
167 auto results = rtree.Nearest(
168 input_coordinate,
169 [this, approach, &input_coordinate](const CandidateSegment &segment) {
170 return boolPairAnd(boolPairAnd(HasValidEdge(segment), CheckSegmentExclude(segment)),
171 CheckApproach(input_coordinate, segment, approach));
172 },
173 [max_results](const std::size_t num_results, const CandidateSegment &) {
174 return num_results >= max_results;
175 });
176
177 return MakePhantomNodes(input_coordinate, results);
178 }
179
180 // Returns max_results nearest PhantomNodes in the given max distance.
181 // Does not filter by small/big component!
182 std::vector<PhantomNodeWithDistance>
NearestPhantomNodes(const util::Coordinate input_coordinate,const unsigned max_results,const double max_distance,const Approach approach) const183 NearestPhantomNodes(const util::Coordinate input_coordinate,
184 const unsigned max_results,
185 const double max_distance,
186 const Approach approach) const
187 {
188 auto results = rtree.Nearest(
189 input_coordinate,
190 [this, approach, &input_coordinate](const CandidateSegment &segment) {
191 return boolPairAnd(boolPairAnd(HasValidEdge(segment), CheckSegmentExclude(segment)),
192 CheckApproach(input_coordinate, segment, approach));
193 },
194 [this, max_distance, max_results, input_coordinate](const std::size_t num_results,
195 const CandidateSegment &segment) {
196 return num_results >= max_results ||
197 CheckSegmentDistance(input_coordinate, segment, max_distance);
198 });
199
200 return MakePhantomNodes(input_coordinate, results);
201 }
202
203 // Returns the nearest phantom node. If this phantom node is not from a big component
204 // a second phantom node is return that is the nearest coordinate in a big component.
205 std::pair<PhantomNode, PhantomNode>
NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,const double max_distance,const Approach approach,const bool use_all_edges) const206 NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,
207 const double max_distance,
208 const Approach approach,
209 const bool use_all_edges) const
210 {
211 bool has_small_component = false;
212 bool has_big_component = false;
213 auto results = rtree.Nearest(
214 input_coordinate,
215 [this,
216 approach,
217 &input_coordinate,
218 &has_big_component,
219 &has_small_component,
220 &use_all_edges](const CandidateSegment &segment) {
221 auto use_segment =
222 (!has_small_component || (!has_big_component && !IsTinyComponent(segment)));
223 auto use_directions = std::make_pair(use_segment, use_segment);
224 const auto valid_edges = HasValidEdge(segment, use_all_edges);
225 const auto admissible_segments = CheckSegmentExclude(segment);
226 use_directions = boolPairAnd(use_directions, admissible_segments);
227 use_directions = boolPairAnd(use_directions, valid_edges);
228 use_directions =
229 boolPairAnd(use_directions, CheckApproach(input_coordinate, segment, approach));
230
231 if (use_directions.first || use_directions.second)
232 {
233 has_big_component = has_big_component || !IsTinyComponent(segment);
234 has_small_component = has_small_component || IsTinyComponent(segment);
235 }
236
237 return use_directions;
238 },
239 [this, &has_big_component, max_distance, input_coordinate](
240 const std::size_t num_results, const CandidateSegment &segment) {
241 return (num_results > 0 && has_big_component) ||
242 CheckSegmentDistance(input_coordinate, segment, max_distance);
243 });
244
245 if (results.size() == 0)
246 {
247 return std::make_pair(PhantomNode{}, PhantomNode{});
248 }
249
250 BOOST_ASSERT(results.size() == 1 || results.size() == 2);
251 return std::make_pair(MakePhantomNode(input_coordinate, results.front()).phantom_node,
252 MakePhantomNode(input_coordinate, results.back()).phantom_node);
253 }
254
255 // Returns the nearest phantom node. If this phantom node is not from a big component
256 // a second phantom node is return that is the nearest coordinate in a big component.
257 std::pair<PhantomNode, PhantomNode>
NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,const Approach approach,const bool use_all_edges) const258 NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,
259 const Approach approach,
260 const bool use_all_edges) const
261 {
262 bool has_small_component = false;
263 bool has_big_component = false;
264 auto results = rtree.Nearest(
265 input_coordinate,
266 [this,
267 approach,
268 &input_coordinate,
269 &has_big_component,
270 &has_small_component,
271 &use_all_edges](const CandidateSegment &segment) {
272 auto use_segment =
273 (!has_small_component || (!has_big_component && !IsTinyComponent(segment)));
274 auto use_directions = std::make_pair(use_segment, use_segment);
275
276 const auto valid_edges = HasValidEdge(segment, use_all_edges);
277 const auto admissible_segments = CheckSegmentExclude(segment);
278 use_directions = boolPairAnd(use_directions, admissible_segments);
279 use_directions = boolPairAnd(use_directions, valid_edges);
280 use_directions =
281 boolPairAnd(use_directions, CheckApproach(input_coordinate, segment, approach));
282
283 if (use_directions.first || use_directions.second)
284 {
285 has_big_component = has_big_component || !IsTinyComponent(segment);
286 has_small_component = has_small_component || IsTinyComponent(segment);
287 }
288
289 return use_directions;
290 },
291 [&has_big_component](const std::size_t num_results, const CandidateSegment &) {
292 return num_results > 0 && has_big_component;
293 });
294
295 if (results.size() == 0)
296 {
297 return std::make_pair(PhantomNode{}, PhantomNode{});
298 }
299
300 BOOST_ASSERT(results.size() == 1 || results.size() == 2);
301 return std::make_pair(MakePhantomNode(input_coordinate, results.front()).phantom_node,
302 MakePhantomNode(input_coordinate, results.back()).phantom_node);
303 }
304
305 // Returns the nearest phantom node. If this phantom node is not from a big component
306 // a second phantom node is return that is the nearest coordinate in a big component.
307 std::pair<PhantomNode, PhantomNode>
NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,const int bearing,const int bearing_range,const Approach approach,const bool use_all_edges) const308 NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,
309 const int bearing,
310 const int bearing_range,
311 const Approach approach,
312 const bool use_all_edges) const
313 {
314 bool has_small_component = false;
315 bool has_big_component = false;
316 auto results = rtree.Nearest(
317 input_coordinate,
318 [this,
319 approach,
320 &input_coordinate,
321 bearing,
322 bearing_range,
323 &has_big_component,
324 &has_small_component,
325 &use_all_edges](const CandidateSegment &segment) {
326 auto use_segment =
327 (!has_small_component || (!has_big_component && !IsTinyComponent(segment)));
328 auto use_directions = std::make_pair(use_segment, use_segment);
329 const auto admissible_segments = CheckSegmentExclude(segment);
330
331 if (use_segment)
332 {
333 use_directions =
334 boolPairAnd(CheckSegmentBearing(segment, bearing, bearing_range),
335 HasValidEdge(segment, use_all_edges));
336 use_directions = boolPairAnd(use_directions, admissible_segments);
337 use_directions = boolPairAnd(
338 use_directions, CheckApproach(input_coordinate, segment, approach));
339
340 if (use_directions.first || use_directions.second)
341 {
342 has_big_component = has_big_component || !IsTinyComponent(segment);
343 has_small_component = has_small_component || IsTinyComponent(segment);
344 }
345 }
346
347 return use_directions;
348 },
349 [&has_big_component](const std::size_t num_results, const CandidateSegment &) {
350 return num_results > 0 && has_big_component;
351 });
352
353 if (results.size() == 0)
354 {
355 return std::make_pair(PhantomNode{}, PhantomNode{});
356 }
357
358 BOOST_ASSERT(results.size() > 0);
359 return std::make_pair(MakePhantomNode(input_coordinate, results.front()).phantom_node,
360 MakePhantomNode(input_coordinate, results.back()).phantom_node);
361 }
362
363 // Returns the nearest phantom node. If this phantom node is not from a big component
364 // a second phantom node is return that is the nearest coordinate in a big component.
365 std::pair<PhantomNode, PhantomNode>
NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,const double max_distance,const int bearing,const int bearing_range,const Approach approach,const bool use_all_edges) const366 NearestPhantomNodeWithAlternativeFromBigComponent(const util::Coordinate input_coordinate,
367 const double max_distance,
368 const int bearing,
369 const int bearing_range,
370 const Approach approach,
371 const bool use_all_edges) const
372 {
373 bool has_small_component = false;
374 bool has_big_component = false;
375 auto results = rtree.Nearest(
376 input_coordinate,
377 [this,
378 approach,
379 &input_coordinate,
380 bearing,
381 bearing_range,
382 &has_big_component,
383 &has_small_component,
384 &use_all_edges](const CandidateSegment &segment) {
385 auto use_segment =
386 (!has_small_component || (!has_big_component && !IsTinyComponent(segment)));
387 auto use_directions = std::make_pair(use_segment, use_segment);
388 const auto admissible_segments = CheckSegmentExclude(segment);
389
390 if (use_segment)
391 {
392 use_directions =
393 boolPairAnd(CheckSegmentBearing(segment, bearing, bearing_range),
394 HasValidEdge(segment, use_all_edges));
395 use_directions = boolPairAnd(use_directions, admissible_segments);
396 use_directions = boolPairAnd(
397 use_directions, CheckApproach(input_coordinate, segment, approach));
398
399 if (use_directions.first || use_directions.second)
400 {
401 has_big_component = has_big_component || !IsTinyComponent(segment);
402 has_small_component = has_small_component || IsTinyComponent(segment);
403 }
404 }
405
406 return use_directions;
407 },
408 [this, &has_big_component, max_distance, input_coordinate](
409 const std::size_t num_results, const CandidateSegment &segment) {
410 return (num_results > 0 && has_big_component) ||
411 CheckSegmentDistance(input_coordinate, segment, max_distance);
412 });
413
414 if (results.size() == 0)
415 {
416 return std::make_pair(PhantomNode{}, PhantomNode{});
417 }
418
419 BOOST_ASSERT(results.size() > 0);
420 return std::make_pair(MakePhantomNode(input_coordinate, results.front()).phantom_node,
421 MakePhantomNode(input_coordinate, results.back()).phantom_node);
422 }
423
424 private:
425 std::vector<PhantomNodeWithDistance>
MakePhantomNodes(const util::Coordinate input_coordinate,const std::vector<EdgeData> & results) const426 MakePhantomNodes(const util::Coordinate input_coordinate,
427 const std::vector<EdgeData> &results) const
428 {
429 std::vector<PhantomNodeWithDistance> distance_and_phantoms(results.size());
430 std::transform(results.begin(),
431 results.end(),
432 distance_and_phantoms.begin(),
433 [this, &input_coordinate](const EdgeData &data) {
434 return MakePhantomNode(input_coordinate, data);
435 });
436 return distance_and_phantoms;
437 }
438
MakePhantomNode(const util::Coordinate input_coordinate,const EdgeData & data) const439 PhantomNodeWithDistance MakePhantomNode(const util::Coordinate input_coordinate,
440 const EdgeData &data) const
441 {
442 util::Coordinate point_on_segment;
443 double ratio;
444 const auto current_perpendicular_distance =
445 util::coordinate_calculation::perpendicularDistance(coordinates[data.u],
446 coordinates[data.v],
447 input_coordinate,
448 point_on_segment,
449 ratio);
450
451 // Find the node-based-edge that this belongs to, and directly
452 // calculate the forward_weight, forward_offset, reverse_weight, reverse_offset
453
454 BOOST_ASSERT(data.forward_segment_id.enabled || data.reverse_segment_id.enabled);
455 BOOST_ASSERT(!data.reverse_segment_id.enabled ||
456 datafacade.GetGeometryIndex(data.forward_segment_id.id).id ==
457 datafacade.GetGeometryIndex(data.reverse_segment_id.id).id);
458 const auto geometry_id = datafacade.GetGeometryIndex(data.forward_segment_id.id).id;
459 const auto component_id = datafacade.GetComponentID(data.forward_segment_id.id);
460
461 const auto forward_weights = datafacade.GetUncompressedForwardWeights(geometry_id);
462 const auto reverse_weights = datafacade.GetUncompressedReverseWeights(geometry_id);
463
464 const auto forward_durations = datafacade.GetUncompressedForwardDurations(geometry_id);
465 const auto reverse_durations = datafacade.GetUncompressedReverseDurations(geometry_id);
466
467 const auto forward_geometry = datafacade.GetUncompressedForwardGeometry(geometry_id);
468
469 const auto forward_weight_offset =
470 std::accumulate(forward_weights.begin(),
471 forward_weights.begin() + data.fwd_segment_position,
472 EdgeWeight{0});
473
474 const auto forward_duration_offset =
475 std::accumulate(forward_durations.begin(),
476 forward_durations.begin() + data.fwd_segment_position,
477 EdgeDuration{0});
478
479 EdgeDistance forward_distance_offset = 0;
480 // Sum up the distance from the start to the fwd_segment_position
481 for (auto current = forward_geometry.begin();
482 current < forward_geometry.begin() + data.fwd_segment_position;
483 ++current)
484 {
485 forward_distance_offset += util::coordinate_calculation::fccApproximateDistance(
486 datafacade.GetCoordinateOfNode(*current),
487 datafacade.GetCoordinateOfNode(*std::next(current)));
488 }
489
490 BOOST_ASSERT(data.fwd_segment_position <
491 std::distance(forward_durations.begin(), forward_durations.end()));
492
493 EdgeWeight forward_weight = forward_weights[data.fwd_segment_position];
494 EdgeDuration forward_duration = forward_durations[data.fwd_segment_position];
495 EdgeDistance forward_distance = util::coordinate_calculation::fccApproximateDistance(
496 datafacade.GetCoordinateOfNode(forward_geometry(data.fwd_segment_position)),
497 point_on_segment);
498
499 const auto reverse_weight_offset =
500 std::accumulate(reverse_weights.begin(),
501 reverse_weights.end() - data.fwd_segment_position - 1,
502 EdgeWeight{0});
503
504 const auto reverse_duration_offset =
505 std::accumulate(reverse_durations.begin(),
506 reverse_durations.end() - data.fwd_segment_position - 1,
507 EdgeDuration{0});
508
509 EdgeDistance reverse_distance_offset = 0;
510 // Sum up the distance from just after the fwd_segment_position to the end
511 for (auto current = forward_geometry.begin() + data.fwd_segment_position + 1;
512 current != std::prev(forward_geometry.end());
513 ++current)
514 {
515 reverse_distance_offset += util::coordinate_calculation::fccApproximateDistance(
516 datafacade.GetCoordinateOfNode(*current),
517 datafacade.GetCoordinateOfNode(*std::next(current)));
518 }
519
520 EdgeWeight reverse_weight =
521 reverse_weights[reverse_weights.size() - data.fwd_segment_position - 1];
522 EdgeDuration reverse_duration =
523 reverse_durations[reverse_durations.size() - data.fwd_segment_position - 1];
524 EdgeDistance reverse_distance = util::coordinate_calculation::fccApproximateDistance(
525 point_on_segment,
526 datafacade.GetCoordinateOfNode(forward_geometry(data.fwd_segment_position + 1)));
527
528 ratio = std::min(1.0, std::max(0.0, ratio));
529 if (data.forward_segment_id.id != SPECIAL_SEGMENTID)
530 {
531 forward_weight = static_cast<EdgeWeight>(forward_weight * ratio);
532 forward_duration = static_cast<EdgeDuration>(forward_duration * ratio);
533 }
534 if (data.reverse_segment_id.id != SPECIAL_SEGMENTID)
535 {
536 reverse_weight -= static_cast<EdgeWeight>(reverse_weight * ratio);
537 reverse_duration -= static_cast<EdgeDuration>(reverse_duration * ratio);
538 }
539
540 // check phantom node segments validity
541 auto areSegmentsValid = [](auto first, auto last) -> bool {
542 return std::find(first, last, INVALID_SEGMENT_WEIGHT) == last;
543 };
544 bool is_forward_valid_source =
545 areSegmentsValid(forward_weights.begin(), forward_weights.end());
546 bool is_forward_valid_target = areSegmentsValid(
547 forward_weights.begin(), forward_weights.begin() + data.fwd_segment_position + 1);
548 bool is_reverse_valid_source =
549 areSegmentsValid(reverse_weights.begin(), reverse_weights.end());
550 bool is_reverse_valid_target = areSegmentsValid(
551 reverse_weights.begin(), reverse_weights.end() - data.fwd_segment_position);
552
553 auto transformed = PhantomNodeWithDistance{
554 PhantomNode{data,
555 component_id,
556 forward_weight,
557 reverse_weight,
558 forward_weight_offset,
559 reverse_weight_offset,
560 forward_distance,
561 reverse_distance,
562 forward_distance_offset,
563 reverse_distance_offset,
564 forward_duration,
565 reverse_duration,
566 forward_duration_offset,
567 reverse_duration_offset,
568 is_forward_valid_source,
569 is_forward_valid_target,
570 is_reverse_valid_source,
571 is_reverse_valid_target,
572 point_on_segment,
573 input_coordinate,
574 static_cast<unsigned short>(util::coordinate_calculation::bearing(
575 coordinates[data.u], coordinates[data.v]))},
576 current_perpendicular_distance};
577
578 return transformed;
579 }
580
CheckSegmentDistance(const Coordinate input_coordinate,const CandidateSegment & segment,const double max_distance) const581 bool CheckSegmentDistance(const Coordinate input_coordinate,
582 const CandidateSegment &segment,
583 const double max_distance) const
584 {
585 BOOST_ASSERT(segment.data.forward_segment_id.id != SPECIAL_SEGMENTID ||
586 !segment.data.forward_segment_id.enabled);
587 BOOST_ASSERT(segment.data.reverse_segment_id.id != SPECIAL_SEGMENTID ||
588 !segment.data.reverse_segment_id.enabled);
589
590 Coordinate wsg84_coordinate =
591 util::web_mercator::toWGS84(segment.fixed_projected_coordinate);
592
593 return util::coordinate_calculation::haversineDistance(input_coordinate, wsg84_coordinate) >
594 max_distance;
595 }
596
CheckSegmentExclude(const CandidateSegment & segment) const597 std::pair<bool, bool> CheckSegmentExclude(const CandidateSegment &segment) const
598 {
599 std::pair<bool, bool> valid = {true, true};
600
601 if (segment.data.forward_segment_id.enabled &&
602 datafacade.ExcludeNode(segment.data.forward_segment_id.id))
603 {
604 valid.first = false;
605 }
606
607 if (segment.data.reverse_segment_id.enabled &&
608 datafacade.ExcludeNode(segment.data.reverse_segment_id.id))
609 {
610 valid.second = false;
611 }
612
613 return valid;
614 }
615
CheckSegmentBearing(const CandidateSegment & segment,const int filter_bearing,const int filter_bearing_range) const616 std::pair<bool, bool> CheckSegmentBearing(const CandidateSegment &segment,
617 const int filter_bearing,
618 const int filter_bearing_range) const
619 {
620 BOOST_ASSERT(segment.data.forward_segment_id.id != SPECIAL_SEGMENTID ||
621 !segment.data.forward_segment_id.enabled);
622 BOOST_ASSERT(segment.data.reverse_segment_id.id != SPECIAL_SEGMENTID ||
623 !segment.data.reverse_segment_id.enabled);
624
625 const double forward_edge_bearing = util::coordinate_calculation::bearing(
626 coordinates[segment.data.u], coordinates[segment.data.v]);
627
628 const double backward_edge_bearing = (forward_edge_bearing + 180) > 360
629 ? (forward_edge_bearing - 180)
630 : (forward_edge_bearing + 180);
631
632 const bool forward_bearing_valid =
633 util::bearing::CheckInBounds(
634 std::round(forward_edge_bearing), filter_bearing, filter_bearing_range) &&
635 segment.data.forward_segment_id.enabled;
636 const bool backward_bearing_valid =
637 util::bearing::CheckInBounds(
638 std::round(backward_edge_bearing), filter_bearing, filter_bearing_range) &&
639 segment.data.reverse_segment_id.enabled;
640 return std::make_pair(forward_bearing_valid, backward_bearing_valid);
641 }
642
643 /**
644 * Checks to see if the edge weights are valid. We might have an edge,
645 * but a traffic update might set the speed to 0 (weight == INVALID_SEGMENT_WEIGHT).
646 * which means that this edge is not currently traversible. If this is the case,
647 * then we shouldn't snap to this edge.
648 */
HasValidEdge(const CandidateSegment & segment,const bool use_all_edges=false) const649 std::pair<bool, bool> HasValidEdge(const CandidateSegment &segment,
650 const bool use_all_edges = false) const
651 {
652
653 bool forward_edge_valid = false;
654 bool reverse_edge_valid = false;
655
656 const auto &data = segment.data;
657 BOOST_ASSERT(data.forward_segment_id.enabled);
658 BOOST_ASSERT(data.forward_segment_id.id != SPECIAL_NODEID);
659 const auto geometry_id = datafacade.GetGeometryIndex(data.forward_segment_id.id).id;
660
661 const auto forward_weights = datafacade.GetUncompressedForwardWeights(geometry_id);
662 if (forward_weights[data.fwd_segment_position] != INVALID_SEGMENT_WEIGHT)
663 {
664 forward_edge_valid = data.forward_segment_id.enabled;
665 }
666
667 const auto reverse_weights = datafacade.GetUncompressedReverseWeights(geometry_id);
668 if (reverse_weights[reverse_weights.size() - data.fwd_segment_position - 1] !=
669 INVALID_SEGMENT_WEIGHT)
670 {
671 reverse_edge_valid = data.reverse_segment_id.enabled;
672 }
673
674 forward_edge_valid = forward_edge_valid && (data.is_startpoint || use_all_edges);
675 reverse_edge_valid = reverse_edge_valid && (data.is_startpoint || use_all_edges);
676
677 return std::make_pair(forward_edge_valid, reverse_edge_valid);
678 }
679
IsTinyComponent(const CandidateSegment & segment) const680 bool IsTinyComponent(const CandidateSegment &segment) const
681 {
682 const auto &data = segment.data;
683 BOOST_ASSERT(data.forward_segment_id.enabled);
684 BOOST_ASSERT(data.forward_segment_id.id != SPECIAL_NODEID);
685 return datafacade.GetComponentID(data.forward_segment_id.id).is_tiny;
686 }
687
CheckApproach(const util::Coordinate & input_coordinate,const CandidateSegment & segment,const Approach approach) const688 std::pair<bool, bool> CheckApproach(const util::Coordinate &input_coordinate,
689 const CandidateSegment &segment,
690 const Approach approach) const
691 {
692 bool isOnewaySegment =
693 !(segment.data.forward_segment_id.enabled && segment.data.reverse_segment_id.enabled);
694 if (!isOnewaySegment && approach == Approach::CURB)
695 {
696 // Check the counter clockwise
697 //
698 // input_coordinate
699 // |
700 // |
701 // segment.data.u ---------------- segment.data.v
702
703 bool input_coordinate_is_at_right = !util::coordinate_calculation::isCCW(
704 coordinates[segment.data.u], coordinates[segment.data.v], input_coordinate);
705
706 if (datafacade.IsLeftHandDriving(segment.data.forward_segment_id.id))
707 input_coordinate_is_at_right = !input_coordinate_is_at_right;
708
709 return std::make_pair(input_coordinate_is_at_right, (!input_coordinate_is_at_right));
710 }
711 return std::make_pair(true, true);
712 }
713
714 const RTreeT &rtree;
715 const CoordinateList &coordinates;
716 DataFacadeT &datafacade;
717 };
718 } // namespace engine
719 } // namespace osrm
720
721 #endif
722