Как найти количество всех закрытых регионов? ⇐ Python

[Anonymous]

Нам нужно написать программу на Python по следующей логике:
Например, у нас есть данные координат линии, где каждый кортеж представляет собой линию из двух точек.
coordinates = [(0.0, 0.0, 50.0, 0.0), (50.0, 0.0, 50.0, 50.0), (50.0, 50.0, 0.0, 50.0), (0.0, 50.0, 0.0, 0.0)].

Задача — выявить все соединения линий, образующие замкнутую область, и вывести количество этих областей. В этом примере есть квадрат. Таким образом, на выходе должно быть 1.
Другие входные данные о координатах:
coordinates = [(0.0, 0.0, 50.0, 0.0), (50.0, 0.0, 50.0, 50.0), (50.0, 50.0, 0.0, 50.0), (0.0, 50.0, 0.0, 0.0), (0.0, 50.0, 50.0, 0.0)]

В данном случае имеется квадрат и линия, разделяющая его пополам. Программа должна определить, что в данном случае эта линия делит наш квадрат пополам и поэтому теперь у нас есть 3 замкнутые фигуры.
Таким образом она должна вывести - 2. Потому что замкнутой области, внутри которой еще есть замкнутые области, нет. дольше считается.
То есть смысл в том, чтобы вывести количество всех закрытых объектов отдельно
Вот код, который может найти только одну закрытую область:
def find_connected_lines(coordinates):
connected_lines = []

lines_dict = {}
for line in coordinates:
for i in range(0, len(line), 2):
point = (line, line[i + 1])
if point not in lines_dict:
lines_dict[point] = []
lines_dict[point].append(line)

def dfs(point):
if point not in visited:
visited.add(point)
for line in lines_dict[point]:
for i in range(0, len(line), 2):
next_point = (line, line[i + 1])
if next_point != point:
dfs(next_point)

for point in lines_dict:
if len(lines_dict[point]) == 2:
connected_lines.append(lines_dict[point][0])
visited = set()
dfs(point)

return connected_lines

def count_closed_areas(coordinates):
connected_lines = find_connected_lines(coordinates)
count = 0
while connected_lines:
line = connected_lines.pop()
count += 1
for other_line in list(connected_lines):
if set(line).intersection(set(other_line)):
connected_lines.remove(other_line)
return count

coordinates1 = [(0.0, 50.0, 0.0, 0.0), (0.0, 50.0, 50.0, 50.0), (0.0, 0.0, 50.0, 0.0), (50.0, 0.0, 50.0, 50.0)]
print("Number of enclosed areas:", count_closed_areas(coordinates1))


Подробнее здесь: https://stackoverflow.com/questions/781 ... ed-regions