Как узнать количество неполных полигонов в двоичном 2d массиве - PullRequest
Новая
       68

Как узнать количество неполных полигонов в двоичном 2d массиве

0 голосов
/ 15 октября 2018

Программа для подсчета многоугольников в булевой 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[i][j] and self.graph[i][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[i][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[i][j] is False and self.graph[i][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)}
...