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 headings and correlated lat/lon to verbose matrix output #5072

Open
wants to merge 7 commits into
base: master
Choose a base branch
from
Open
Show file tree
Hide file tree
Changes from 3 commits
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
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -25,6 +25,7 @@
* ADDED: per level elevator penalty [#4973](https://github.com/valhalla/valhalla/pull/4973)
* ADDED: `ignore_construction` allows routing on ways with construction tag [#5030](https://github.com/valhalla/valhalla/pull/5030)
* ADDED: Australian English language translations [#5057](https://github.com/valhalla/valhalla/pull/5057)
* ADDED: headings and correlated ll's in verbose matrix output [#5072](https://github.com/valhalla/valhalla/pull/5072)

## Release Date: 2024-10-10 Valhalla 3.5.1
* **Removed**
Expand Down
2 changes: 1 addition & 1 deletion docs/docs/api/matrix/api-reference.md
Original file line number Diff line number Diff line change
Expand Up @@ -93,7 +93,7 @@ The following parameters are only present in `"verbose": true` mode:
| :---- | :----------- |
| `sources` | The sources passed to the request. |
| `targets` | The targets passed to the request. |
| `sources_to_targets` | An array of time and distance between the sources and the targets.<br>The array is <b>row-ordered</b>, meaning the time and distance from the first location to all others forms the first row of the array, followed by the time and distance from the second source location to all target locations, etc.<br>The Object contained in the arrays contains the following fields:<ul><li><code>distance</code>: The computed distance between each set of points. Distance will always be 0.00 for the first element of the time-distance array for <code>one_to_many</code>, the last element in a <code>many_to_one</code>, and the first and last elements of a <code>many_to_many</code>.</li><li><code>time</code>: The computed time between each set of points. Time will always be 0 for the first element of the time-distance array for <code>one_to_many</code>, the last element in a <code>many_to_one</code>, and the first and last elements of a <code>many_to_many</code>.</li><li><code>to_index</code>: The destination index into the locations array.</li><li><code>from_index</code>: The origin index into the locations array.</li><li><code>date_time</code>: When a user will arrive at/depart from this location. See <a href="#time-dependent-matrices">the part above</a> where we explain how time dependent matices work for further context.<br> Note: If the time is above the setting <code>max_timedep_distance_matrix</code> this is skipped.<br>Note: If the departure/arrival time is unspecified it is not computed.</li><li><code>time_zone_offset</code>, <code>time_zone_name</code>: time zone at the target location. See <a href="#time-dependent-matrices">here</a> on requesting time dependent matrices. Note: this is skipped if the time is greater than <code>max_timedep_distance_matrix</code> or no route was found for the location pair.</li></ul> |
| `sources_to_targets` | An array of time and distance between the sources and the targets.<br>The array is <b>row-ordered</b>, meaning the time and distance from the first location to all others forms the first row of the array, followed by the time and distance from the second source location to all target locations, etc.<br>The Object contained in the arrays contains the following fields:<ul><li><code>distance</code>: The computed distance between each set of points. Distance will always be 0.00 for the first element of the time-distance array for <code>one_to_many</code>, the last element in a <code>many_to_one</code>, and the first and last elements of a <code>many_to_many</code>.</li><li><code>time</code>: The computed time between each set of points. Time will always be 0 for the first element of the time-distance array for <code>one_to_many</code>, the last element in a <code>many_to_one</code>, and the first and last elements of a <code>many_to_many</code>.</li><li><code>to_index</code>: The destination index into the locations array.</li><li><code>from_index</code>: The origin index into the locations array.</li><li><code>date_time</code>: When a user will arrive at/depart from this location. See <a href="#time-dependent-matrices">the part above</a> where we explain how time dependent matices work for further context.<br> Note: If the time is above the setting <code>max_timedep_distance_matrix</code> this is skipped.<br>Note: If the departure/arrival time is unspecified it is not computed.</li><li><code>time_zone_offset</code>, <code>time_zone_name</code>: time zone at the target location. See <a href="#time-dependent-matrices">here</a> on requesting time dependent matrices. Note: this is skipped if the time is greater than <code>max_timedep_distance_matrix</code> or no route was found for the location pair.</li><li>`begin_heading` **beta**: the heading at the beginning of path in degrees</li><li>`end_heading` **beta**: the heading at the end of the path in degrees</li><li>`begin_lat` **beta**: the latitude of the correlated source location for this connection</li><li>`begin_lon` **beta**: the longitude of the correlated source location for this connection</li><li>`begin_lat` **beta**: the latitude of the correlated target location for this connection</li><li>`begin_lon` **beta**: the longitude of the correlated target location for this connection</li></ul> |

### Concise mode (`"verbose": false`)

Expand Down
6 changes: 6 additions & 0 deletions proto/matrix.proto
Original file line number Diff line number Diff line change
Expand Up @@ -20,4 +20,10 @@ message Matrix {
repeated string time_zone_offsets = 9;
repeated string time_zone_names = 10;
repeated bool second_pass = 11;
repeated float begin_heading = 12;
repeated float end_heading = 13;
repeated double begin_lat = 14;
repeated double begin_lon = 15;
repeated double end_lat = 16;
repeated double end_lon = 17;
}
182 changes: 108 additions & 74 deletions src/thor/costmatrix.cc
Original file line number Diff line number Diff line change
Expand Up @@ -242,7 +242,7 @@

// resize/reserve all properties of Matrix on first pass only
valhalla::Matrix& matrix = *request.mutable_matrix();
reserve_pbf_arrays(matrix, best_connection_.size(), costing_->pass());
reserve_pbf_arrays(matrix, best_connection_.size(), request.options().verbose(), costing_->pass());
Copy link
Member Author

Choose a reason for hiding this comment

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

only reserve space for the new information when we know we will need it


// Form the matrix PBF output
graph_tile_ptr tile;
Expand All @@ -256,10 +256,105 @@
uint32_t target_idx = connection_idx % target_location_list.size();
uint32_t source_idx = connection_idx / target_location_list.size();

// first recost and form the path, if desired (either time and/or geometry requested)
const auto shape = RecostFormPath(graphreader, best_connection, source_location_list[source_idx],
target_location_list[target_idx], source_idx, target_idx,
time_infos[source_idx], invariant, shape_format);
std::string shape;
Copy link
Member Author

@chrstnbwnkl chrstnbwnkl Jan 27, 2025

Choose a reason for hiding this comment

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

small change, large diff: I pulled the path construction out of RecostFormPath (now that I spell it out, maybe this should be renamed to something like RecostFormShape), because we may need it for the headings and correlated lat/lon's. I figured this was better than the alternative, which would require passing a lot more args to the method, and making it do things beyond its original scope (i.e. forming part of the response).

Copy link
Member

Choose a reason for hiding this comment

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

what if we kept this stuff down in FormPath but maybe we rename it to somethign else? Im actually ok with it still being named FormPath really, its the stuff you have to do after you do the expansion to make use of the paths that were found. in the case of other routing algorithms we just return the path itself (edgeids) but for matrix we are pretty much done so doing a bit of "serialization" is ok too. seems like we can just send the request API object to this method and modify it there to save on arguments to the method.

Copy link
Member Author

Choose a reason for hiding this comment

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

I ended up doing what you suggested: leave the name as is and just change the signature of RecostFormPath to include the request so that we can set those new fields directly in there.


// walk the path if (a) it's a time dependent request, (b) the user requested shapes or
// (c) the user requested verbose mode
if ((has_time_ || shape_format != no_shape || request.options().verbose()) &&
best_connection.cost.secs != 0.f && best_connection.distance != kMaxCost) {
// walk the path
// Get the indices where the connection occurs.
uint32_t connedge_idx1 =
edgestatus_[MATRIX_FORW][source_idx].Get(best_connection.edgeid).index();
uint32_t connedge_idx2 =
edgestatus_[MATRIX_REV][target_idx].Get(best_connection.opp_edgeid).index();

// set of edges recovered from shortcuts (excluding shortcut's start edges)
std::unordered_set<GraphId> recovered_inner_edges;

// A place to keep the path
std::vector<GraphId> path_edges;

// Work backwards on the forward path
graph_tile_ptr tile;
for (auto edgelabel_index = connedge_idx1; edgelabel_index != kInvalidLabel;
edgelabel_index = edgelabel_[MATRIX_FORW][source_idx][edgelabel_index].predecessor()) {
const BDEdgeLabel& edgelabel = edgelabel_[MATRIX_FORW][source_idx][edgelabel_index];

const DirectedEdge* edge = graphreader.directededge(edgelabel.edgeid(), tile);
if (edge == nullptr) {
throw tile_gone_error_t("CostMatrix::RecostPaths failed", edgelabel.edgeid());

Check warning on line 286 in src/thor/costmatrix.cc

View check run for this annotation

Codecov / codecov/patch

src/thor/costmatrix.cc#L286

Added line #L286 was not covered by tests
}

if (edge->is_shortcut()) {
auto superseded = graphreader.RecoverShortcut(edgelabel.edgeid());
recovered_inner_edges.insert(superseded.begin() + 1, superseded.end());
std::move(superseded.rbegin(), superseded.rend(), std::back_inserter(path_edges));
} else

Check warning on line 293 in src/thor/costmatrix.cc

View check run for this annotation

Codecov / codecov/patch

src/thor/costmatrix.cc#L290-L293

Added lines #L290 - L293 were not covered by tests
path_edges.push_back(edgelabel.edgeid());
}

// Reverse the list
std::reverse(path_edges.begin(), path_edges.end());

// Append the reverse path from the destination - use opposing edges
// The first edge on the reverse path is the same as the last on the forward
// path, so get the predecessor.
auto& target_edgelabels = edgelabel_[MATRIX_REV][target_idx];
for (auto edgelabel_index = target_edgelabels[connedge_idx2].predecessor();
edgelabel_index != kInvalidLabel;
edgelabel_index = target_edgelabels[edgelabel_index].predecessor()) {
const BDEdgeLabel& edgelabel = target_edgelabels[edgelabel_index];
const DirectedEdge* opp_edge = nullptr;
GraphId opp_edge_id = graphreader.GetOpposingEdgeId(edgelabel.edgeid(), opp_edge, tile);
if (opp_edge == nullptr) {
throw tile_gone_error_t("CostMatrix::RecostPaths failed", edgelabel.edgeid());

Check warning on line 311 in src/thor/costmatrix.cc

View check run for this annotation

Codecov / codecov/patch

src/thor/costmatrix.cc#L311

Added line #L311 was not covered by tests
}

if (opp_edge->is_shortcut()) {
auto superseded = graphreader.RecoverShortcut(opp_edge_id);
recovered_inner_edges.insert(superseded.begin() + 1, superseded.end());
std::move(superseded.begin(), superseded.end(), std::back_inserter(path_edges));
} else

Check warning on line 318 in src/thor/costmatrix.cc

View check run for this annotation

Codecov / codecov/patch

src/thor/costmatrix.cc#L315-L318

Added lines #L315 - L318 were not covered by tests
path_edges.emplace_back(std::move(opp_edge_id));
}

const auto& source_edge =
find_correlated_edge(source_location_list[source_idx], path_edges.front());
const auto& target_edge =
find_correlated_edge(target_location_list[target_idx], path_edges.back());
float source_pct = static_cast<float>(source_edge.percent_along());
float target_pct = static_cast<float>(target_edge.percent_along());

if (request.options().verbose()) {
matrix.mutable_begin_lat()->Set(connection_idx, source_edge.ll().lat());
matrix.mutable_begin_lon()->Set(connection_idx, source_edge.ll().lng());
matrix.mutable_end_lat()->Set(connection_idx, source_edge.ll().lat());
matrix.mutable_end_lon()->Set(connection_idx, source_edge.ll().lng());

// get begin/end heading using the path's begin/end edge shapes
const DirectedEdge* start_edge =
graphreader.directededge(static_cast<GraphId>(source_edge.graph_id()), tile);
std::vector<PointLL> shp = tile->edgeinfo(start_edge).shape();
if (!start_edge->forward())
std::reverse(shp.begin(), shp.end());
matrix.mutable_begin_heading()->Set(connection_idx,
PointLL::HeadingAlongPolyline(shp, start_edge->length() *
source_pct));
const DirectedEdge* end_edge =
graphreader.directededge(static_cast<GraphId>(target_edge.graph_id()), tile);
shp = tile->edgeinfo(end_edge).shape();
if (!end_edge->forward())
std::reverse(shp.begin(), shp.end());
matrix.mutable_end_heading()->Set(connection_idx,
PointLL::HeadingAlongPolyline(shp, end_edge->length() *
target_pct));
}

shape =
RecostFormPath(graphreader, best_connection, time_infos[source_idx], invariant,
shape_format, path_edges, source_edge, target_edge, source_pct, target_pct);
}

float time = best_connection.cost.secs;
if (time < kMaxCost && request.options().verbose()) {
Expand All @@ -282,6 +377,7 @@
matrix.mutable_second_pass()->Set(connection_idx, true);
connection_failed = true;
}

matrix.mutable_from_indices()->Set(connection_idx, source_idx);
matrix.mutable_to_indices()->Set(connection_idx, target_idx);
matrix.mutable_distances()->Set(connection_idx, best_connection.distance);
Expand Down Expand Up @@ -1190,77 +1286,14 @@
// Form the path from the edfge labels and optionally return the shape
std::string CostMatrix::RecostFormPath(GraphReader& graphreader,
BestCandidate& connection,
const valhalla::Location& source,
const valhalla::Location& target,
const uint32_t source_idx,
const uint32_t target_idx,
const baldr::TimeInfo& time_info,
const bool invariant,
const ShapeFormat shape_format) {
// no need to look at source == target or missing connectivity
if ((!has_time_ && shape_format == no_shape) || connection.cost.secs == 0.f ||
connection.distance == kMaxCost) {
return "";
}

// Get the indices where the connection occurs.
uint32_t connedge_idx1 = edgestatus_[MATRIX_FORW][source_idx].Get(connection.edgeid).index();
uint32_t connedge_idx2 = edgestatus_[MATRIX_REV][target_idx].Get(connection.opp_edgeid).index();

// set of edges recovered from shortcuts (excluding shortcut's start edges)
std::unordered_set<GraphId> recovered_inner_edges;

// A place to keep the path
std::vector<GraphId> path_edges;

// Work backwards on the forward path
graph_tile_ptr tile;
for (auto edgelabel_index = connedge_idx1; edgelabel_index != kInvalidLabel;
edgelabel_index = edgelabel_[MATRIX_FORW][source_idx][edgelabel_index].predecessor()) {
const BDEdgeLabel& edgelabel = edgelabel_[MATRIX_FORW][source_idx][edgelabel_index];

const DirectedEdge* edge = graphreader.directededge(edgelabel.edgeid(), tile);
if (edge == nullptr) {
throw tile_gone_error_t("CostMatrix::RecostPaths failed", edgelabel.edgeid());
}

if (edge->is_shortcut()) {
auto superseded = graphreader.RecoverShortcut(edgelabel.edgeid());
recovered_inner_edges.insert(superseded.begin() + 1, superseded.end());
std::move(superseded.rbegin(), superseded.rend(), std::back_inserter(path_edges));
} else
path_edges.push_back(edgelabel.edgeid());
}

// Reverse the list
std::reverse(path_edges.begin(), path_edges.end());

// Append the reverse path from the destination - use opposing edges
// The first edge on the reverse path is the same as the last on the forward
// path, so get the predecessor.
auto& target_edgelabels = edgelabel_[MATRIX_REV][target_idx];
for (auto edgelabel_index = target_edgelabels[connedge_idx2].predecessor();
edgelabel_index != kInvalidLabel;
edgelabel_index = target_edgelabels[edgelabel_index].predecessor()) {
const BDEdgeLabel& edgelabel = target_edgelabels[edgelabel_index];
const DirectedEdge* opp_edge = nullptr;
GraphId opp_edge_id = graphreader.GetOpposingEdgeId(edgelabel.edgeid(), opp_edge, tile);
if (opp_edge == nullptr) {
throw tile_gone_error_t("CostMatrix::RecostPaths failed", edgelabel.edgeid());
}

if (opp_edge->is_shortcut()) {
auto superseded = graphreader.RecoverShortcut(opp_edge_id);
recovered_inner_edges.insert(superseded.begin() + 1, superseded.end());
std::move(superseded.begin(), superseded.end(), std::back_inserter(path_edges));
} else
path_edges.emplace_back(std::move(opp_edge_id));
}

const auto& source_edge = find_correlated_edge(source, path_edges.front());
const auto& target_edge = find_correlated_edge(target, path_edges.back());
float source_pct = static_cast<float>(source_edge.percent_along());
float target_pct = static_cast<float>(target_edge.percent_along());
const ShapeFormat shape_format,
Copy link
Member Author

Choose a reason for hiding this comment

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

simplified signature

const std::vector<GraphId>& path_edges,
const PathEdge& source_edge,
const PathEdge& target_edge,
const double source_pct,
const double target_pct) {

// recost the path if this was a time-dependent expansion
if (has_time_) {
Expand Down Expand Up @@ -1297,6 +1330,7 @@
auto is_first_edge = i == 0;
auto is_last_edge = i == (path_edges.size() - 1);

graph_tile_ptr tile;
Copy link
Member Author

Choose a reason for hiding this comment

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

previously this reused the tile pointer used for forming the path.

const auto* de = graphreader.directededge(path_edge, tile);
auto edge_shp = tile->edgeinfo(de).shape();

Expand Down
4 changes: 3 additions & 1 deletion src/thor/timedistancebssmatrix.cc
Original file line number Diff line number Diff line change
Expand Up @@ -181,8 +181,10 @@ bool TimeDistanceBSSMatrix::ComputeMatrix(Api& request,

// Initialize destinations once for all origins
InitDestinations<expansion_direction>(graphreader, destinations);

// reserve the PBF vectors
reserve_pbf_arrays(*request.mutable_matrix(), origins.size() * destinations.size());
reserve_pbf_arrays(*request.mutable_matrix(), origins.size() * destinations.size(),
request.options().verbose());

for (int origin_index = 0; origin_index < origins.size(); ++origin_index) {
edgelabels_.reserve(max_reserved_labels_count_);
Expand Down
3 changes: 2 additions & 1 deletion src/thor/timedistancematrix.cc
Original file line number Diff line number Diff line change
Expand Up @@ -205,7 +205,8 @@ bool TimeDistanceMatrix::ComputeMatrix(Api& request,
// Initialize destinations once for all origins
InitDestinations<expansion_direction>(graphreader, destinations);
// reserve the PBF vectors
reserve_pbf_arrays(*request.mutable_matrix(), num_elements, costing_->pass());
reserve_pbf_arrays(*request.mutable_matrix(), num_elements, request.options().verbose(),
costing_->pass());

for (int origin_index = 0; origin_index < origins.size(); ++origin_index) {
// reserve some space for the next dijkstras (will be cleared at the end of the loop)
Expand Down
25 changes: 25 additions & 0 deletions src/tyr/matrix_serializer.cc
Original file line number Diff line number Diff line change
Expand Up @@ -139,6 +139,12 @@ json::ArrayPtr serialize_row(const valhalla::Matrix& matrix,
const auto& date_time = matrix.date_times()[i];
const auto& time_zone_offset = matrix.time_zone_offsets()[i];
const auto& time_zone_name = matrix.time_zone_names()[i];
const auto& begin_lat = matrix.begin_lat()[i];
const auto& begin_lon = matrix.begin_lon()[i];
const auto& end_lat = matrix.end_lat()[i];
const auto& end_lon = matrix.end_lon()[i];
const auto& begin_heading = matrix.begin_heading()[i];
const auto& end_heading = matrix.end_heading()[i];
if (time != kMaxCost) {
map = json::map({{"from_index", static_cast<uint64_t>(source_index)},
{"to_index", static_cast<uint64_t>(target_index + (i - start_td))},
Expand All @@ -156,6 +162,25 @@ json::ArrayPtr serialize_row(const valhalla::Matrix& matrix,
map->emplace("time_zone_name", time_zone_name);
}

if (begin_heading != kInvalidHeading) {
map->emplace("begin_heading", json::fixed_t{begin_heading, 0});
}

if (end_heading != kInvalidHeading) {
map->emplace("end_heading", json::fixed_t{end_heading, 0});
}
if (begin_lat != INVALID_LL) {
map->emplace("begin_lat", json::fixed_t{begin_lat, 6});
}
if (begin_lon != INVALID_LL) {
map->emplace("begin_lon", json::fixed_t{begin_lon, 6});
}
if (end_lat != INVALID_LL) {
map->emplace("end_lat", json::fixed_t{end_lat, 6});
}
if (end_lon != INVALID_LL) {
map->emplace("end_lon", json::fixed_t{end_lon, 6});
}
if (matrix.shapes().size() && shape_format != no_shape) {
// TODO(nils): tdmatrices don't have "shape" support yet
if (!matrix.shapes()[i].empty()) {
Expand Down
Loading
Loading