如何在一组线段中找到闭合对象？

Question

我有一个包含多个元组的列表。每个元组里有一些坐标点（x, y, x1, y1,...），这些点连起来形成了一条线。所有这些线组合在一起就形成了一幅图。

在这幅图里，有5个封闭的形状。请问我该如何获取这些形状的数量以及它们的坐标呢？

Coordinates_list = [(939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005), (939, 1002, 939, 900), (939, 900, 961, 916), (961, 916, 1031, 898), (1031, 898, 1080, 906), (1080, 906, 1190, 896), (1190, 896, 1225, 897), (1223, 1005, 1225, 897), (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)]

我试着用深度优先搜索（DFS）算法来解决这个问题，但结果总是比实际的形状数量少。不过这里的数据呈现方式有些不同——每个元组里最多只有两个点，但这并不影响图的整体形状。

def find_closed_figures(lines):
    def dfs(line_idx, visited):
        visited.add(line_idx)
        for neighbor_idx, line in enumerate(lines):
            if neighbor_idx not in visited and lines[line_idx][3:6] == line[0:3]:
                dfs(neighbor_idx, visited)

    closed_figures_count = 0
    visited_lines = set()
    for idx, line in enumerate(lines):
        if idx not in visited_lines:
            dfs(idx, visited_lines)
            closed_figures_count += 1

    return closed_figures_count

coordinates_list = [(939, 1002, 0, 984, 993, 0), (984, 993, 0, 998, 1001, 0), (998, 1001, 0, 1043, 995, 0), (1043, 995, 0, 1080, 1004, 0), (1080, 1004, 0, 1106, 994, 0), (1106, 994, 0, 1147, 1003, 0), (1147, 1003, 0, 1182, 995, 0), (1182, 995, 0, 1223, 1005, 0), (939, 1002, 0, 939, 900, 0), (939, 900, 0, 961, 916, 0), (961, 916, 0, 1031, 898, 0), (1031, 898, 0, 1080, 906, 0), (1080, 906, 0, 1190, 896, 0), (1190, 896, 0, 1225, 897, 0), (1223, 1005, 0, 1225, 897, 0), (939, 1002, 0, 1031, 898, 0), (1031, 898, 0, 1106, 994, 0), (1106, 994, 0, 1190, 896, 0), (1190, 896, 0, 1182, 995, 0)]


closed_figures_count = find_closed_figures(coordinates_list)
print(closed_figures_count)

Answer 1

你提供的数据是由一系列“线”组成的，这些线是平面上从一个(x, y)点到另一个(x, y)点的段。你还提供了一个与这些数据对应的图形。

从图形上看，这些数据可以被视为一个网络（数学上叫做“图”），而你想解决的问题是找到这个网络中所有没有“弦”的循环。循环是网络中一系列点（顶点），它们形成一个闭合的环。没有“弦”的循环是指这个循环内部没有任何线穿过它——举个例子，如果你把形状1和形状2结合在一起，虽然你仍然会得到一个形状，但因为有一条线穿过它，所以它就不是没有“弦”的循环。

像 networkx 这样的库有一些函数可以帮你完成这些复杂的工作，只要你把数据转换成一个实际的图或网络。

看看这段代码：

from turtle import Turtle, setworldcoordinates
import networkx as nx
import matplotlib.pyplot as plt

# the example data
data = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]


def draw_segments(lines, llx, lly, urx, ury):
    # draw data in the format provided as a turtle graphic
    t = Turtle()

    setworldcoordinates(llx, lly, urx, ury)

    t.hideturtle()
    t.speed(0)

    for line in lines:
        start, rest = line[0:2], line[2:]
        rest = [(rest[i], rest[i + 1]) for i in range(0, len(rest), 2)]
        t.penup()
        t.setposition(*start)
        t.pendown()
        for point in rest:
            t.setposition(*point)


def lines_to_segments(lines):
    # breaks up `lines` into unique segments with a start and end point
    result = []
    for line in lines:
        assert len(line) % 2 == 0  # the number of coordinates has to be even for each 'line'
        for i in range(0, len(line) - 2, 2):
            # start always to the left of end, to be able to check for unique segments
            if line[i] < line[i + 2]:
                segment = (line[i], line[i + 1], line[i + 2], line[i + 3])
            else:
                segment = (line[i + 2], line[i + 3], line[i], line[i + 1])
            # only add the segment if it wasn't there already
            if segment not in result:
                result.append(segment)
    return result


def network_from_segments(segments):
    g = nx.Graph()
    for segment in segments:
        g.add_edge((segment[0], segment[1]), (segment[2], segment[3]))
    return g


def main():
    # to see the data as a graphic:
    # draw_segments(data, 800, 800, 1400, 1100)

    # break up the lines into individual edges
    data_segments = lines_to_segments(data)
    # and turn those into a networkx graph
    data_g = network_from_segments(data_segments)

    # show a graphic of the network using matplotlib (optional)
    # nx.draw(data_g, with_labels=True, font_weight='bold')
    # plt.show()

    print('The network is planar:', nx.is_planar(data_g))

    # all the heavy lifting is here, networkx can find the chord-less cycles
    cycles = list(nx.chordless_cycles(data_g))
    print('The number of chord-less cycles:', len(cycles))
    print('The cycles:')
    for cycle in cycles:
        print(cycle)

    input('Press Enter to continue...')


if __name__ == "__main__":
    main()

把绘制原始图形或对应网络的部分注释掉。如果你直接运行这段代码，它会输出根据你提供的数据定义的图中“形状”或说是没有“弦”的循环的数量。

解决问题的代码如下：

import networkx as nx

data = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]


def lines_to_segments(lines):
    # breaks up `lines` into unique segments with a start and end point
    result = []
    for line in lines:
        assert len(line) % 2 == 0  # the number of coordinates has to be even for each 'line'
        for i in range(0, len(line) - 2, 2):
            # start always to the left of end, to be able to check for unique segments
            if line[i] < line[i + 2]:
                segment = (line[i], line[i + 1], line[i + 2], line[i + 3])
            else:
                segment = (line[i + 2], line[i + 3], line[i], line[i + 1])
            # only add the segment if it wasn't there already
            if segment not in result:
                result.append(segment)
    return result


def network_from_segments(segments):
    g = nx.Graph()
    for segment in segments:
        g.add_edge((segment[0], segment[1]), (segment[2], segment[3]))
    return g


def main():
    # break up the lines into individual edges
    data_segments = lines_to_segments(data)
    # and turn those into a networkx graph
    data_g = network_from_segments(data_segments)

    # all the heavy lifting is here, networkx can find the chord-less cycles
    cycles = list(nx.chordless_cycles(data_g))
    print('The number of chord-less cycles:', len(cycles))


if __name__ == "__main__":
    main()

Answer 2

这里是Grismar的回答的简化版，他的解释也很不错。我只是去掉了手动查找段落的部分，直接把每个点当作一个节点来处理。

import networkx as nx

lines = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]
point_lists = [[pair for pair in zip(line[::2],line[1::2])] for line in lines]
edges = [segment for point_list in point_lists for segment in zip(point_list[:-1], point_list[1:])]
G = nx.from_edgelist(edges)
cycles = list(nx.chordless_cycles(G))
print('The number of chord-less cycles:', len(cycles))
print('The cycles:')
for cycle in cycles: print("\t", cycle)