[streets] Buildings with a single shared vertex

[vvoovv]

It's required to join buildings with shared edges to triangulate the area within a graph-cycle.

Buildings that share only one vertex can't be processed by PyGEOS.

[polarkernel]

The issue seems to be more complicated. For buildings only, my proposition works fine. But for example this building in _facade_visibility/moscow_leningradskiprospekt.osm has a vertex (pointed to by red arrow) that has exactly the same value as the vertex of the landuse=grass polyline around it:

Both get then holes in the same cycle graph. pyGEOS has no problem with shared vertices, but the triangle's mototonization algorithm crashes. I don't know if this case should also be classified as OSM mapping issue. If not, then I have to solve the issue in the triangulation algorithm for shared vertices, I think.

[vvoovv]

I don't know if this case should also be classified as OSM mapping issue. If not, then I have to solve the issue in the triangulation algorithm for shared vertices, I think.

The grass and the buildings share the same OSM nodes. The mapping is completely correct.

[polarkernel]

The grass and the buildings share the same OSM nodes. The mapping is completely correct.

OK, then I have to find a general solution for the triangulation algorithm for shared vertices. Let me see if someone reveals this secret on the net.

[vvoovv]

The building and the grass can be joined together like it's done for the building with shared edges.

[polarkernel]

The building and the grass can be joined together like it's done for the building with shared edges.

That's another solution, for sure simpler than to adapt the triangulation algorithm. But this would require to find shared edges for both, buildings and polylines, so that these could be skipped, as it is possible now for buildings. The RoadPolygonsManager should provide some kind of polylineObjects in place of only buildings.

[vvoovv]

Where are the buildings joined in the code?

[polarkernel]

Where are the buildings joined in the code?

It is made in the method mergeBuildingsToBlocks(), starting at line 27. The principle is quite simple. All edges delivered by edgeInfo() are stored in a dictionary segDict, where the source vertex v1 is the key and the destination vertex v2 is the value. Starting at line 48, a first segment is taken and its way followed key by key until it is found as destination, while the used segments are removed from the dictionary. This path then becomes a polygon and the next starting key is taken for the next block.

Curently I use a queue as value of the dictionary, but ths is a relict of a first attempt to handle shared vertices.

[polarkernel]

Curently I use a queue as value of the dictionary, but ths is a relict of a first attempt to handle shared vertices.

I forgot to mention that in the committed version, the queue is required. Without it, the creation of blocks does not work for single shared vertices. I have a solution that handles these, but it is not yet committed.

[vvoovv]

The issue seems to be more complicated.

It can be even more complicated.

A building can share a single vertex with the grass (or forest and other areas). A building can share one or more edges with the area. A building can be located completely within the area. A building can overlap with the area.

Can we rely on PyGEOS to join buildings and other areas and then subtract the resulting polygons from the graph-cycle?

[polarkernel]

Can we rely on PyGEOS to join buildings and other areas and then subtract the resulting polygons from the graph-cycle?

I think, this should work. pyGEOS provides a method union(), which can construct the union of two polygons. I never used it yet, so I don't know exactly, what it does. The subtraction will be done without problems. A single shared vertex can be handled correctly, I know how to do that.

Note, pyGEOS is not the reason for the issues with shared vertices and edges. It is the scan line algorithm in the triangulation, used to create monotone polygons, that cannot handle them. What about to give me another week to do some research on how to solve the issue there?

[polarkernel]

Can we rely on PyGEOS to join buildings and other areas and then subtract the resulting polygons from the graph-cycle?

Just tried it to unify all polyline objects (areas and buildings of one search in the KD-tree) into one multipolygon using pyGEOS union() and then to subtract this from the graph-cycle polygon. Works perfect!! I could remove the whole process of creating blocks of buildings and the usage of shared edges. From a first impression (not measured) it is as fast as the current solution and the search for shared egdes is unnecessary. I have just to refactor the detection of single shared vertices.

You had a great idea!! Thanks!

[polarkernel]

Works perfect!!

Praised too soon! union()does not work correctly in many cases. Some objects are not complete, some not processed at all. Others create topology exceptions where there were none before. I have to think about the whole thing again. Too bad!

[polarkernel]

I have to think about the whole thing again

I am currently working on a solution that processes buildings and the other polyline object at once. Removing shared edges is not that difficult this way. Looks promising, all O(n) at this time. It seems that it will be even possible to handle intersecting objects. It is my goal to detect and, if possible, repair mapping issues already before starting the process chain.

[vvoovv]

I think it doesn't make sense to separate buildings from the other polylines objects (grass, forests, etc) for the task of triangulating a graph-cycle.

This is true for any polyline objects including the buildings:

• An area can share a single vertex with another area.
• An area can share one or more edges with another area.
• An area can be located completely within another area.
• An area can overlap with another area.

[polarkernel]

It is my goal to detect and, if possible, repair mapping issues already before starting the process chain.

This is a very demanding and frustrating task. I committed a version, where I tried to do this. Sorry for the wrong title of the commit, something went wrong with my development environmwent. A new method checkAndRepairObjectPolys() processes all edges of buildings and the other polylines objects at once. It does the following:

• Remove all shared edges between the objects.
• Checks for shared vertices and analyses them.
• Repairs polygons by merging them, when they intersect
• Repairs single shared vertices by moveing one of them by 1mm away from the other.
• Checks for (simple) self-intersections that may rarely be built by parsing the adjacency list of the edges.
• Reports detected issues.

When the original file _facade_visibility/moscow_leningradskiprospekt.osm (without any corrections) is processed, the following corrections are reported:

