[streets] Ignored buildings for street triangulation

[vvoovv]

[streets] Ignored buildings for street triangulation

[polarkernel]

Mapping CONFLICT unresolved: Three or more polygons removed
What are the ids of those polygons? What's wrong with them?

The following ids have been involved:
127311040, 127311042, 889264836, 889264837, 127311046, 28956401, 127311031, 727503161

At the end of the block-building process, they form a degenerated polygon due to the intersection with the landuse=construction area 889264836:

[polarkernel]

Just an intermediate report on what I am currently doing:

After several days of attempts to patch and improve the previous solution, I abandoned this approach. Currently, I am trying to find and correct mapping errors in advance, before the connected buildings and polyline objects are merged into blocks.

Mapping errors occur much more frequently than I previously thought. Basically, three types of errors can be found::

• Self-intersections in objects
• Intersections between neighbor objects
• Single shared nodes between objects

To remain efficient I use scientific methods from graph theory. I plan (and have partially implemented) to apply the following steps:

• From a graph of all object segments it is easily possible to find disconnected groups of connected objects using a BFS (breadth-first search) in the graph. Such groups will potentially be merged to blocks.
• Self intersections and intersections between neighbor objects can then be found using our SweepIntersector, applied to every such group. This is much faster than to find intersections for all segments at once.
• These intersections repaired before moving on.
• Using another graph algorithm based on DFS (depth-first search), so called articulation points can be found, which are exactly the single shared nodes between objects.
• Objects connected by single shared nodes are the repaired by separating them by 1mm.

Unfortunately, I found that the SweepIntersector still has a bug, so I have to step back and try to fix it first. So things are going on, but take time. However, it is the only way to get a reliable solution.

[vvoovv]

I think this is due to straight angle removal.

I suggest to move the code block if app.buildings at the very end of the file mpl_blosm.py. Then the action RoadPolygons will be executed before the action StraightAngles.

[polarkernel]

Is it a serious bug?

It wasn't. Although the algorithm can handle overlayed segments, it seems that it is not (always) able to handle shared segments. Those arise often for buildings and polyline objects. I do not try to fix the algorithm for this very special case, it's too complicated. But it's easy to remove shared segments before checking for intersections. So this issue is solved.

[vvoovv]

Can we also remove the action WayClustering?

Yes.

Then I'll retire the option --wayClustering and rename the class WayClusterRenderer.

[vvoovv]

I removed WayClustering and the option --wayClustering from setup/mpl_blosm.py.

[polarkernel]

I have completely refactored the method checkAndRepairObjectPolys() in read_polygons.py. Mapping issues like intersections or single shared vertices between buildings are now repaired before these objects are merged to blocks. This is much cleaner and also more reliable than before. All, the construction of graph-cycles (with island cycles), the generation of blocks for buildings and polyline objects and the subtraction of these blocks from the graph-cycles, execute now without any error and without removal of any object. This issue #32 is thus solved.

The next issue to solve is triangulation. It seems that sometimes duplicate triangles are generated.

[polarkernel]

Here is an example of ignored buildings for the street triangulation.
File: facade_visibility/berlin_karl_marx_allee.osm, near the cemetery.

Mapping CONFLICT repaired: Single shared vertex between polygons 23971268 and 272556005
Mapping CONFLICT repaired: Overlapping or touching polygons 28956401 and 889264836
Mapping CONFLICT unresolved: Polygons 863144481 and 23971340 removed
Mapping CONFLICT unresolved: Three or more polygons removed

This building block is related to the last line of the mapping conflict messages. This is one case that I did not yet implement in the series of repair attempts, but I will set it onto my to-do list. The reason is an intersection of the landuse=construction area 889264836 with its neighbor building 28956401.

Beside the attempt to repair such cases, should we maybe filter landuse=construction areas?

[vvoovv]

Mapping CONFLICT unresolved: Polygons 863144481 and 23971340 removed

What's wrong with them? The polygons don't overlap.

[vvoovv]

Mapping CONFLICT unresolved: Three or more polygons removed

What are the ids of those polygons? What's wrong with them?

[vvoovv]

Beside the attempt to repair such cases, should we maybe filter landuse=construction areas?

Construction areas area clearly distinguishable on the ground. So I don't think it makes sense to filter them out.

[polarkernel]

Mapping CONFLICT unresolved: Polygons 863144481 and 23971340 removed
What's wrong with them? The polygons don't overlap.

This is a bug. At the end of the block-building process, polygons have only been merged, when they intersected. I will add a condition A.touches(B) . This correction will follow with the next commit.

[polarkernel]

Mapping CONFLICT unresolved: Polygons 863144481 and 23971340 removed
What's wrong with them? The polygons don't overlap.
This is a bug.

No, it isn't. The objects do intersect:

[vvoovv]

• From a graph of all object segments it is easily possible to find disconnected groups of connected objects using a BFS (breadth-first search) in the graph. Such groups will potentially be merged to blocks.

I've just made a commit to the dev branch, where I used depth-first search to find building parts within a building footprint. The problem can be also reformulated as the problem to find a group of connected edges.

I guess either BFS or DFS can be used to find a group of connected objects.

