I am trying to code a function to find the cycles in a 2D set of curves. The input would be something like this:
I have highlighted some curves to show how any line will only meet another at an endpoint.
My desired output is a list of tags of all the objects that form a cycle. There are many possible cycles in this geometry, but I am after all the cycles that have no cycles within them. Below is an example of the desired cycles to be found in the part, with different colours representing the areas enclosed by the different cycles.
I am thinking of solving it iwith the followng method ( in terrible pseudocode)
Get spanning tree of part // all curves not in spanning trees are called Ncurves For (all Ncurves) // 1 --Add one curve that was not in spanning tree --Find resulting cycle made --Keep cycle with contained Ncurves --If (cycle does not contain any Ncurves) ---> it is a desired cycle--->Break ----Get spanning tree of new cycle with any Ncurves // 2 ----For (all Ncurves in this new spanning tree) ----------do steps between 1 and 2
My method is iterative and could branch out into many loops but given the nature of the geometry it might be better than finding every possible cycle and choosing from there. Also I cant really get my head around the pseudocode for a function to find every possible path around the curves, never mind actually coding it.
I have asked a similar question here but I don't need to create a sheet, I just need a list of bounding tags. Link:
As a constraint I have to solve the problem in C++
Any ideas or guidance on how to code this would be greatly appreciated.