How to find cycles among an array of lines?

Question

I have a minimal reproducible example.

Input data:

coordinates = [(50.0, 50.0, 100.0, 50.0), (70.0, 50.0, 75.0, 40.0, 80.0, 50.0)]

This is what these lines form in the drawing:

The task is to find a loop, i.e. a closed region, and display their boundaries in the terminal.

In this case, the result should be as follows (it is represented as [(line1), (line2)]):

[(70.0, 50.0, 75.0, 40.0), (75.0, 40.0, 80.0, 50.0), (80.0, 50.0, 70.0, 50.0)]

I tried the cycle_basic method from the networkx library.

But in this method it is necessary that the cycle vertices touch the vertices of other cycles. But here the vertices can touch any place of another cycle

Answer 1

IIUC, you want the induced / chordless_cycles. If so, here is a primal approach with networkx:

points = MultiPoint(list(batched(chain.from_iterable(coordinates), 2)))

lines = [
    line
    for coo in coordinates
    for pop in pairwise(batched(coo, 2))
    for gc in [split(LineString(pop), points)]
    for line in gc.geoms
]

G = gdf_to_nx(
    gpd.GeoDataFrame(geometry=lines), multigraph=False, approach="primal"
)

cycles = [
    [
        tuple(chain.from_iterable(pair))
        for pair in pairwise(cyc)
    ] for cyc in nx.chordless_cycles(G)
    for cyc in [cyc + [cyc[0]]]
]

Output (cycles, clockwise):

[
    [ # top/green cycle
        (70.0, 50.0, 80.0, 50.0),
        (80.0, 50.0, 77.5, 45.0),
        (77.5, 45.0, 72.5, 45.0),
        (72.5, 45.0, 70.0, 50.0),
    ],
    [ # bottom/red cycle
        (72.5, 45.0, 77.5, 45.0),
        (77.5, 45.0, 75.0, 40.0),
        (75.0, 40.0, 72.5, 45.0),
    ],
]

Used input (coordinates) :

from itertools import chain, batched, pairwise
import geopandas as gpd
from momepy import gdf_to_nx
import networkx as nx
from shapely import LineString, MultiPoint
from shapely.ops import split

coordinates = [
    (50.0, 50.0, 100.0, 50.0),
    (70.0, 50.0, 75.0, 40.0, 80.0, 50.0),
    (72.5, 45.0, 77.5, 45.0)
]

---

^{Full code
Old answer}