I've also implemented a tracing of missing parts. It's required that building parts cover the building footprint completely. However there is an undocumented way of 3D mapping: map only building parts that differ from the rest of the buildings. The rest of the building then should have the height taken from the building footprint. To trace those missing parts it was required to sort the edges sharing the same node by angle. I employed the concept of pseudo-angle as you introduced it earlier.

The question if we can share something from our current work. I am not sure. My task was quite specific to the processing of building parts.

[vvoovv]

Unfortunately, I found that the SweepIntersector still has a bug, so I have to step back and try to fix it first. So things are going on, but take time. However, it is the only way to get a reliable solution.

Is it a serious bug?

[vvoovv]

No, it isn't. The objects do intersect:

Sorry. I can't find this node. Can you point to it on a larger map extract?

[polarkernel]

The question if we can share something from our current work. I am not sure. My task was quite specific to the processing of building parts.

Thanks! I already have solutions for both, the search for connected segments and for the search for articulation nodes. The first uses a BFS and the latter a DFS search. They have been easy to implement and have a O(n) complexity.

[polarkernel]

Sorry. I can't find this node. Can you point to it on a larger map extract?

Maybe this helps. The node of the outer building (at the right) is inside the other building, but only for about 4mm.

[polarkernel]

Is it a serious bug?

I don't hope so. One intersection is missed and another ist ouside of the segment. Maybe it's from the same issue. The only problem is that debugging in this complicated structure is very difficult, which makes the task boring.

[vvoovv]

Sorry, still can't find the problem node. The greenish polygon is grass. The other polygon is a building. I checked it in JOSM.

[polarkernel]

Sorry, still can't find the problem node. The greenish polygon is grass. The other polygon is a building. I checked it in JOSM.

???? You are right, in the original data there is no intersection, but look once like this ...

        buildingVerts = [v for building in manager.buildings for v in building.polygon.verts if\
                         building.element.tags["id"] == '23971340' ]
        grassVerts = [edge.v1 for polyline in manager.polylines for edge in polyline.edges if\
                         polyline.element.tags["id"] == '863144481' ]
        for v1,v2 in zip(buildingVerts,buildingVerts[1:]+[buildingVerts[0]]):
            plt.plot([v1[0],v2[0]],[v1[1],v2[1]],'k')
        for v1,v2 in zip(grassVerts,grassVerts[1:]+[grassVerts[0]]):
            plt.plot([v1[0],v2[0]],[v1[1],v2[1]],'r')
        plt.gca().axis('equal')
        plt.show()        

... and magnify this node, then you will see that the building has no node at this position. Was it maybe removed by straight angle removal? If yes, then this feature should be switched off for this task. It is maybe the reason for many other issues.

EDIT: Code corrected.

[polarkernel]

I suggest to move the code block if app.buildings at the very end of the file mpl_blosm.py.

Seems not to work. The block if app.highways or app.railways also refers to buildings, which then becomes None in mpl_blosm.py. When I put the code block if roadPolygons in front of it, then building.polygon does not exist from the manager.

[vvoovv]

I commented the action StraightAngles for now.

[vvoovv]

Can we also remove the action WayClustering?

[polarkernel]

I commented the action StraightAngles for now.

Works and removes a lot of conflicts. Thanks.

Can we also remove the action WayClustering?

Yes.

[vvoovv]

Can we also remove the action WayClustering?

Yes.

If I remove the action WayClustering then the attribute networkGraph isn't created. That leads to an error.

[polarkernel]

If I remove the action WayClustering then the attribute networkGraph isn't created. That leads to an error.

The question is: Will we still need these junction clusters built in WayClustering? It was an early attempt to find ways clusters, not finished and not reliable. There the attribute networkGraph is mainly used to render the beautiful map. I could create this attribute in RoadPolygons, as it is used there anyway. I just tried, this seems to work. I committed a (backup) version where I commented the code in WayClustering and added the construction of networkGraph to RoadPolygons. All other processes are commented out, so you may use it to test if this map is still drawn when you remove WayClustering.

[vvoovv]

Now the street triangulation isn't rendered.

[vvoovv]

The question is: Will we still need these junction clusters built in WayClustering? It was an early attempt to find ways clusters, not finished and not reliable.

I hope that it will be possible to create the geometry for the streets without junction clusters.

[polarkernel]

Now the street triangulation isn't rendered.

That's intentional, I'm in the middle of the development there and this part is not running yet. In the method go() of RoadPolygons these processes are commented out. But when the map is rendered, its OK, then you may remove WayClustering.

[polarkernel]

I hope that it will be possible to create the geometry for the streets without junction clusters.

I propose we let the code of WayClustering in the project, but do not execute it, just in case should it later be required unexpectedly.

[vvoovv]

I propose we let the code of WayClustering in the project, but do not execute it, just in case should it later be required unexpectedly.

Yes, I wanted to preserve WayClustering in the repository.

[vvoovv]

I also renamed WayClusterRenderer -> RoadPolygonsRenderer.

[vvoovv]

Have you tested it against all files in the repo osm_extracts?

[polarkernel]

Have you tested it against all files in the repo osm_extracts?

Yes, except the small special test files, like for example feature_test_01.osm.

[polarkernel]

The next issue to solve is triangulation. It seems that sometimes duplicate triangles are generated.

This issue is fixed now.

[vvoovv]

Thanks!

Time to close this issue.