I have a list of tuples. Each tuple contains coordinate points (x, y, x1, y1,...) forming a line. All these lines form a 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)
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)