Программа для подсчета многоугольников в логической 2D-матрице
class Graph:
def __init__(self, row, col, g):
self.ROW = row
self.COL = col
self.graph = g
# A function to check if a given cell
# (row, col) can be included in DFS
def isSafe(self, i, j, visited):
# row number is in range, column number
# is in range and value is 1
# and not yet visited
return (i >= 0 and i < self.ROW and
j >= 0 and j < self.COL and
not visited[j] and self.graph[j])
def DFS(self, i, j, visited, coordinates):
# These arrays are used to get row and
# column numbers of 8 neighbours of a given cell
rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
# Mark this cell as visited
visited[j] = True
# get the vertex co-ordinates of polygon
coordinates.append([i, j])
# Recur for all connected neighbours
for k in range(8):
# print('i :', i, 'i + rowNbr[k] :', i + rowNbr[k], 'j :', j, 'j + colNbr[k]: ', j + colNbr[k])
if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):
self.DFS(i + rowNbr[k], j + colNbr[k], visited, coordinates)
# The main function that returns
return coordinates
def countIslands(self):
# Make a bool array to mark visited cells. Initially all cells are unvisited
visited = [[False for j in range(self.COL)] for i in range(self.ROW)]
# Initialize count as 0 and travese through the all cells of given matrix
count = 0
for i in range(self.ROW):
for j in range(self.COL):
# If a cell with value 1 is not visited yet, then new island found
if visited[j] is False and self.graph[j] == 1:
# Visit all cells in this island and increment island count
# Initialize the vertex co-ordinates empty list
coordinates = []
all_nodes = self.DFS(i, j, visited, coordinates)
all_polygon.update({'polygon{}'.format(count): all_nodes})
count += 1
return count, all_polygon
def read_binary_file(file_name):
graph = []
with open(file_name, "r") as f:
for line in f.readlines():
graph.append([int(i) for i in line.strip()])
row = len(graph)
col = len(graph[0])
return graph, row, col
if __name__ == '__main__':
all_polygon = dict()
centroids = dict()
file_name = 'sample.txt'
graph, row, col = read_binary_file(file_name)
g = Graph(row, col, graph)
count, all_polygon = g.countIslands()
print('Count of Polygons :', count)
for i in range(count):
x = [p[0] for p in all_polygon['polygon{}'.format(i)]]
y = [p[1] for p in all_polygon['polygon{}'.format(i)]]
centroid = (sum(x) / len(all_polygon['polygon{}'.format(i)]), sum(y) / len(all_polygon['polygon{}'.format(i)]))
centroids.update({'polygon{}'.format(i): centroid})
print(centroids)
Текущий код: Возможность подсчета общего количества полигонов (независимо от того, завершены они или нет) с использованием рекурсивного алгоритма DFS. но мне нужно отдельно подсчитать завершенные и незавершенные.
Пример двоичной матрицы 10x10:
0000000000
0011111000
0100000100
1000001000
1000010000
0111100000
0000000000
0000111110
0000000010
0000111110
Здесь показано, как получить количество замкнутых и неполных многоугольников.
Polygon 1 edges:[[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 7], [3, 6], [4, 5], [5, 4], [5, 3], [5, 2], [5, 1], [4, 0], [3, 0], [2, 1]]
Polygon 2 edges:[[7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 8], [9, 7], [9, 6], [9, 5], [9, 4], [9, 8]]
Centroids: {'polygon0': (2.87, 3.26), 'polygon1': (8.0, 6.18)}
Подробнее здесь: https://stackoverflow.com/questions/528 ... y-2d-array
