[osrm] 01/05: Imported Upstream version 5.3.3+ds
Bas Couwenberg
sebastic at debian.org
Wed Aug 31 11:12:50 UTC 2016
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 <sebastic at xs4all.nl>
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
More information about the Pkg-grass-devel
mailing list