Combine way takes ages (I stopped after 7 minutes)

[stoecker]

Current SVN: 15542

With attached file joining the two ways takes extremely long (if it ever finish). Shorting the ways allowed joining (also with the overlap).

[GerdP]

Problem seems to be in org.openstreetmap.josm.data.osm.NodeGraph.buildSpanningPath()
Not sure why it is called in this situation.

[GerdP]

There is a comment in org.openstreetmap.josm.data.osm.NodeGraph.buildSpanningPath()
"In the worst case this loops over all nodes which is very slow for large ways."
Very true ;)
My first assumption was that CombineWayAction would simply add the nodes of one way to the nodes of the other, similar to the method that is used to calculate the rings of multipolygons.
Instead, it seems to search for "good" first point in the combined way. I am still trying to understand the reason for this,
the code is very old.

@Dirk: Do you think that the result with my simplified example is correct?

[GerdP]

corrected simplified sample, first version contained an artifact

[GerdP]

The problem with the existing algorithm is that it does a brute force search for the best node to start with when there is no "terminal node" like in a c-shaped or d-shaped way.
It starts with node 2684142672 and adds nodes in clockwise order until it detects a problem when it comes to node 176872704 for the 2nd time. This "problem detection" in buildSpanningPath() is a rather complex operation, I think it is at least O(n²) and it uses a synchronized Stack. Instead of starting a 2nd try with this problem node as start it uses the node 1740733337 and fails again at the same place after. This is done for thousands of nodes and each call takes very long as we have a O(n³) algo now.
I think it is obvious that we should start with a node that appears most often in the given edges when there is no "terminal node". The patch implements this.
The search for the start node is much faster than the problem detection. On my PC I see < 30 ms for the additional search and ~1500 to 3500 ms for the (single) call of buildSpanningPath() to compute the result.
Timings heavily depend on the order in which you select the ways before combining them and the JRE just-in-time-compiler.

BTW: Validator complains that the combined way is self-intersecting. I am unsure if this warning is correct or not.

[stoecker]

BTW: Validator complains that the combined way is self-intersecting. I am unsure if this warning is correct or not.

That's correct. The inner hole and the outer bounds are connected via an overlapping way (i.e. polygon with inner hole without multipolygon - very old style geometry, see #18367, that's how such things were drawn in the early days of OSM :-).

Leaving your fix aside: Why do we do such a complex algorithm at all? In the past we simply looked at the ends of the ways and joined them when two nodes are identical. That probably had issues when joining many ways, but in simple cases it was flawless.

My proposal (beside your fix) would be to reintroduce this for simply cases like only two ways. In maximum this are 4 node identity checks. This would also fix #18367.

[GerdP]

Replying to stoecker:

BTW: Validator complains that the combined way is self-intersecting. I am unsure if this warning is correct or not.

That's correct. The inner hole and the outer bounds are connected via an overlapping way

No, it is not. The resulting way has no overlapping segments.

[stoecker]

Well, then this is wrong. Combine Way action should not remove a section of the way. This is the task of other actions, but combine way only should combine ways.

[GerdP]

That was also my thought. So why do we have this poorly performing method buildSpanningPath()?

[stoecker]

No idea. Why/When was it introduced?

[GerdP]

A big change in r2070. I did not find an explanation why it was introduced, unless #3208 was the reason.

[GerdP]

In my eyes the methods in NodeGraph are simply a bad choice when we want to combine ways. Very confusing...

[GerdP]

I think the attached sample.osm explains why buildSpanningPath() was introduced. If we simply connect the two given ways we get two self-intersections. The implemented algo splits and reassembles the ways so that the result is not self-intersecting although validator says that it is.
This opens two questions:

• Should we keep this behaviour in CombineWayAction ?
• Why do we ignore p-shaped ways in SelfIntersectingWay but not B-shaped or 8-shaped ways?

[GerdP]

Oops, sorry, seems I was all wrong. The implemented algo doesn't prevent the self-intersections.
In SelfIntersectingWay we check this: "all nodes of a way must appear only once, only the first and/or last node are allowed to appear exactly two times". This allows closed ways and b-shaped ways, but not B-shaped or 8-shaped ways.
This was discussed in #14202. I think it is just a compromise that suits the usage inOSM , not exactly right or wrong.

Method buildSpanningPath() calculates a path that is accepted by the OverlappingWays test, means, the path doesn' contain a segment twice. I see no reason to use this in CombineWayAction and I agree with Dirk that the result for the attached brandenburg-simple.osm is wrong as it silently removes a part of one of the ways.

Method buildSpanningPath() is also used in ParallelWayAction, and I also see no need to use it there.
I think org.openstreetmap.josm.plugins.opendata.core.datasets.WayCombiner is another such case.

IIGTR only the plugin merge-overlap uses and requires exactly what buildSpanningPath() does now.

So, I think I should

• create a new simple method to combine ways which just connects end points of the ways and - maybe - reverses the order where needed, but without removing edges or recombining parts and use that new method to replace the wrong usage of buildSpanningPath()
• improve performance of buildSpanningPath() as it might help the merge-overlap plugin

[GerdP]

Improve performance of NodeGraph.buildSpanningPath(). Remaining sow case: When the graph is disconnected it might still search through all nodes, e.g. when you add an unconnected closed way with a few nodes to Brandenburg.osm search and try to connect all three ways. Will not take foreever but maybe a minute or so to find out no result. I think this case should better be detected in the calling method.

[GerdP]

further improvements: detect unconnected graph, only iterate over those nodes which can be start nodes in a spanning way. This works in fractions of a second for all cases I can think of, even with > 40000 nodes.

[GerdP]

I plan to commit patch 18368-v3b.patch after the release of the new tested version.

[GerdP]

In 15554/josm:

see #18368: Drastically improve performance of NodeGraph.buildSpanningPath() used in combine way 'C' and parallel ways map mode
In special cases the old code was extremely slow, for example when you try to connect the ways of a complex multipolygon containing inner rings
which always should fail.

• detect unconnected graph
• use extra HashSet for check if a NodePair is already in the path to avoid sequential search
• avoid to test start points which cannot be the start point in a "spanning path"

[GerdP]

Performance problem is solved. I've opened #18385 for the wrong result.