Kara-Ro
commented
2 years ago Quick update. I think that the situation when two diagonals originate from single vertex should not appear when minimal number of rectangles is required.
The problem is that my implementation of the queryPoint() does not include the interval endpoint. Hence the situation above was not recognized as intersection.
Simply including the endpoint solved the issue.
Hello,
The function findRegions() fails when a vertex is linked with four segments. This is the case when one vertex has two splitters. Then four rectangles should share this vertex.
This case is not covered in the code which then creates a chaotic loop and overlapping final rectangles similar to issue #6.
The plot above shows such a loop. The blue polygons shows holes in a large polygon. The grey lines are selected splitting horizontal and vertical diagonals. The crosses shows the set of vertices. The findRegions() functions starts at path 12 index 1 continues to 13/1 -> -2/62 -> -1/59 and now the interesting part is that the next vertex is not the initial 12/1 but 21/0.
This is a direct consequence of the reconnecting of vertices in splitSegment() function, which works only when maximum of three rectangles (including the hole poly) share the vertex.
I am trying to figure out a way around this issue. I tried to copy the vertex when visited twice in splitSegment() function similarly to approach in splitConcave() so it could be visited twice but no luck so far.
Adding line count to vertices as shortly discussed here https://stackoverflow.com/questions/45516875/splitting-the-remaining-space-of-rectangles-into-rectangles might also solve the issue.
If anybody have a better idea, or know the solution I would be grateful for help.