Fixing edge connectivity for OSM ways with differing layer tag values #220

MikeGost · 2018-09-19T05:03:02Z

Description:

In the existing implementation, we would only way-section two ways if they had the same layer tag value. However, this ignored a very common OSM use-case where two ways could be connected, but have two distinct layer tag values. As an example, imagine a trunk-link of layer 0 linking a trunk road of layer 1 to another road of layer 0 - a very common case for most on/off ramps. This PR updates the way-sectioning logic to allow sectioning if two ways have different layer tag values, as long as the intersection is at the end point of one of the ways. This is a clear distinction, to avoid sectioning anything that is intersecting at a non-endpoint, since this is often times a mapping error. As an example, imagine an overpass road of layer 1 sharing a shape point with an underlying residential road of layer 0. If we way-section at a non-end point, we would end up connecting these two, when in reality there is no way to drive from the overpass to the residential road beneath it. It's worth calling out - that the existing logic may still have some corner cases that exist. However, these changes align the Atlas more closely with the OSM data model.

Potential Impact:

This will have an impact on any consumer of the atlas with the changes. Specifically, the proper connectivity is now ensured with ways that are connected at endpoints and having different layer tag values.

Unit Test Approach:

Added 2 new unit tests and renamed an existing one to capture behavior more accurately. The test suite is now comprised of three cases where two ways with different layer tag values are intersecting. The intersections occur at the beginning, middle and end of the way. When the intersection happens at the start or end of the way, the proper connectivity is ensured. Whereas, if the intersection is during a non-end point between the two ways of different layer tag values, then we ensure they are not connected. The two unit tests both fail without the changes and pass afterwards. Below are the screenshots of the behavior the unit tests are testing:

Intersection at start of the way:

Intersection at end (and also at the end) of the way:

Test Results:

Ran the changes on a shard that contains such intersections and visually verified correct stitching and connectivity.

In doubt: Contributing Guidelines

jklamer

Looks good! Nice unit testing.

jklamer · 2018-09-19T05:12:16Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

                    if (locationIsPartOfAnIntersectingEdgeOfTheSameLayer(shapePoint, line))
                    {
                        addPointToNodeList(shapePoint, nodesForEdge);
                    }
+
+                    // 4. Check if there is an intersecting edge, of a different layer at this


nit: In the comment I believe this is described as case 3b?

Good point, I'll update the comment to reflect the 3b

jklamer · 2018-09-19T05:18:29Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+                // Find all intersecting edges
+                .stream(this.rawAtlas.linesContaining(location,
+                        target -> target.getIdentifier() != line.getIdentifier()
+                                && isAtlasEdge(target) && target.asPolyLine().contains(location)))


does this.rawAtlas.lineContaining() also return lines where the location isn't a shape point but just somewhere along a segment?

It only looks at the shape points. But @MikeGost can correct me here, I think location is only a start/end point, so it should match with a shape point, right?

@matthieun is correct, the lineContaining() call only looks at the underlying PolyLine shape points. The location is the intersection location - I will rename it to make that more clear. And then in the anyMatch block, we make sure that the intersection happens at the start/end point only, not somewhere in between.

Correction, the location is just a shape point, with a possible intersection that we are checking for.

