Traversal rewrite

[barendgehrels]

Hi! This is mainly for @vissarion @tinko92 and @awulkiew

This is based on some recent bugs (#1349, #1221), PR's (#1350, #1356, #1357, all closed and not merged) and discussions.

Introduction

It was hard to fix it inside the traversal_switch_detector. Also, the switch detector, and the traversal itself had become quite complex in the last 15 years. The new test provided by Tinko easily detected errors in the logic (similarly for recursive polygons).

I first did an experiment using Boost.Graph, which can detect biconnected components. Biconnected components perfectly indicated isolated rings, where there is one connection, but it should not be followed.

That experiment was successful and that is one of the PR's. That makes traversal_switch_detector redundant for ii turns (the intersection/intersection, these are the turns which generate interior rings touching the exterior, and are therefore "isolated").

But I realized that part of the switch detector should then stay, because it is used for union as well - and that the normal traversal would become another (bit) more complex, and that the primitives I used for the graph ('nodes`) are very convenient for traversal as well.

A node is either a turn (this is an intersection, but we call it turn), or a cluster (a cluster is a set of colocated turns). In the traversal we travel from node to node. The old algorithm needed some complex logic to figure out how to travel through a cluster. Some of that logic is still there, but with nodes it became different and much simpler.

Using these new primitives, the traversal became also simpler and more consistent. It is also less code.

Essential question

Can we add a dependency to Boost.Graph?

If not, it's also solvable, but then we need to write our own code to detect biconnected components (it's a common algorithm).

More details

The image below is an intersection with two polygons, where all operations are present and all methods as well.

The resulting contains 2 inner rings (lower and right). The "pseudo" inner ring on the left side is not an inner ring, because it would then cause a disconnected interior. So that's a separate outer ring.

This is the corresponding Graph with the same turn numbers, and their "component ids"

(The component ids are indicated in the first QGis figure as well, as red numbers). Feeding this information into Boost.Graph and it can generate the components with one call.

For union, it is similar:

and the graph, showing one isolated area

So this also makes the concept of "isolation" similar to intersection and union (it was not).

Small detail: if there is a turn traveling to itself (a common situation), an extra "pseudo-node" is generated in between, for the graph only, to properly do the detection. It's not relevant for traversal.

Test results

The overlay and buffer tests show no regressions (after some iterations of course).

I'm happy to say that it does well on most of the robustness tests.

• the new random_bitset_grids test of @tinko92 does not find any errors anymore in the new traversal
  • old code: iterations: 100000 errors: 15 time: 48.341
  • new cod: iterations: 100000 errors: 0 time: 57.101
• neither does recursive_polygons (with triangles)
  • old_code: geometries: 255000 errors: 2 type: d time: 22.955
  • new code: geometries: 255000 errors: 0 type: d time: 22.062
• and recursive_polygons_buffer
  • old code: geometries: 168165 errors: 617 type: d time: 18.235
  • new code: geometries: 173145 errors: 591 type: d time: 18.402

The buffer test is very prone to floating point precision - which are not really touched by this PR. It is better but not by much yet.
The performance should remain similar. I see now, writing this summary, that Tinko's test is a bit slower, I'll check why that is (there seem still some improvements possible).

Code base size

Based on this all, there will be a huge PR with around 6600 lines deleted, and around 4000 lines added again.

In summary, deleted:

• traversal_switch_detector.hpp (746 lines)
• traversal_ring_creator.hpp (427 lines)
• traversal.hpp (1046 lines)
• sort_by_side.hpp (746 lines)

And added

• detect_biconnected_components.hpp (249 lines, the detection)
• traverse_through_components.hpp (590 lines, the main traversal)
• select_edge.hpp (349 lines)
• is_target_operation.hpp (222 lines)
• assign_clustered_counts.hpp (552 lines, replacing sort_by_side)
• and some more, and many test cases

Timeline

Most of the work is done, I'll publish a big PR next week

[tinko92]

Sounds very promising! Reducing the complexity of overlay by 2600 lines and gaining correctness are both great, especially losing sort_by_side sounds like it could further help to isolate floating-point computations and make the analysis of future issues that relate to them less complex.

My test may be prone to generating pathological cases wrt to how many turns and clusters there are compared to the overall input size, its time cost for turn handling may be irrelevant to real world input.

For all use cases that I used BG for in the past (mainly as a dependency for 2D algorithms in a research CAD software project), adding this dependency on BGL would not have been an issue since it has the same licence, is also header only, is also a very mature library, has same C++14 requirement and afaics no current discussion visible in their github to raise that. I do not know about compilation times, that would be observeable with the PR. It seems strongly preferable to me over adding the complexity of reimplementing the biconnected graph detection in BG itself.

[vissarion]

Nice observation and work! The idea of reducing the isolated rings computation to biconnected components in the graph is neat and will improve the code a lot (both in correctness and easiness of maintenance).

Regarding the main question which is adding a dependency on Boost.Graph I do not have clear preference because it depends on the pros and cons. The pros are posted by Tinko above, namely, no need of reimplementation, maintenance of a new algorithm. On the other hand, if the implementing biconnected components is simple and short (which seems like the case) maybe it makes sense to go that way avoiding a new dependency. Additionally, the implementation should not be as generic as the implementation of the Boost.Graph since it is an internal detail. Also the new implementation can work on the existing structure of turns as computed in Boost.Geometry and do not need to transform it to a graph structure and pass it to Boost.Graph (maybe that is not an issue, since I haven't seen the code).

[barendgehrels]

Thanks for your answers!

Regarding Boost.Graph

• agree with the pros listed by Tinko
• also agree with Vissarion, the implementation should be around 200 lines of code
• it uses only Boost.Graph' s public interface, that should not be a problem
• but yes we have to do some transformation indeed
• and there is one issue in the Boost.Graph's output for biconnected components, I listed in my (still unpublished) branch as It appears that in an undirected graph, the components for two edges are sometimes different. - so that would also be a reason to avoid it

Regarding performance:

• I improved it a bit but Tinko's test stays a bit slower than it was before (other tests are not influenced).
• Agree that it is not the typical use case and it does not have to block the new algorithm
• At least - we can have the PR first such that we know where we're talking about

Regarding sort by side:

• The file is gone indeed - but some sorting is still done, we heavily depend on side

I'm still doing some cleanup and will probably first do a small PR with some tweaks only (for example in cmake files)