如何在一组线中找到循环？

Question

我有一个简单的例子可以复现这个问题。

输入数据如下：

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

这些数据在图形中形成的样子是这样的：

任务是找到一个循环，也就是一个封闭的区域，并在终端上显示它们的边界。

在这个例子中，结果应该是这样的（用[(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)]

我尝试使用networkx库中的cycle_basic方法。

但是这个方法要求循环的顶点必须接触到其他循环的顶点。而在这里，顶点可以在另一个循环的任何地方接触。

Answer 1

如果我理解得没错，你想要的是诱导的 / 无弦循环。如果是这样，这里有一个使用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]]]
]

输出结果（循环, 顺时针）：

[
    [ # 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),
    ],
]

使用的输入（坐标）：

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)
]

---

^{完整代码
旧答案}