如何在一系列线中找到闭合对象？

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

注释掉绘制原始图形或相应网络的部分。如果您按原样运行它，它将输出由您拥有的数据定义的图形中的“形状”数量或无弦周期数。