Python 如何在一组行中找到循环

发布于03月20日

我有一个最小的可重现的例子.

输入数据:

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:

任务是找到一个循环，即一个封闭的区域，并在终端中显示它们的边界.

在这种情况下，结果应该如下(它表示为[(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)]个

我try 了networkx库中的Cycle_Basic方法.

但在这种方法中，循环顶点必须接触其他循环的顶点.但在这里顶点可以接触到另一个循环的任何地方

推荐答案

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

输出(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),
    ],
]

使用的输入(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}