How do you get the coordinates of the boundaries of each closed area?

Question

I have a list of coordinates of each line that forms such a drawing:

The task is to get the coordinates of all boundaries of closed objects. There are 15 closed objects in total. How can this be realized in autocad? Or using python.

The input data is too large, so I will show the format of this data - coordinates_list = [[x, y, z, x1, y1, z1], [x2, y2, z2, x3, y3, z3] etc.].

I tried to use the _-BOUNDARY command in autocad, but this command doesn't work because it doesn't allow you to read coordinates.

In python I tried to use DFS algorithm, but it finds always less number of objects

Answer 1

As @CaptainTrunky pointed out, in this case you need to use cycle_basic from the networkx library. I didn't get the desired result right away, because the area boundaries are displayed in a non-closed form. And to make them appear correctly, you need to duplicate the first point in the end:

coordinates = [(x1, y2, x2, y2), (x2, y2, x3, y4), etc.].

point_lists = [[pair for pair in zip(line[::2],line[1::2])] for line in coordinates]
edges = [segment for point_list in point_lists for segment in zip(point_list[::-1], point_list[1:])]
G = nx.from_edgelist(edges)

# cycle_basis
cycle_basis = nx.cycle_basis(G)
print("cycle_basis: =", len(cycle_basis)))
for cycle in cycle_basis:
    cycle.append(cycle[0])
    print(cycle)

Answer 2

I think (but I'm not 100% sure) that the thing you need is called cycle basis. You could try using networkx python package to build cycle basis, see the example. Algorithmically speaking, it works roughly in the following way:

1. Build a spanning tree. There would be some edges that are missing from a tree
2. Iterate over each missing edge and build a cycle that adds it to a tree. Each such cycle would be a part of cycle basis

I'm not sure about the problem you are solving, e.g. do you need a basis or a minimal basis or a full enumeration of all cycles in a graph, but most likely you will find a solution using the same networkx library