This is an automated email from the git hooks/post-receive script. sebastic pushed a commit to branch master in repository osrm.
commit c4c6335d23921716fa963b4e981334952619cafc Author: Bas Couwenberg <[email protected]> Date: Wed Aug 31 12:52:35 2016 +0200 Imported Upstream version 5.3.3+ds --- CHANGELOG.md | 8 +++ features/guidance/turn-lanes.feature | 25 +++++++- features/testbot/via.feature | 35 +++++++++++ include/engine/datafacade/shared_datafacade.hpp | 5 -- include/engine/routing_algorithms/routing_base.hpp | 73 +++++++++++----------- .../engine/routing_algorithms/shortest_path.hpp | 6 +- src/extractor/extractor_callbacks.cpp | 2 +- src/extractor/guidance/intersection_generator.cpp | 2 +- src/extractor/guidance/turn_lane_data.cpp | 22 +++++++ src/extractor/guidance/turn_lane_handler.cpp | 15 ++--- src/extractor/guidance/turn_lane_matcher.cpp | 44 +++++++++++-- 11 files changed, 175 insertions(+), 62 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index abf3326..49523cf 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,3 +1,11 @@ +# 5.3.3 + Changes from 5.3.2 + - Bugfixes + - Fixed an issue that would result in segfaults for viaroutes with an invalid intermediate segment when u-turns were allowed at the via-location + - Fixed an issue that could result in segfaults when querying roads that could require looping back to the start of a way while using a core factor + - Fixed an issue that could break some testcases when using a core factor + - Fixed an issue with parallel edges that could result in weird routes + # 5.3.2 Changes from 5.3.1 - Bugfixes diff --git a/features/guidance/turn-lanes.feature b/features/guidance/turn-lanes.feature index 3ef5332..8a57c42 100644 --- a/features/guidance/turn-lanes.feature +++ b/features/guidance/turn-lanes.feature @@ -724,8 +724,8 @@ Feature: Turn Lane Guidance And the ways | nodes | name | highway | turn:lanes:forward | - | ab | road | primary | through,right | - | bc | road | primary | through,right | + | ab | road | primary | through;right | + | bc | road | primary | through;right | | cd | road | primary | | | xa | road | primary | | | be | turn | primary | | @@ -846,3 +846,24 @@ Feature: Turn Lane Guidance | waypoints | route | turns | lanes | | d,a |||| # Note: at the moment we don't care about routes, we care about the extract process triggering assertions + + @reverse @2730 + Scenario: Reverse on the right + Given the node map + | a | | | c | | + | | | | b | d | + | f | | | e | | + + And the ways + | nodes | highway | name | turn:lanes:forward | oneway | + | ab | primary | in | left\|through\|right;reverse | yes | + | bc | primary | left | | no | + | bd | primary | through | | no | + | be | primary | right | | no | + | bf | primary | in | | yes | + + When I route I should get + | waypoints | route | turns | lanes | + | a,c | in,left,left | depart,turn left,arrive | ,left:true straight:false right;uturn:false, | + | a,d | in,through,through | depart,new name straight,arrive | ,left:false straight:true right;uturn:false, | + | a,e | in,right,right | depart,turn right,arrive | ,left:false straight:false right;uturn:true, | diff --git a/features/testbot/via.feature b/features/testbot/via.feature index 08a684a..d3092cb 100644 --- a/features/testbot/via.feature +++ b/features/testbot/via.feature @@ -262,3 +262,38 @@ Feature: Via points | 3,2,1 | ab,bc,cd,da,ab,ab,ab,bc,cd,da,ab,ab | 3000m +-1 | | 6,5,4 | bc,cd,da,ab,bc,bc,bc,cd,da,ab,bc,bc | 3000m +-1 | | 9,8,7 | cd,da,ab,bc,cd,cd,cd,da,ab,bc,cd,cd | 3000m +-1 | + + # See issue #2706 + # this case is currently broken. It simply works as put here due to staggered intersections triggering a name collapse. + # See 2824 for further information + @todo + Scenario: Incorrect ordering of nodes can produce multiple U-turns + Given the node map + | | a | | | | + | e | b | c | d | f | + + And the ways + | nodes | oneway | + | abcd | no | + | ebbdcf | yes | + + When I route I should get + | from | to | route | + | e | f | ebbdcf,ebbdcf | + + @2798 + Scenario: UTurns Enabled + Given the node map + | a | b | c | d | e | + + And the query options + | continue_straight | false | + + And the ways + | nodes | oneway | + | abc | yes | + | edc | yes | + + When I route I should get + | waypoints | route | + | a,b,e | | diff --git a/include/engine/datafacade/shared_datafacade.hpp b/include/engine/datafacade/shared_datafacade.hpp index 91e2a02..bdcd5bc 100644 --- a/include/engine/datafacade/shared_datafacade.hpp +++ b/include/engine/datafacade/shared_datafacade.hpp @@ -276,11 +276,6 @@ class SharedDataFacade final : public BaseDataFacade void LoadCoreInformation() { - if (data_layout->num_entries[storage::SharedDataLayout::CORE_MARKER] <= 0) - { - return; - } - auto core_marker_ptr = data_layout->GetBlockPtr<unsigned>( shared_memory, storage::SharedDataLayout::CORE_MARKER); util::ShM<bool, true>::vector is_core_node( diff --git a/include/engine/routing_algorithms/routing_base.hpp b/include/engine/routing_algorithms/routing_base.hpp index 4f77c09..1956cd8 100644 --- a/include/engine/routing_algorithms/routing_base.hpp +++ b/include/engine/routing_algorithms/routing_base.hpp @@ -90,14 +90,11 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface if (new_distance < upper_bound) { // if loops are forced, they are so at the source - if (new_distance >= 0 && - (!force_loop_forward || forward_heap.GetData(node).parent != node) && - (!force_loop_reverse || reverse_heap.GetData(node).parent != node)) - { - middle_node_id = node; - upper_bound = new_distance; - } - else + if ((force_loop_forward && forward_heap.GetData(node).parent == node) || + (force_loop_reverse && reverse_heap.GetData(node).parent == node) || + // in this case we are looking at a bi-directional way where the source + // and target phantom are on the same edge based node + new_distance < 0) { // check whether there is a loop present at the node for (const auto edge : facade->GetAdjacentEdgeRange(node)) @@ -121,6 +118,13 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface } } } + else + { + BOOST_ASSERT(new_distance >= 0); + + middle_node_id = node; + upper_bound = new_distance; + } } } @@ -513,7 +517,12 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface std::vector<NodeID> &packed_path) const { NodeID current_node_id = middle_node_id; - while (current_node_id != search_heap.GetData(current_node_id).parent) + // all initial nodes will have itself as parent, or a node not in the heap + // in case of a core search heap. We need a distinction between core entry nodes + // and start nodes since otherwise start node specific code that assumes + // node == node.parent (e.g. the loop code) might get actived. + while (current_node_id != search_heap.GetData(current_node_id).parent && + search_heap.WasInserted(search_heap.GetData(current_node_id).parent)) { current_node_id = search_heap.GetData(current_node_id).parent; packed_path.emplace_back(current_node_id); @@ -625,8 +634,9 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface NodeID middle = SPECIAL_NODEID; distance = duration_upper_bound; - std::vector<std::pair<NodeID, EdgeWeight>> forward_entry_points; - std::vector<std::pair<NodeID, EdgeWeight>> reverse_entry_points; + using CoreEntryPoint = std::tuple<NodeID, EdgeWeight, NodeID>; + std::vector<CoreEntryPoint> forward_entry_points; + std::vector<CoreEntryPoint> reverse_entry_points; // get offset to account for offsets on phantom nodes on compressed edges const auto min_edge_offset = std::min(0, forward_heap.MinKey()); @@ -643,7 +653,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface { const NodeID node = forward_heap.DeleteMin(); const int key = forward_heap.GetKey(node); - forward_entry_points.emplace_back(node, key); + forward_entry_points.emplace_back(node, key, forward_heap.GetData(node).parent); } else { @@ -664,7 +674,7 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface { const NodeID node = reverse_heap.DeleteMin(); const int key = reverse_heap.GetKey(node); - reverse_entry_points.emplace_back(node, key); + reverse_entry_points.emplace_back(node, key, reverse_heap.GetData(node).parent); } else { @@ -680,36 +690,27 @@ template <class DataFacadeT, class Derived> class BasicRoutingInterface } } } - // TODO check if unordered_set might be faster - // sort by id and increasing by distance - auto entry_point_comparator = [](const std::pair<NodeID, EdgeWeight> &lhs, - const std::pair<NodeID, EdgeWeight> &rhs) { - return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second); - }; - std::sort(forward_entry_points.begin(), forward_entry_points.end(), entry_point_comparator); - std::sort(reverse_entry_points.begin(), reverse_entry_points.end(), entry_point_comparator); - NodeID last_id = SPECIAL_NODEID; + const auto insertInCoreHeap = + [](const CoreEntryPoint &p, SearchEngineData::QueryHeap &core_heap) { + NodeID id; + EdgeWeight weight; + NodeID parent; + // TODO this should use std::apply when we get c++17 support + std::tie(id, weight, parent) = p; + core_heap.Insert(id, weight, parent); + }; + forward_core_heap.Clear(); - reverse_core_heap.Clear(); for (const auto &p : forward_entry_points) { - if (p.first == last_id) - { - continue; - } - forward_core_heap.Insert(p.first, p.second, p.first); - last_id = p.first; + insertInCoreHeap(p, forward_core_heap); } - last_id = SPECIAL_NODEID; + + reverse_core_heap.Clear(); for (const auto &p : reverse_entry_points) { - if (p.first == last_id) - { - continue; - } - reverse_core_heap.Insert(p.first, p.second, p.first); - last_id = p.first; + insertInCoreHeap(p, reverse_core_heap); } // get offset to account for offsets on phantom nodes on compressed edges diff --git a/include/engine/routing_algorithms/shortest_path.hpp b/include/engine/routing_algorithms/shortest_path.hpp index 5d52dc9..c0a338b 100644 --- a/include/engine/routing_algorithms/shortest_path.hpp +++ b/include/engine/routing_algorithms/shortest_path.hpp @@ -114,7 +114,11 @@ class ShortestPathRouting final needs_loop_forwad, needs_loop_backwards); } - new_total_distance += std::min(total_distance_to_forward, total_distance_to_reverse); + // if no route is found between two parts of the via-route, the entire route becomes + // invalid. Adding to invalid edge weight sadly doesn't return an invalid edge weight. Here + // we prevent the possible overflow, faking the addition of infinity + x == infinity + if (new_total_distance != INVALID_EDGE_WEIGHT) + new_total_distance += std::min(total_distance_to_forward, total_distance_to_reverse); } // searches shortest path between: diff --git a/src/extractor/extractor_callbacks.cpp b/src/extractor/extractor_callbacks.cpp index 7d98804..becb166 100644 --- a/src/extractor/extractor_callbacks.cpp +++ b/src/extractor/extractor_callbacks.cpp @@ -1,8 +1,8 @@ -#include "extractor/extractor_callbacks.hpp" #include "extractor/external_memory_node.hpp" #include "extractor/extraction_containers.hpp" #include "extractor/extraction_node.hpp" #include "extractor/extraction_way.hpp" +#include "extractor/extractor_callbacks.hpp" #include "extractor/restriction.hpp" #include "util/for_each_pair.hpp" diff --git a/src/extractor/guidance/intersection_generator.cpp b/src/extractor/guidance/intersection_generator.cpp index 48f3efd..a9355ce 100644 --- a/src/extractor/guidance/intersection_generator.cpp +++ b/src/extractor/guidance/intersection_generator.cpp @@ -277,7 +277,7 @@ Intersection IntersectionGenerator::mergeSegregatedRoads(Intersection intersecti { const double correction_factor = (intersection[1].turn.angle) / 2; for (std::size_t i = 2; i < intersection.size(); ++i) - intersection[i].turn.angle += correction_factor; + intersection[i].turn.angle -= correction_factor; intersection[0] = merge(intersection[0], intersection[1]); intersection[0].turn.angle = 0; intersection.erase(intersection.begin() + 1); diff --git a/src/extractor/guidance/turn_lane_data.cpp b/src/extractor/guidance/turn_lane_data.cpp index f79f065..84a1c4f 100644 --- a/src/extractor/guidance/turn_lane_data.cpp +++ b/src/extractor/guidance/turn_lane_data.cpp @@ -38,6 +38,28 @@ bool TurnLaneData::operator<(const TurnLaneData &other) const TurnLaneType::left, TurnLaneType::sharp_left, TurnLaneType::uturn}; + // U-Turns are supposed to be on the outside. So if the first lane is 0 and we are looking at a + // u-turn, it has to be on the very left. If it is equal to the number of lanes, it has to be on + // the right. These sorting function assume reverse to be on the outside always. Might need to + // be reconsidered if there are situations that offer a reverse from some middle lane (seems + // improbable) + + if (tag == TurnLaneType::uturn) + { + if (from == 0) + return true; + else + return false; + } + + if (other.tag == TurnLaneType::uturn) + { + if (other.from == 0) + return false; + else + return true; + } + return std::find(tag_by_modifier, tag_by_modifier + 8, this->tag) < std::find(tag_by_modifier, tag_by_modifier + 8, other.tag); } diff --git a/src/extractor/guidance/turn_lane_handler.cpp b/src/extractor/guidance/turn_lane_handler.cpp index 076750b..cf68e91 100644 --- a/src/extractor/guidance/turn_lane_handler.cpp +++ b/src/extractor/guidance/turn_lane_handler.cpp @@ -118,9 +118,8 @@ Intersection TurnLaneHandler::assignTurnLanes(const NodeID at, if (!lane_data.empty() && canMatchTrivially(intersection, lane_data) && lane_data.size() != - static_cast<std::size_t>( - lane_data.back().tag != TurnLaneType::uturn && intersection[0].entry_allowed ? 1 - : 0) + + static_cast<std::size_t>(( + !hasTag(TurnLaneType::uturn, lane_data) && intersection[0].entry_allowed ? 1 : 0)) + possible_entries && intersection[0].entry_allowed && !hasTag(TurnLaneType::none, lane_data)) lane_data.push_back({TurnLaneType::uturn, lane_data.back().to, lane_data.back().to}); @@ -351,14 +350,8 @@ bool TurnLaneHandler::isSimpleIntersection(const LaneDataVector &lane_data, if (lane_data.back().tag == TurnLaneType::uturn) return findBestMatchForReverse(lane_data[lane_data.size() - 2].tag, intersection); - // TODO(mokob): #2730 have a look please - // BOOST_ASSERT(lane_data.front().tag == TurnLaneType::uturn); - // return findBestMatchForReverse(lane_data[1].tag, intersection); - // - if (lane_data.front().tag == TurnLaneType::uturn) - return findBestMatchForReverse(lane_data[1].tag, intersection); - - return findBestMatch(data.tag, intersection); + BOOST_ASSERT(lane_data.front().tag == TurnLaneType::uturn); + return findBestMatchForReverse(lane_data[1].tag, intersection); }(); std::size_t match_index = std::distance(intersection.begin(), best_match); all_simple &= (matched_indices.count(match_index) == 0); diff --git a/src/extractor/guidance/turn_lane_matcher.cpp b/src/extractor/guidance/turn_lane_matcher.cpp index 7b0d413..c89bd23 100644 --- a/src/extractor/guidance/turn_lane_matcher.cpp +++ b/src/extractor/guidance/turn_lane_matcher.cpp @@ -134,17 +134,17 @@ typename Intersection::const_iterator findBestMatch(const TurnLaneType::Mask &ta // possible that it is forbidden. In addition, the best u-turn angle does not necessarily represent // the u-turn, since it could be a sharp-left turn instead on a road with a middle island. typename Intersection::const_iterator -findBestMatchForReverse(const TurnLaneType::Mask &leftmost_tag, const Intersection &intersection) +findBestMatchForReverse(const TurnLaneType::Mask &neighbor_tag, const Intersection &intersection) { - const auto leftmost_itr = findBestMatch(leftmost_tag, intersection); - if (leftmost_itr + 1 == intersection.cend()) + const auto neighbor_itr = findBestMatch(neighbor_tag, intersection); + if ((neighbor_itr + 1 == intersection.cend()) || (neighbor_itr == intersection.cbegin() + 1)) return intersection.begin(); const constexpr double idealized_turn_angles[] = {0, 35, 90, 135, 180, 225, 270, 315}; const TurnLaneType::Mask tag = TurnLaneType::uturn; const auto idealized_angle = idealized_turn_angles[getMatchingModifier(tag)]; return std::min_element( - intersection.begin() + std::distance(intersection.begin(), leftmost_itr), + intersection.begin() + std::distance(intersection.begin(), neighbor_itr), intersection.end(), [idealized_angle, &tag](const ConnectedRoad &lhs, const ConnectedRoad &rhs) { // prefer valid matches @@ -165,6 +165,12 @@ findBestMatchForReverse(const TurnLaneType::Mask &leftmost_tag, const Intersecti bool canMatchTrivially(const Intersection &intersection, const LaneDataVector &lane_data) { std::size_t road_index = 1, lane = 0; + if (!lane_data.empty() && lane_data.front().tag == TurnLaneType::uturn) + { + // the very first is a u-turn to the right + if (intersection[0].entry_allowed) + lane = 1; + } for (; road_index < intersection.size() && lane < lane_data.size(); ++road_index) { if (intersection[road_index].entry_allowed) @@ -207,6 +213,34 @@ Intersection triviallyMatchLanesToTurns(Intersection intersection, road.turn.lane_data_id = lane_data_id; }; + if (!lane_data.empty() && lane_data.front().tag == TurnLaneType::uturn) + { + // the very first is a u-turn to the right + if (intersection[0].entry_allowed) + { + std::size_t u_turn = 0; + if (node_based_graph.GetEdgeData(intersection[0].turn.eid).reversed) + { + if (intersection.size() <= 1 || !intersection[1].entry_allowed || + intersection[1].turn.instruction.direction_modifier != + DirectionModifier::SharpRight) + { + // cannot match u-turn in a valid way + return intersection; + } + u_turn = 1; + road_index = 2; + } + intersection[u_turn].entry_allowed = true; + intersection[u_turn].turn.instruction.type = TurnType::Turn; + intersection[u_turn].turn.instruction.direction_modifier = DirectionModifier::UTurn; + + matchRoad(intersection[u_turn], lane_data.back()); + // continue with the first lane + lane = 1; + } + } + for (; road_index < intersection.size() && lane < lane_data.size(); ++road_index) { if (intersection[road_index].entry_allowed) @@ -231,7 +265,7 @@ Intersection triviallyMatchLanesToTurns(Intersection intersection, std::size_t u_turn = 0; if (node_based_graph.GetEdgeData(intersection[0].turn.eid).reversed) { - if (intersection.back().entry_allowed || + if (!intersection.back().entry_allowed || intersection.back().turn.instruction.direction_modifier != DirectionModifier::SharpLeft) { -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/osrm.git _______________________________________________ Pkg-grass-devel mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel
