Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add support for closure annotations #2816

Merged
merged 7 commits into from
Feb 23, 2021
Merged
Changes from 1 commit
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Add support for closure annotations
Adds a new shape attribute filter for getting closure locations in the
directions response. Similar to incidents, each closure annotation has
a start & end geometry index, which indexes into the coordinates list.
mandeepsandhu committed Feb 23, 2021
commit ace168d416393f3603dbbd20eab511d04e5b5fa2
6 changes: 6 additions & 0 deletions proto/trip.proto
Original file line number Diff line number Diff line change
@@ -319,6 +319,11 @@ message TripLeg {
optional uint32 end_shape_index = 4;
};

message Closure {
optional uint32 begin_shape_index = 1;
optional uint32 end_shape_index = 2;
};

optional uint64 osm_changeset = 1;
optional uint64 trip_id = 2;
optional uint32 leg_id = 3;
@@ -331,6 +336,7 @@ message TripLeg {
optional ShapeAttributes shape_attributes = 10;
repeated Incident incidents = 11;
repeated string algorithms = 12;
repeated Closure closures = 13;
}

message TripRoute {
1 change: 1 addition & 0 deletions src/thor/attributes_controller.cc
Original file line number Diff line number Diff line change
@@ -131,6 +131,7 @@ const std::unordered_map<std::string, bool> AttributesController::kDefaultAttrib
{kShapeAttributesLength, false},
{kShapeAttributesSpeed, false},
{kShapeAttributesSpeedLimit, false},
{kShapeAttributesClosure, false},
};

AttributesController::AttributesController() {
58 changes: 52 additions & 6 deletions src/thor/triplegbuilder.cc
Original file line number Diff line number Diff line change
@@ -125,6 +125,17 @@ void UpdateIncident(const std::shared_ptr<const valhalla::IncidentsTile>& incide
}
}

valhalla::TripLeg_Closure* fetch_last_closure_annotation(TripLeg& leg) {
return leg.closures_size() ? leg.mutable_closures(leg.closures_size() - 1) : nullptr;
}

valhalla::TripLeg_Closure* fetch_or_create_closure_annotation(TripLeg& leg) {
valhalla::TripLeg_Closure* closure = fetch_last_closure_annotation(leg);
// If last closure annotation has its end index populated, create a new
// closure annotation
return (!closure || closure->has_end_shape_index()) ? leg.add_closures() : closure;
}

/**
* Chops up the shape for an edge so that we have shape points where speeds change along the edge
* and where incidents occur along the edge. Also sets the various per shape point attributes
@@ -172,6 +183,7 @@ void SetShapeAttributes(const AttributesController& controller,
double speed; // meters per second
uint8_t congestion;
std::vector<const valhalla::IncidentsTile::Location*> incidents;
bool closed;
};

// A list of percent along the edge, corresponding speed (meters per second), incident id
@@ -187,23 +199,28 @@ void SetShapeAttributes(const AttributesController& controller,
cuts.emplace_back(cut_t{traffic_speed.breakpoint1 / 255.0,
speed,
static_cast<std::uint8_t>(traffic_speed.congestion1),
{}});
{},
traffic_speed.closed(0)});
if (traffic_speed.breakpoint2 > 0) {
cuts.emplace_back(cut_t{traffic_speed.breakpoint2 / 255.0,
speed,
static_cast<std::uint8_t>(traffic_speed.congestion2),
{}});
{},
traffic_speed.closed(1)});
if (traffic_speed.speed3 != UNKNOWN_TRAFFIC_SPEED_RAW) {
cuts.emplace_back(
cut_t{1, speed, static_cast<std::uint8_t>(traffic_speed.congestion3), {}});
cuts.emplace_back(cut_t{1,
speed,
static_cast<std::uint8_t>(traffic_speed.congestion3),
{},
traffic_speed.closed(2)});
}
}
}
}

// Cap the end so that we always have something to use
if (cuts.empty() || cuts.back().percent_along < tgt_pct) {
cuts.emplace_back(cut_t{tgt_pct, speed, UNKNOWN_CONGESTION_VAL, {}});
cuts.emplace_back(cut_t{tgt_pct, speed, UNKNOWN_CONGESTION_VAL, {}, false});
}

// sort the start and ends of the incidents along this edge
@@ -241,7 +258,8 @@ void SetShapeAttributes(const AttributesController& controller,
cuts.insert(itr, cut_t{offset,
itr == cuts.end() ? speed : itr->speed,
itr == cuts.end() ? UNKNOWN_CONGESTION_VAL : itr->congestion,
{&incident}});
{&incident},
itr == cuts.end() ? false : itr->closed});
}
}
}
@@ -289,6 +307,25 @@ void SetShapeAttributes(const AttributesController& controller,
distance *= coef;
shift = 1;
}
if (controller.attributes.at(kShapeAttributesClosure)) {
// Process closure annotations
if (cut_itr->closed) {
// Found a closure. Fetch a new annotation, or the last closure
// annotation if it does not have an end index set (meaning the shape
// is still within an existing closure)
::valhalla::TripLeg_Closure* closure = fetch_or_create_closure_annotation(leg);
if (!closure->has_begin_shape_index()) {
closure->set_begin_shape_index(i - 1);
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How come it's i - 1 and not just i?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since this loops starts from the 2nd shape index. It does that since we create cuts only if speed changes in subsequent shape segments.

}
} else {
// Not a closure, check if we need to set the end of an existing
// closure annotation or not
::valhalla::TripLeg_Closure* closure = fetch_last_closure_annotation(leg);
if (closure && !closure->has_end_shape_index()) {
closure->set_end_shape_index(i - 1);
}
}
}
distance_total_pct = next_total;
double time = distance / cut_itr->speed; // seconds

@@ -1413,6 +1450,15 @@ void TripLegBuilder::Build(
node->mutable_cost()->mutable_transition_cost()->set_cost(0);
}

if (controller.attributes.at(kShapeAttributesClosure)) {
// Set the end shape index if we're ending on a closure as the last index is
// not processed in SetShapeAttributes above
valhalla::TripLeg_Closure* closure = fetch_last_closure_annotation(trip_path);
if (closure && !closure->has_end_shape_index()) {
closure->set_end_shape_index(trip_shape.size() - 1);
}
}

// Assign the admins
AssignAdmins(controller, trip_path, admin_info_list);

18 changes: 18 additions & 0 deletions src/tyr/route_serializer_osrm.cc
Original file line number Diff line number Diff line change
@@ -773,6 +773,21 @@ void serializeIncidents(const google::protobuf::RepeatedPtrField<TripLeg::Incide
doc.emplace("incidents", serialized_incidents);
}

void serializeClosures(const valhalla::TripLeg& leg, json::Jmap& doc) {
if (!leg.closures_size()) {
return;
}
auto closures = json::array({});
closures->reserve(leg.closures_size());
for (const valhalla::TripLeg_Closure& closure : leg.closures()) {
auto closure_obj = json::map({});
closure_obj->emplace("geometry_index_start", static_cast<uint64_t>(closure.begin_shape_index()));
closure_obj->emplace("geometry_index_end", static_cast<uint64_t>(closure.end_shape_index()));
closures->emplace_back(std::move(closure_obj));
}
doc.emplace("closures", closures);
}

// Compile and return the refs of the specified list
// TODO we could enhance by limiting results by using consecutive count
std::string get_sign_element_refs(const google::protobuf::RepeatedPtrField<
@@ -1595,6 +1610,9 @@ json::ArrayPtr serialize_legs(const google::protobuf::RepeatedPtrField<valhalla:
// Add incidents to the leg
serializeIncidents(path_leg.incidents(), *output_leg);

// Add closures
serializeClosures(path_leg, *output_leg);

// Keep the leg
output_legs->emplace_back(std::move(output_leg));
leg++;
199 changes: 199 additions & 0 deletions test/gurka/test_closure_annotations.cc
Original file line number Diff line number Diff line change
@@ -0,0 +1,199 @@
#include "gurka.h"
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could we apply more compiler warnings to this file at https://github.com/valhalla/valhalla/blob/master/test/gurka/CMakeLists.txt#L14 ?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

totally! will add it

#include "test.h"

#include <boost/format.hpp>
#include <gtest/gtest.h>

using namespace valhalla;
using LiveTrafficCustomize = test::LiveTrafficCustomize;

namespace {

inline void
SetSubsegmentLiveSpeed(baldr::TrafficSpeed* live_speed, uint64_t speed, uint8_t subsegment) {
live_speed->breakpoint1 = subsegment;
live_speed->overall_speed = speed >> 1;
live_speed->speed1 = speed >> 1;
}

inline void SetLiveSpeed(baldr::TrafficSpeed* live_speed, uint64_t speed) {
SetSubsegmentLiveSpeed(live_speed, speed, 255);
}

void close_partial_dir_edge(baldr::GraphReader& reader,
baldr::TrafficTile& tile,
uint32_t index,
double percent_along,
baldr::TrafficSpeed* current,
const std::string& edge_name,
const std::string& start_node,
const gurka::map& map) {
baldr::GraphId tile_id(tile.header->tile_id);
auto edge = std::get<0>(gurka::findEdge(reader, map.nodes, edge_name, start_node));
if (edge.Tile_Base() == tile_id && edge.id() == index) {
SetSubsegmentLiveSpeed(current, 0, static_cast<uint8_t>(255 * percent_along));
}
}

void close_dir_edge(baldr::GraphReader& reader,
baldr::TrafficTile& tile,
uint32_t index,
baldr::TrafficSpeed* current,
const std::string& edge_name,
const std::string& start_node,
const gurka::map& map) {
close_partial_dir_edge(reader, tile, index, 1., current, edge_name, start_node, map);
}

void close_bidir_edge(baldr::GraphReader& reader,
baldr::TrafficTile& tile,
uint32_t index,
baldr::TrafficSpeed* current,
const std::string& edge_name,
const gurka::map& map) {
baldr::GraphId tile_id(tile.header->tile_id);
std::string start_node(1, edge_name.front());
std::string end_node(1, edge_name.back());

close_dir_edge(reader, tile, index, current, edge_name, start_node, map);
close_dir_edge(reader, tile, index, current, edge_name, end_node, map);
}

} // namespace

class ClosureAnnotations : public ::testing::Test {
protected:
static gurka::map closure_map;
static int const default_speed;
static std::string const tile_dir;
static std::shared_ptr<baldr::GraphReader> reader;

static void SetUpTestSuite() {
const std::string ascii_map = R"(

A-1----2-B
|
3
|
C
|
4
|
D-5----6-E
)";

const std::string speed_str = std::to_string(default_speed);
const gurka::ways ways = {{"AB", {{"highway", "primary"}, {"maxspeed", speed_str}}},
{"BC", {{"highway", "primary"}, {"maxspeed", speed_str}}},
{"CD", {{"highway", "primary"}, {"maxspeed", speed_str}}},
{"DE", {{"highway", "primary"}, {"maxspeed", speed_str}}}};

const auto layout = gurka::detail::map_to_coordinates(ascii_map, 100, {.05f, .2f});
closure_map = gurka::buildtiles(layout, ways, {}, {}, tile_dir);

closure_map.config.put("mjolnir.traffic_extract", tile_dir + "/traffic.tar");
test::build_live_traffic_data(closure_map.config);

reader = test::make_clean_graphreader(closure_map.config.get_child("mjolnir"));
}

void set_default_speed_on_all_edges() {
test::customize_live_traffic_data(closure_map.config,
[](baldr::GraphReader&, baldr::TrafficTile&, uint32_t,
baldr::TrafficSpeed* current) -> void {
SetLiveSpeed(current, default_speed);
});
}

virtual void SetUp() {
set_default_speed_on_all_edges();

// Partially(50%) close 12
test::customize_live_traffic_data(closure_map.config,
[](baldr::GraphReader& reader, baldr::TrafficTile& tile,
uint32_t index, baldr::TrafficSpeed* current) -> void {
// close_partial_dir_edge(reader, tile, index, 0.5, current,
// "AB", "B", closure_map);
close_partial_dir_edge(reader, tile, index, 0.5, current,
"AB", "A", closure_map);
});

#if 0
// Fully close BC
test::customize_live_traffic_data(closure_map.config,
[](baldr::GraphReader& reader, baldr::TrafficTile& tile,
uint32_t index, baldr::TrafficSpeed* current) -> void {
close_bidir_edge(reader, tile, index, current, "BC", closure_map);
});
// Partially(50%) close DE
test::customize_live_traffic_data(closure_map.config,
[](baldr::GraphReader& reader, baldr::TrafficTile& tile,
uint32_t index, baldr::TrafficSpeed* current) -> void {
close_partial_dir_edge(reader, tile, index, 0.5, current, "DE", "D", closure_map);
});
#endif
}

virtual void TearDown() {
set_default_speed_on_all_edges();
}
};

gurka::map ClosureAnnotations::closure_map = {};
const int ClosureAnnotations::default_speed = 36;
const std::string ClosureAnnotations::tile_dir = "test/data/closure_annotations";
std::shared_ptr<baldr::GraphReader> ClosureAnnotations::reader;

const std::string req_without_closure_annotations = R"({
"locations": [
{"lat": %s, "lon": %s},
{"lat": %s, "lon": %s}
],
"costing": "auto",
"costing_options": {
"auto": {
"speed_types": [ "freeflow", "constrained", "predicted", "current"],
"ignore_closures": true
}
},
"date_time": { "type": 3, "value": "current" },
"format": "osrm"
}
)";

const std::string req_with_closure_annotations = R"({
"locations": [
{"lat": %s, "lon": %s},
{"lat": %s, "lon": %s}
],
"costing": "auto",
"costing_options": {
"auto": {
"speed_types": [ "freeflow", "constrained", "predicted", "current"],
"ignore_closures": true
}
},
"date_time": { "type": 3, "value": "current" },
"format": "osrm",
"shape_format": "geojson",
"filters": {
"attributes": [
"shape_attributes.closure"
],
"action": "include"
}
}
)";

TEST_F(ClosureAnnotations, EndOnClosure) {
const std::string& req =
(boost::format(req_with_closure_annotations) % std::to_string(closure_map.nodes.at("1").lat()) %
std::to_string(closure_map.nodes.at("1").lng()) %
std::to_string(closure_map.nodes.at("2").lat()) %
std::to_string(closure_map.nodes.at("2").lng()))
.str();
auto result = gurka::do_action(Options::route, closure_map, req, reader);
gurka::assert::raw::expect_path(result, {"AB"});

// rapidjson::Document response = gurka::convert_to_json(result, valhalla::Options_Format_osrm);
}
1 change: 1 addition & 0 deletions valhalla/thor/attributes_controller.h
Original file line number Diff line number Diff line change
@@ -136,6 +136,7 @@ const std::string kShapeAttributesTime = "shape_attributes.time";
const std::string kShapeAttributesLength = "shape_attributes.length";
const std::string kShapeAttributesSpeed = "shape_attributes.speed";
const std::string kShapeAttributesSpeedLimit = "shape_attributes.speed_limit";
const std::string kShapeAttributesClosure = "shape_attributes.closure";

// Categories
const std::string kNodeCategory = "node.";