Search code examples
pythonautocad

How to find closed objects among an array of lines?

I have a list of tuples. Each tuple contains coordinate points (x, y, x1, y1,...) forming a line. All these lines form a drawing.

drawing

There are 5 closed objects in this picture. How can I get the number of these objects with their coordinates?

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

I tried to use the DFS (Depth First Search) Algorithm, but it always returned fewer objects than there actually were. But the data here is presented differently - here there are no more than two points in the tuple, but this does not change the drawing

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

  • Here is a condensed version of Grismar's answer, where he has a good explanation as well. I just removed the manual search for segments and treated each point as a node directly.

    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)