Mapping CONFLICT repaired: Overlapping or touching polygons 23971268 and 272556021
Mapping CONFLICT repaired: Overlapping or touching polygons 272556024 and 23971268
Mapping CONFLICT repaired: Single shared vertex between polygons 23971268 and 272556005
Mapping CONFLICT repaired: Overlapping or touching polygons 863144481 and 23971340
Mapping CONFLICT repaired: Overlapping or touching polygons 272556010 and 24264773
Mapping CONFLICT repaired: Overlapping or touching polygons 28956401 and 889264837
Mapping CONFLICT repaired: Overlapping or touching polygons 28956401 and 889264836
Mapping CONFLICT repaired: Overlapping or touching polygons 738177353 and 113597139
Mapping CONFLICT repaired: Overlapping or touching polygons  (28956401, 889264837, 727503161)  merged.
Mapping CONFLICT repaired:: Polygons  {28956401, 889264837, 727503161}  merged
Mapping CONFLICT repaired:: Polygons  {28956401, 889264837}  merged

But finally, still two exceptions on triangulation are raised. But its at least a starting point. However, I need a break now.

[vvoovv]

This is a very demanding and frustrating task. I committed a version, where I tried to do this.

Yes, it's an extremely complex task. That's really an achievement that you were able to provide a solution so fast!

However, I need a break now.

Well deserved :)

[polarkernel]

I committed a version with some minor bug fixes and improvements. The file _moscow_leningradskiprospekt.osm (without any corrections) runs now without any exceptions and all OSM-mapping errors are repaired correctly.

There was an issue that was very hard to find. Polygons with antiparallel edges with street-islands are neither simple nor valid, but pyGEOS does not check that. On the subtraction of the small gap that cuts the polygon there, pyGEOS creates sometimes duplicate vertices. I had to introduce an additional check there.

I continue now debugging with the goal that all our data files can be triangulated correctly without raising exceptions. The next error I found is a missing way-intersection by the Bentley-Ottman algorithm. Difficult to solve. Should you hear of a more robust library ...

[polarkernel]

The next error I found is a missing way-intersection by the Bentley-Ottman algorithm.

The current algorithm misses too often segments that are almost vertical. It isn't reliable enough for our application. Missing intersections lead to severe distortions in the construction of graph-cycles. The classical Bentley-Ottman does not allow vertical segments and segment with common start- or end-points. But given by the influence of sunshine on the orientation of buildings, vertical (S-N) streets appear quite often in maps. Furthermore, way-segments have by definition common end-points. Treating these issues in some kind of post-processing is too error prone.

Currently I try to implement another sweep-line algorithm following this paper. I believe that I understand the algorithm and will be able to implement it. However, it will take some time, but slowly I become trained in translating papers to code.

[vvoovv]

Currently I try to implement another sweep-line algorithm following this paper.

Hopefully this algorithm will provide more reliable results.

Will it be also required to implement the required algorithms and data structures from the LEDA library?

[polarkernel]

Hopefully this algorithm will provide more reliable results.

I think so. Vertical segments and segments with common start- or end-points are processed by intention at the moment, when the scan line meets them and not as a patch elsewhere. In one of the papers I found, Mehlhorn writes:

We want to stress that the implementation makes no assumptions about the input, in particular, segments may have length zero, may be vertical or may overlap, several segments may intersect in the same point, endpoints of segments may lie in the interior of other segments ...

Will it be also required to implement the required algorithms and data structures from the LEDA library?

I don't hope so. I will first work with simple double precision values and not use the types rat_point and rat_segment described in the paper. Should floating-point issues arrive I have the idea to copy some ideas from pyGEOS, but first I try without these.

[polarkernel]

I'm sorry, I was too brave, I have to give up this idea again. I failed at the implementation of the so-called Y-structure. It looked like a sorted container and is also based on a structure called sortseq. But then I stumbled over methods like insert_at, flip_items and reverse_items, which destroy the order of this structure. I can't understand what is actually done there. The risk is too high that I waste a lot of time and end with an unpredictable result, that will not help to solve our issue. I need to find another solution.

[polarkernel]

I'm sorry, I was too brave, I have to give up this idea again.

I think now I have finally domesticated this beast. My patience was stretched to its limits and sometimes beyond, but I think it's working now. Now it remains to integrate it into the program.

[vvoovv]

Congratulations!

I think it deserves to be published in a separate repository,

[polarkernel]

Congratulations! I think it deserves to be published in a separate repository,

Thanks! Publish in a separate repository, why not. But first I have to clean the code from a lot of debug output and then do some minor optimisations. Then see, if it still runs ;-). Finally I like to integrate it in our project and then test it under "OSM-conditions", which have been the hardest for many other algorithms we already developed in this project. After, I will put the code into a separate repo.

[vvoovv]

After, I will put the code into a separate repo.

Ok.

[vvoovv]

Did you use mathutils data structures and methods in the new library?

[polarkernel]

Did you use mathutils data structures and methods in the new library?

No. Vertices are just tuples of coordinates for input and output, while internally they use a special class. I dont think that mathutils vectors would be a good idea, as they use only single precision floating point numbers.

I commited the new version a few minures ago. Now, the construction of the section network and its graph cycles works correctly for all our data sets. There is one very complicated case of street islands in _bratislava_oldtown.osm, which lets the program crash. But this is not due to missing way intersections.

I will now prepare a short README for the new algorithm and post it then in a new repo. Then I will I continue to debug the rest of the program (inlcuding the case mentiones above), there seem to be still bugs in the subsequents stages.

[vvoovv]

I dont think that mathutils vectors would be a good idea, as they use only single precision floating point numbers.

I see.

[polarkernel]

I will now prepare a short README for the new algorithm and post it then in a new repo.

All done.

[vvoovv]

I've tested the file demo.py from _sweepintersector. It worked for me.