search

prochitecture / blosm

GNU General Public License v3.0
11 stars 3 forks source link

Last bug fixes towards correct triangulation #33

Open polarkernel opened 2 years ago

polarkernel commented 2 years ago

On the way to error free results for triangulations, I like to note some solved issues, just to remember the reasons for these bug fixes.

polarkernel commented 2 years ago

In rare cases, graph-cycle islands touch their surrounding cycle in just one single vertex, as depicted in the left image. The extraction of the cycle then delivers a degenerated polygon, as depicted in the middle image. pyGEOS can't process such degenerated polygons. The bug fix creates a polygon as depicted in the right image, with the smaller polygon as a hole for the island, where the vertices shared before are now separated by 1mm.

polarkernel commented 2 years ago

In rare cases, polyline objects (red in the example images below) touch the surrounding graph-cycle way-segments (black lines) in just one single vertex (see red arrow), when subtracted. These can't be triangulated and have to be separated by 1mm. This is done, where required, in a new process called cleaningForTriangulation() just before the triangulation.

polarkernel commented 2 years ago

After the above fixes, all our data sets provide correct triangles, except one graph-cycle from the file _beijingcenter.osm, which lets the triangulation crash. I am sitting now in front of this bug since three day and was not yet able to solve it. The polygon with its holes is completely correct, as it has to be expected. It is very strange that this crash then leads to a sequence of crashes of further polygons, although the PolygonTriangulation class is completely reset in each case. If you prevent this strange polygon from being processed, then the following ones will also be processed correctly.

Very bizarre! There must be a subtle bug in the triangulation, which is very hard to find.

vvoovv commented 2 years ago

Is it possible to eliminate that case with some condition that detects the failure of the triangulation?

polarkernel commented 2 years ago

Is it possible to eliminate that case with some condition that detects the failure of the triangulation?

Not yet within the triangulation itself. Should I understand, find a reason or any sign there, that the crash will arrive, then I would also be able to find a solution, I am sure.

The crash is caught by an exception handler, which would normally just exclude this graph cycle. But the mysterious consequences are, that the processing of the following cycles is affected by this crash. The triangulation receives simply two lists, one for the vertices outer polygon border and one containing lists of the hole vertices, similar to what we had for the skeletonization. The triangulation class itself is reset for every run. I even tried to create a new instance of it every time. In C or C++, such a behavior could arrive by pointers writing to memory that is not owned by the class. But in Python?

vvoovv commented 2 years ago

Really strange.

polarkernel commented 2 years ago

Should I understand, find a reason or any sign there, that the crash will arrive, then I would also be able to find a solution, I am sure.

I FIXED THE BUG !!!!! It was an error in processing a merge vertex that occurred only when two segments touched in a distinct situation. Among tens of thousands of polygons this happened only once in this special case. I tested the solution for all our data files, it works correctly! The solution is committed.

The strange behavior with the follow-up errors, however, remains unexplained.