[streets] Unconnected Way-Islands in Graph-Cycles

[polarkernel]

A solution is sought for the processing of way-islands that are not connected to the rest of the way-section graph.

[polarkernel]

In principle it is not difficult to detect such way-islands. Graph-cycles are constructed by following the edges of the graph in counter-clockwise order, as depicted in a) in the sketch below. An island creates then two polygons using the same vertices, as depicted in b). One is in counter-clockwise order (green) and one in clockwise order (red). The former can be processed like all other cycles, while the latter can easily be detected and becomes a hole in the outer polygon. pyGEOS should bw able to handle these. The only difficulty is to find the surrounding cycle for the island-cycle in an efficient way, as the polygons get created more or less randomly.

A special problem arises, when the ways of the island do not form an inner cycle, as depicted in c). This can still be detected , as the clockwise polygon gets still created, but as a degenerated polygon with zero area. Maybe a dummy island could be constructed by the union of the inflated way segments, but this situtation is still completely unsolved.

[vvoovv]

Is this problem only relevant for a graph-cycle located within another graph-cycles? What about two unconnected graph-cycles?

[polarkernel]

Is this problem only relevant for a graph-cycle located within another graph-cycles?

The scene border is already used as a dummy cycle (its way-sections get tagged as category='scene_border' in the section network, when the clipping to the scene occurs). So for example two islands would become two holes in this dummy cycle.

[vvoovv]

A possible solution.

From the upper part of the island spawn a vertical way-segment going upwards till it intersects with another graph-cycle. Additional from the lower part of the island spawn a vertical way-segment going downwards till it intersects with another graph-cycle.

[polarkernel]

Sorry, I accidentally clicked a wrong button.

[polarkernel]

... as depicted in b). One is in counter-clockwise order (green) and one in clockwise order (red). The former can be processed like all other cycles, while the latter can easily be detected and becomes a hole in the outer polygon.

I just committed a solution that processes this case correctly. I used the proposed detection of the clockwise ordered cycle, when the cycle is a way-island. There are examples, where such islands are even nested, for instance the ways around the object 637834383 in _facade_visibility/beijingcenter.osm. The detected cycles around this object are depicted on the left of the following image.

The black polygon is the outermost cycle and the blue ones are the detected cycles with clockwise order. For every island polygon, its dead-end ways are removed and the enclosing counter-clockwise cycle is found, then the island becomes a hole of this cycle. Like this, the three graph-cycles with holes depicted on the right are generated (hole in red). Finding the smallest enclosing cycle has a complexity of O(n*m), where n is the total number of cycles and m is the number of island-cycles. To give some numbers, for the large scene of _beijingcenter.osm, n=722 and m=5. Most of the required comparisons fail already by comparison of the bounding boxes, which is a fast test.

The last commit includes also another improvement, which addresses islands that are still connected by some kind of bridge to the outer cycle by a single way. In the old version, all dead-end ways have been removed, while this bridge was converted into a one millimeter width gap. A very complicated process (already mentioned here), that was error prone. In _bratislava_oldtown.osm, in a large area around the Museum of History (node 437135673), I found an example that crashed this process:

It's unbelievable, but this maze is a graph-cycle with islands, you can reach any other from any point inside (except in the islands). In my new solution I removed all dead-end ways, including the bridges and created islands, also cleaned from dead-ends. The result is a graph-cycle (black), a set of holes (red) for the islands and a set of removed ways (blue). On the right, just as illustration, the cycle-graph ready for further processing in green:

The code to reach this result is very simple and reliable. A lot of issues disappeared, since I introduced this approach. There are still issues to debug in the stages that follow, but this was again a good step forward, I think.

[vvoovv]

I tried the file _bratislava_oldtown.osm. What are the blue lines used for?

[polarkernel]

I tried the file bratislava_old_town.osm. What are the blue lines used for?

Sorry, I forgot that, they are the result of an exception raised in the triangulation stage. Just comment the line 570 in _roadpolygons.py to remove them.

It is one example of ..

There are still issues to debug in the stages that follow