jklamer · 2018-09-19T05:19:55Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+        return Iterables
+                // Find all intersecting edges
+                .stream(this.rawAtlas.linesContaining(location,
+                        target -> target.getIdentifier() != line.getIdentifier()


do you have to worry about the reverse edge here or are these line just the OSM ways navigable or not?

This way-sectioning phase works on a "raw" atlas that only contains lines, points and relations. This step is what determines what becomes an edge and a line, and that creates the reverse edges. At that point, there are no reverse edges yet.

That's correct - no need to worry about reverse edges here. We only see Lines, that will become Edges, at this point and are trying to establish all Node locations. Once we have that, we will section this Line to create forward and reverse Edges, as needed, based on the tagging.

jklamer · 2018-09-19T05:24:07Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+                    final PolyLine candidatePolyline = candidate.asPolyLine();
+                    final boolean intersectionIsAtEndPoint = candidatePolyline.first()
+                            .equals(location) || candidatePolyline.last().equals(location);
+                    return edgesOnDifferentLayers && intersectionIsAtEndPoint;


Not sure if you're trying to absolutely squeeze performance here, but if you want to avoid doing

final boolean intersectionIsAtEndPoint = candidatePolyline.first() .equals(location) || candidatePolyline.last().equals(location);

unless necessary you can squeeze it into

return edgesOnDifferentLayers && (candidatePolyline.first() .equals(location) || candidatePolyline.last().equals(location));

Good point, I actually had that at first, and then changed it back to the current version for readability. It probably makes sense to change it back. Thanks for the catch!

This is true, but worst case (assuming the compiler does not do final variable optimizations) it's only 2 extra byte code instructions (an istore_ and an iload_ for the intersectionIsAtEndPoint variable).

I think having the name of what that predicate represents (intersectionIsAtEndPoint) is useful for readability - especially if someone else needs to dig back into the code in the future.

I'll change it back!

Code tennis! :)

matthieun

Nice fix @MikeGost! Would be nice to test on some shards to make sure it does not introduce new hotspots (if not done already)

matthieun · 2018-09-19T13:10:48Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+        return Iterables
+                // Find all intersecting edges
+                .stream(this.rawAtlas.linesContaining(location,
+                        target -> target.getIdentifier() != line.getIdentifier()


This way-sectioning phase works on a "raw" atlas that only contains lines, points and relations. This step is what determines what becomes an edge and a line, and that creates the reverse edges. At that point, there are no reverse edges yet.

matthieun · 2018-09-19T13:13:04Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+                // Find all intersecting edges
+                .stream(this.rawAtlas.linesContaining(location,
+                        target -> target.getIdentifier() != line.getIdentifier()
+                                && isAtlasEdge(target) && target.asPolyLine().contains(location)))


It only looks at the shape points. But @MikeGost can correct me here, I think location is only a start/end point, so it should match with a shape point, right?

MikeGost · 2018-09-19T16:30:31Z

Good point @matthieun - that was my plan for today :)

lucaspcram

Looks good to me @MikeGost , nice testing.

I had a slightly different opinion than you and @jklamer on one of the changes, but it's not that big a deal.

AlexHsieh22

a few minor suggestions, overall LGTM!

AlexHsieh22 · 2018-09-19T17:20:49Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+                {
+                    final long layerValue = LayerTag.getTaggedOrImpliedValue(candidate, 0L);
+                    final boolean edgesOnDifferentLayers = targetLayerValue != layerValue;
+                    final PolyLine candidatePolyline = candidate.asPolyLine();


not sure what the compiler will do in this case, but does it make sense to return early if edgesOnDifferentLyaers is false?

Gave this some thought during original implementation. I don't think the performance improvement would be that great, considering that the intersection logic is fairly trivial (two equality checks for Location class). My thought was to weight readability over minor performance. Will consider changing if I see this misbehaving on the cluster :)

AlexHsieh22 · 2018-09-19T17:24:55Z

src/main/java/org/openstreetmap/atlas/geography/atlas/raw/sectioning/WaySectionProcessor.java

+    {
+        final long targetLayerValue = LayerTag.getTaggedOrImpliedValue(line, 0L);
+
+        return Iterables


This code to return a stream of intersecting edges (or even a list) seems reusable. Thoughts on pulling it out into a helper function?

Same comment here. Going to keep as is for readability here.

Fixing edge connectivity for varying layer tags

69d259e

MikeGost added Bug Enhancement labels Sep 19, 2018

MikeGost requested review from matthieun and jklamer September 19, 2018 05:03

jklamer previously approved these changes Sep 19, 2018

View reviewed changes

matthieun previously approved these changes Sep 19, 2018

View reviewed changes

Consistent commenting and minor modification of return statement

5c463d5

MikeGost dismissed stale reviews from matthieun and jklamer via 5c463d5 September 19, 2018 16:31

lucaspcram previously approved these changes Sep 19, 2018

View reviewed changes

Changing back for readability - aka code tennis

dadb317

MikeGost dismissed lucaspcram’s stale review via dadb317 September 19, 2018 16:47

lucaspcram approved these changes Sep 19, 2018

View reviewed changes

AlexHsieh22 approved these changes Sep 19, 2018

View reviewed changes

matthieun approved these changes Sep 20, 2018

View reviewed changes

matthieun merged commit 2b343dc into osmlab:dev Sep 21, 2018

matthieun added this to the 5.1.13 milestone Oct 17, 2018

MikeGost deleted the subAtlas branch November 8, 2018 20:51

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fixing edge connectivity for OSM ways with differing layer tag values #220

Fixing edge connectivity for OSM ways with differing layer tag values #220

MikeGost commented Sep 19, 2018

jklamer left a comment

jklamer Sep 19, 2018

MikeGost Sep 19, 2018

jklamer Sep 19, 2018

matthieun Sep 19, 2018

MikeGost Sep 19, 2018 •

edited

Loading

MikeGost Sep 19, 2018

jklamer Sep 19, 2018

matthieun Sep 19, 2018

MikeGost Sep 19, 2018

jklamer Sep 19, 2018

MikeGost Sep 19, 2018

lucaspcram Sep 19, 2018 •

edited

Loading

MikeGost Sep 19, 2018

lucaspcram Sep 19, 2018

matthieun left a comment

matthieun Sep 19, 2018

matthieun Sep 19, 2018

MikeGost commented Sep 19, 2018

lucaspcram left a comment •

edited

Loading

AlexHsieh22 left a comment

AlexHsieh22 Sep 19, 2018

MikeGost Sep 19, 2018

AlexHsieh22 Sep 19, 2018

MikeGost Sep 19, 2018

Fixing edge connectivity for OSM ways with differing layer tag values #220

Fixing edge connectivity for OSM ways with differing layer tag values #220

Conversation

MikeGost commented Sep 19, 2018

Description:

Potential Impact:

Unit Test Approach:

Test Results:

Ran the changes on a shard that contains such intersections and visually verified correct stitching and connectivity.

jklamer left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

MikeGost Sep 19, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lucaspcram Sep 19, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

matthieun left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

MikeGost commented Sep 19, 2018

lucaspcram left a comment • edited Loading

Choose a reason for hiding this comment

AlexHsieh22 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

MikeGost Sep 19, 2018 •

edited

Loading

lucaspcram Sep 19, 2018 •

edited

Loading

lucaspcram left a comment •

edited

Loading