ASSIGNMENT_2

import sys
from collections import defaultdict
import numpy as np

# sys.setrecursionlimit(100000)


# TODO Cannot get polygons as expected.

class PolygonsError(Exception):
    pass


class Polygons:
    def __init__(self, file_name):
        self.file_name = file_name
        self.mapping_depth_polygon=defaultdict(list)
        self.all_points={}
        self.mapping_cur_point = {}
        self.mapping_cur_point_reverse = {}
        self.dict_turning_points={}
        self.dict_path = {}
        self.dict_perimeter = {}
        self.dict_area = {}
        self.dict_convex = {}
        self.dict_nb_invariant_rotations = {}
        self.dict_depth = {}
        self.grid = self.parse_file_content()
        self.check_inputs()
        self.parse_file_content()
        self.traverse_graph()
        # self.display_path()
        self.find_turning_points()
        # self.display_turing_points()
        self.perimeter_compute()
        # self.display_perimeter()
        self.area_compute()
        # self.display_area()
        self.convex_analyse()
        # self.display_convex()
        self.nb_rotations_analyse()
        # self.display_nb_of_invariant_rotations()
        self.depth_analyse()
        # self.display_depth()
        # self.print_result()


    def check_inputs(self):
        rows = len(self.grid)
        cols = len(self.grid[0])
        if rows < 2 or rows > 50 or cols < 2 or cols > 50:
            raise PolygonsError("Incorrect input.")
            

        for i in range(rows):
            for j in range(cols):
                if self.grid[i][j] != 0 and self.grid[i][j] != 1:
                    raise PolygonsError("Incorrect input.")
                    

    def parse_file_content(self):
        with open(self.file_name) as file:
            grid = []
            for line in file:
                if line.isspace():
                    continue
                else:
                    digits = line.strip().replace(' ', '')
                    for digit in digits:
                        if digit.isdigit():
                            continue
                        else:
                            raise PolygonsError("Incorrect input.")
                            
                    row = [int(item) for item in digits]
                grid.append(row)
            # 防止出现不是每一行都等长
            next_length, cur_length = len(grid[0]), len(grid[0])
            for item in grid:
                cur_length=len(item)
                if next_length!=cur_length:
                    raise PolygonsError("Incorrect input.")
                next_length=cur_length
            # 防止出现全为0的情况
            # have_one = 0
            # for line in grid:
            #     if line.count(1):
            #         have_one = 1
            #         break
            # if have_one == 0: # if all is 0 
                # raise PolygonsError("Incorrect input.")
        return grid

    def find_polygon(self, x, y):
        # print('x,y',x,y)
        rows = len(self.grid)
        cols = len(self.grid[0])
        start_group = []
        start_direction_group = []
        cur_direction = 1
        direction_dict = {0: (-1, 0), 1: (-1, 1), 2: (0, 1), 3: (1, 1), 4: (1, 0), 5: (1, -1), 6: (0, -1), 7: (-1, -1)}
        directions_list = [key for key in direction_dict.keys()]
        direction_mapping = {0: 5, 1: 6, 2: 7, 3: 0, 4: 1, 5: 2, 6: 3, 7: 4}
        # 找第一个点附近的
        first_direction_list = directions_list[direction_mapping[cur_direction]:] + directions_list[
                                                                                    :direction_mapping[cur_direction]]
        first_direction_list = first_direction_list[::-1]

        for key in first_direction_list:
            cur_x, cur_y = x + direction_dict[key][0], y + direction_dict[key][1]
            if 0 <= cur_x < rows and 0 <= cur_y < cols and self.grid[cur_x][cur_y] == 1:
                start_group.append((cur_x, cur_y))
                start_direction_group.append(key)
        if start_group:
            start_point = start_group[-1]
            # print('start',start_point)
        else:
            raise PolygonsError('Cannot get polygons as expected.')
            
        end_point = (x, y)
        # print('end',end_point)
        if start_direction_group:
            start_direction = start_direction_group[-1]
            # print('start_dir',start_direction)
        else:
            raise PolygonsError('Cannot get polygons as expected.')
            

        def find_path(start, path_reverse):
            path_reverse.append(start)
            if start == (start_point[0], start_point[1]):
                return path_reverse
            return find_path((pre_dict[start][0], pre_dict[start][1]), path_reverse)

        def dfs(x, y, start_direction):
            starting = False
            found = False
            visited.add((x, y))
            visit.append((x, y))
            while found == False and visited:
                if not visit and starting == True:
                    return -1
                v = visit.pop()
                visited.add(v)

                if v == (end_point[0], end_point[1]):
                    found = True
                else:
                    direction_list = directions_list[direction_mapping[start_direction]:] + directions_list[
                                                                                            :direction_mapping[
                                                                                                start_direction]]
                    direction_list = direction_list[::-1]
                    # print('direction_list',direction_list)
                    for key in direction_list:
                        cur_x, cur_y = v[0] + direction_dict[key][0], v[1] + direction_dict[key][1]

                        if 0 <= cur_x < rows and 0 <= cur_y < cols and self.grid[cur_x][cur_y] == 1 and (
                                cur_x, cur_y) not in visited:
                            starting = True
                            pre_dict[(cur_x, cur_y)] = (v[0], v[1])
                            visit.append((cur_x, cur_y))
                            start_direction = key

        visit = []
        visited = set()
        if start_group and start_direction_group:
            pre_dict = {(start_point[0], start_point[1]): (start_point[0], start_point[1])}

            dfs(start_point[0], start_point[1], start_direction)
            path_reverse = find_path((end_point[0], end_point[1]), path_reverse=[])
            path = path_reverse[::-1]
            # print(path)
            for point in path:
                self.grid[point[0]][point[1]] = 0
        return path

    def traverse_graph(self):
        rows = len(self.grid)
        cols = len(self.grid[0])
        for i in range(rows):
            for j in range(cols):
                if self.grid[i][j] == 1:
                    # print(i,j)
                    path = self.find_polygon(i, j)
                    self.dict_path[(i, j)] = path

    #TODO 为什么需要将横纵坐标交换？该死的坐标顺序，我原先的顺序怎么就不行
    def find_turning_points(self):
        for k, v in self.dict_path.items():
            turning_points = []
            n=len(v)
            for idx in range(n):
                p1=v[idx-1]
                p2=v[idx]
                p3=v[(idx+1)%n]
                cross_product=(p2[0] - p1[0]) * (p3[1] - p2[1]) - (
                        p2[1] - p1[1]) * (p3[0] - p2[0])

                if cross_product!=0:
                    turning_points.append(p2)
            # 我也不知道为什么啊，但是输出结果？？？
            if turning_points:
                turning_points.insert(0,turning_points.pop())
            else:
                raise PolygonsError('Cannot get polygons as expected.')
            turning_points=[(y,x) for x,y in turning_points]
            self.dict_turning_points[k]=turning_points


    # def perimeter_compute(self):
    #     for k, v in self.dict_path.items():
    #         value1, value2 = 0, 0
    #         n = len(v)
    #         for idx in range(-1, n - 1):
    #             if v[idx][0] == v[idx + 1][0] or v[idx][1] == v[idx + 1][1]:
    #                 value1 += abs(v[idx + 1][0] - v[idx][0]) + abs(v[idx + 1][1] - v[idx][1])
    #             else:
    #                 value2 += abs(v[idx][0] - v[idx + 1][0])
    #         value1 = round(value1 * 0.4, 1)
    #         if value1 == 0:
    #             value = f'{value2}*sqrt(.32)'
    #         else:
    #             if value2 == 0:
    #                 value = value1
    #             else:
    #                 value = f'{value1} + {value2}*sqrt(.32)'
    #         self.dict_perimeter[k] = value
    def perimeter_compute(self):
        for k, v in self.dict_path.items():
            n=len(v)
            value1,value2=0,0
            for idx1 in range(n):
                idx2 = (idx1 + 1) % n
                if v[idx2][0]==v[idx1][0] or v[idx2][1]==v[idx1][1]: # 位于同一垂直线或水平线
                    cur_value=abs(v[idx2][0]-v[idx1][0])+abs(v[idx2][1]-v[idx1][1])
                    value1+=cur_value
                else:
                    cur_value=abs(v[idx2][0]-v[idx1][0])
                    value2+=cur_value
            value1 = round(value1 * 0.4, 1)
            if value1 == 0:
                value = f'{value2}*sqrt(.32)'
            else:
                if value2 == 0:
                    value = value1
                else:
                    value = f'{value1} + {value2}*sqrt(.32)'
            self.dict_perimeter[k] = value
    
    def area_compute(self):
        for k, v in self.dict_path.items():
            n = len(v)
            area = 0
            for idx1 in range(n):
                idx2 = (idx1 + 1) % n
                cur_area = v[idx1][0] * v[idx2][1] - v[idx2][0] * v[idx1][1]
                area += cur_area
            area = (abs(area) * 0.16) / 2
            self.dict_area[k] = f'{area:.2f}'

    # TODO 三个以下的点无法形成多边形
    def convex_analyse(self):
        def cross_product(p1, p2, p3):
            # 计算叉积
            x1, y1 = p1
            x2, y2 = p2
            x3, y3 = p3
            return (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2)

        for k, v in self.dict_path.items():
            is_Convex = True
            n = len(v)
            if n < 3:
                return False
            for idx1 in range(n):
                idx2, idx3 = (idx1 - 1) % n, (idx1 + 1) % n
                p1, p2, p3 = v[idx1], v[idx2], v[idx3]
                cp = cross_product(p1, p2, p3)
                if cp < 0:
                    is_Convex = False
                    break
            if is_Convex:
                self.dict_convex[k] = 'yes'
            else:
                self.dict_convex[k] = 'no'

    def nb_rotations_analyse(self):
        def generate_grid(v):
            # 找到坐标的范围
            min_x = min(v, key=lambda x: x[0])[0]
            max_x = max(v, key=lambda x: x[0])[0]
            min_y = min(v, key=lambda x: x[1])[1]
            max_y = max(v, key=lambda x: x[1])[1]

            # 创建一个全零矩阵，用于存储01矩阵
            matrix = np.zeros((max_y - min_y + 1, max_x - min_x + 1), dtype=int)

            # 将给定坐标点的位置设置为1
            for x, y in v:
                matrix[y - min_y, x - min_x] = 1
            return matrix

        for k, v in self.dict_path.items():
            nb_of_invariant = 1
            matrix = generate_grid(v)
            new_matrix0 = np.rot90(matrix)
            if np.array_equal(new_matrix0, matrix):
                nb_of_invariant += 1
            new_matrix1 = np.rot90(new_matrix0)
            if np.array_equal(new_matrix1, matrix):
                nb_of_invariant += 1
            new_matrix2 = np.rot90(new_matrix1)
            if np.array_equal(new_matrix2, matrix):
                nb_of_invariant += 1
            self.dict_nb_invariant_rotations[k] = nb_of_invariant

    # def depth_analyse(self):
    #     rows = len(self.grid)
    #     cols = len(self.grid[0])
    #     new_grid = [[0 for _ in range(cols)] for _ in range(rows)]

    #     def generate_component_graph():
    #         cnt = 1
    #         for k, v in self.dict_path.items():
    #             for item in v:
    #                 new_grid[item[0]][item[1]] = cnt
    #             self.mapping_cur_point[k] = cnt
    #             cnt += 1

    #     generate_component_graph()

    #     for ke, va in self.mapping_cur_point.items():
    #         self.mapping_cur_point_reverse[va] = ke

    #     def display_component_graph():
    #         for i in range(rows):
    #             for j in range(cols):
    #                 print(new_grid[i][j], end='\t')
    #             print()

    #     # display_component_graph()

    #     def find_way_out(cur_point):
    #         '''
    #         对于cur_point 上下左右遍历下一个 0或者自己的点
    #         '''
    #         distinct = []
    #         direction_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    #         obstruct = False
    #         found = False
    #         visited = set()
    #         visit = []
    #         visited.add((cur_point[0], cur_point[1]))
    #         visit.append((cur_point[0], cur_point[1]))
    #         while found == False and visited:
    #             if visit:
    #                 v = visit.pop()
    #             else:
    #                 min_depth = 0
    #                 if self.mapping_cur_point_reverse[new_grid[distinct[0][0]][distinct[0][1]]] in self.dict_depth:
    #                     min_depth = self.dict_depth[
    #                         self.mapping_cur_point_reverse[new_grid[distinct[0][0]][distinct[0][1]]]]
    #                 else:
    #                     return min_depth
    #                 point_number = set()
    #                 for item0 in distinct:
    #                     if new_grid[item0[0]][item0[1]] != 0:
    #                         if not new_grid[item0[0]][item0[1]] in point_number and self.mapping_cur_point_reverse[
    #                             new_grid[item0[0]][item0[1]]] in self.dict_depth:
    #                             point_number.add(new_grid[item0[0]][item0[1]])
    #                             cur_depth = self.dict_depth[
    #                                 self.mapping_cur_point_reverse[new_grid[item0[0]][item0[1]]]]
    #                             if cur_depth < min_depth:
    #                                 min_depth = cur_depth
    #                 return min_depth + 1
    #             visited.add(v)
    #             # 如果能到达边界，并且未受阻挡
    #             if (v[0] <= 0 or v[0] >= cols or v[1] <= 0 or v[1] >= rows) and obstruct == False:
    #                 return 0
    #             for direction in direction_list:
    #                 cur_x, cur_y = v[0] + direction[0], v[1] + direction[1]
    #                 if 0 <= cur_x < rows and 0 <= cur_y < cols:
    #                     if (new_grid[cur_x][cur_y] == 0 or new_grid[cur_x][cur_y] == self.mapping_cur_point[
    #                         cur_point]) and not (cur_x, cur_y) in visited:
    #                         visit.append((cur_x, cur_y))
    #                     else:
    #                         distinct.append((cur_x, cur_y))

    #     for k, v in self.dict_path.items():
    #         self.dict_depth[k] = find_way_out(k)
    def depth_analyse(self):
        def store_all_points():
            no=1
            for v in self.dict_path.values():
                self.all_points[no]=v
                no+=1

        def inside_or_not(x,y,v):
            n=len(v)
            inside=False
            intersection_x=0
            # 顶点
            first_x,first_y=v[0][0],v[0][1]
            for idx in range(n+1):
                cur_x,cur_y=v[idx%n][0],v[idx%n][1]
                if min(first_y,cur_y)<y<=max(first_y,cur_y) and x<=max(first_x,cur_x):
                    if first_y!=cur_y:
                        intersection_x=first_x+(y-first_y)*(cur_x-first_x)/(cur_y-first_y)
                    if first_x==cur_x or x<=intersection_x:
                        inside=not inside

                first_x,first_y=cur_x,cur_y
            return inside

        store_all_points()
        for k, v in self.dict_path.items():
            cur_depth = 0
            x=v[-1][0]
            y=v[-1][1]
            for idx in self.all_points:
                if inside_or_not(x,y,self.all_points[idx]):
                    cur_depth+=1

            self.dict_depth[k]=cur_depth

    def analyse(self):
        '''
        # self.dict_perimeter
        # self.dict_area
        # self.dict_convex
        # self.dict_nb_invariant_rotations
        # self.dict_depth
        :return:
        '''
        cnt = 1
        for key in self.dict_perimeter.keys():
            print(f"Polygon {cnt}:")
            cnt += 1
            print(f"    Perimeter: {self.dict_perimeter[key]}")
            print(f"    Area: {self.dict_area[key]}")
            print(f"    Convex: {self.dict_convex[key]}")
            print(f"    Nb of invariant rotations: {self.dict_nb_invariant_rotations[key]}")
            print(f"    Depth: {self.dict_depth[key]}")


    def display(self):
        def group_sort():
            for k,v in self.dict_depth.items():
                self.mapping_depth_polygon[v].append(k)
        group_sort()

        rows = len(self.grid)
        cols = len(self.grid[0])
        tex_file_name = self.file_name.split(".")[0]
        with open(f'{tex_file_name}.tex', 'w+') as tex_file:
            print('\\documentclass[10pt]{article}', file=tex_file)
            print('\\usepackage{tikz}', file=tex_file)
            print('\\usepackage[margin=0cm]{geometry}', file=tex_file)
            print('\\pagestyle{empty}', file=tex_file)
            print('', file=tex_file)
            print('\\begin{document}', file=tex_file)
            print('', file=tex_file)
            print('\\vspace*{\\fill}', file=tex_file)
            print('\\begin{center}', file=tex_file)
            print('\\begin{tikzpicture}[x=0.4cm, y=-0.4cm, thick, brown]', file=tex_file)

            print(
                f'\\draw[ultra thick] (0, 0) -- ({cols - 1}, 0) -- ({cols - 1}, {rows - 1}) -- (0, {rows - 1}) -- cycle;\n',
                file=tex_file)

            str_to_float=[float(x) for x in list(self.dict_area.values())]
            if str_to_float:
                max_area=max(str_to_float)
                min_area=min(str_to_float)
            for k,v in self.mapping_depth_polygon.items():
                print(f'% Depth {k}', file=tex_file)
                for item in v:
                    print_line=''
                    for single_item in self.dict_turning_points[item]:
                        print_line += f'({single_item[0]}, {single_item[1]}) -- '
                    if max_area!=min_area:
                        color=int(round((max_area - float(self.dict_area[item])) * 100 / (max_area - min_area),0))
                    else:
                        color=100
                    print(f'\\filldraw[fill=orange!{color}!yellow] {print_line}cycle;', file=tex_file)


            print('\\end{tikzpicture}', file=tex_file)
            print('\\end{center}', file=tex_file)
            print('\\vspace*{\\fill}', file=tex_file)
            print('', file=tex_file)
            print('\\end{document}', file=tex_file)

    def display_path(self):
        for key, value in self.dict_path.items():
            print(key, value)

    def display_turing_points(self):
        for key, value in self.dict_turning_points.items():
            print(key, value)

    def display_perimeter(self):
        for key, value in self.dict_perimeter.items():
            print(key, value)

    def display_area(self):
        for key, value in self.dict_area.items():
            print(key, value)

    def display_convex(self):
        for key, value in self.dict_convex.items():
            print(key, value)

    def display_nb_of_invariant_rotations(self):
        for key, value in self.dict_nb_invariant_rotations.items():
            print(key, value)

    def display_depth(self):
        for key, value in self.dict_depth.items():
            print(key, value)


# if __name__ == '__main__':
# parser = ArgumentParser()
# parser.add_argument('--file', dest = 'file_filename')
# parser.add_argument('-print', action = 'store_true')
# args = parser.parse_args()
# file_name = args.file_filename
# print(file_name)
# polys = Polygons(file_name)
# polys.print_result()
# polys.display()
# polys = Polygons('polys_2.txt')
# polys.print_result()
# polys.display()
# polys = Polygons('polys_3.txt')
# polys.print_result()
# polys.display()
# polys = Polygons('polys_4.txt')
# polys.print_result()
# polys.display()