import sys
import math
import numpy
import random
from PyQt5.QtCore import Qt, QPoint, QRectF
from PyQt5.QtGui import QPainter, QPen, QBrush
from PyQt5.QtWidgets import QMainWindow, QWidget, QApplication


class MyMainWindow(QMainWindow):
    def __init__(self):
        super().__init__()
        self.setWindowTitle("Построение выпуклых многоугольников")
        self.setGeometry(180, 100, 600, 600)  # начало в экр., ширина, высота
        palette = self.palette()
        palette.setColor(self.backgroundRole(), Qt.white)
        self.setPalette(palette)
        self.form_widget = MyFormWidget()
        self.setCentralWidget(self.form_widget)


class MyFormWidget(QWidget):
    def __init__(self):
        super().__init__()
        self.poly_1_true = {'bottom1': [(200, 200, 0), (250, 150, 50), (100, 200, 0)],  # bottom
                            'back1': [(250, 150, 50), (150, 100, 0), (100, 200, 0)],  # back
                            'right1': [(200, 200, 0), (250, 150, 50), (150, 100, 0)],  # right
                            'front1': [(100, 200, 0), (200, 200, 0), (150, 100, 0)]}  # front

        self.poly_2_true = {'left2': [(200, 150, 0), (200, 50, 0), (250, 20, 100), (250, 120, 100)],  # left
                            'bottom2': [(200, 150, 0), (300, 150, 0), (350, 120, 100), (250, 120, 100)],  # bottom
                            'back2': [(350, 120, 100), (350, 20, 100), (250, 20, 100), (250, 120, 100)],  # back
                            'top2': [(200, 50, 0), (300, 50, 0), (350, 20, 100), (250, 20, 100)],  # top
                            'right2': [(300, 50, 0), (300, 150, 0), (350, 120, 100), (350, 20, 100)],  # right
                            'front2': [(200, 150, 0), (200, 50, 0), (300, 50, 0), (300, 150, 0)]}  # front

    def paintEvent(self, QPaintEvent):
        self.qp = QPainter()
        self.qp.begin(self)
        self.y_segments = {}
        self.side_color = {}
        self.min_y, self.max_y = self.get_min_max_y()
        self.find_segment_for_y()
        self.set_color()
        self.segments_painter()
        self.qp.end()

    def get_vertex(self, poly):
        vertex = set()
        for side in poly.keys():
            for x in poly[side]:
                vertex.add(x)
        return [*vertex]

    def local_min_max_y(self, vertex):
        return min(v[1] for v in vertex), max(v[1] for v in vertex)

    def get_min_max_y(self):
        poly_vert_1 = self.get_vertex(self.poly_1_true)
        poly_vert_2 = self.get_vertex(self.poly_2_true)
        y_min_1, y_max_1 = self.local_min_max_y(poly_vert_1)
        y_min_2, y_max_2 = self.local_min_max_y(poly_vert_2)
        return min(y_min_1, y_min_2), max(y_max_1, y_max_2)

    def find_bones(self, side):
        return [(side[i], side[i - 1]) for i in range(len(side))]

    def get_bones_intersection(self, y, bones):
        bones_res = []
        for v1, v2 in bones:
            if v1[1] <= y <= v2[1] or v2[1] <= y <= v1[1]:
                bones_res.append((v1, v2))
        return bones_res

    def get_equa_bones(self, bone):
        # представление ребра в виде уравнений
        x1, y1, z1 = bone[0]
        x2, y2, z2 = bone[1]
        p = (x2-x1, y2-y1, z2-z1) # == M направляющий вектор
        return bone[0], p

    def find_inters_y_bone(self, y, bone):
        # ищем координаты x, z точек пересечения у и ребер
        coords, p = self.get_equa_bones(bone)
        if p[0] and p[1] and p[2]:
            x = round(p[0]/p[1]*(y-coords[1]) + coords[0])
            z = round(p[2]/p[1]*(y-coords[1]) + coords[2])
            return x, z
        elif not p[0] and not p[2]:
            return coords[0], coords[2]
        elif not p[0]:
            x = coords[0]
            z = round(p[2] / p[1] * (y - coords[1]) + coords[2])
            return x, z
        elif not p[2]:
            x = round(p[0] / p[1] * (y - coords[1]) + coords[0])
            z = coords[2]
            return x, z

    def get_special_segment_inters(self, y, bone):
        end1, end2 = (), ()
        if bone[0][1] == y == bone[1][1]:
            x1 = min(bone[0][0], bone[1][0])  # первый конец по х
            x2 = max(bone[0][0], bone[1][0]) # второй
            z1 = min(bone[0][2], bone[1][2])
            z2 = max(bone[0][2], bone[1][2])
            return (x1, z1), (x2, z2)
        return end1, end2

    def find_equal_y_x_z_coord(self, y, bones):
        for bone in bones:
            if y == bone[0][1]:
                return bone[0][0], bone[0][2]
            if y == bone[1][1]:
                return bone[1][0], bone[1][2]
        return -1, -1

    def find_polygon_segment(self, y, polygon):
        # return dict of {((x1, z1), (x2, z2)): 'bottom1' ...
        segm_side = {}
        for name_side in polygon:  # набираем точки на конкретной плоскости Оxz для у
            pre_inters_points = set()
            y_min, y_max = self.local_min_max_y(polygon[name_side])
            if y < y_min or y > y_max:
                continue
            if (y_min < y < y_max):
                # y точно внутри грани
                # нужно найти пересечения у с ребрами, которые задаются началом и концом и уравнением
                bones = self.find_bones(polygon[name_side])
                need_bones = self.get_bones_intersection(y, bones)
                for bone in need_bones:
                    x, z = self.find_inters_y_bone(y, bone) # x, z
                    pre_inters_points.add((x, z))
            else:
                # попали либо в ребро, либо в вершину
                # нужно определить, во что конкретно
                bones = self.find_bones(polygon[name_side])
                flag_found = False
                for bone in bones:  # ищем отрезки
                    end1, end2 = self.get_special_segment_inters(y, bone)
                    if end1 and end2:
                        pre_inters_points.add(end1)
                        pre_inters_points.add(end2)
                        flag_found = True
                    if flag_found:
                        break
                if not flag_found:  # не нашли отрезки, ищем вершины
                    x, z = self.find_equal_y_x_z_coord(y, bones)
                    if x > -1 and z > -1:
                        pre_inters_points.add((x, z))
            if pre_inters_points:
                if len(pre_inters_points) == 2:
                    inters_points = [x for x in pre_inters_points]
                    if inters_points[0] not in segm_side.keys():
                        segm_side[inters_points[0]] = [name_side] # дб две точки пересечения с коорд x и z
                    else:
                        segm_side[inters_points[0]].append(name_side)
                    if inters_points[1] not in segm_side.keys():
                        segm_side[inters_points[1]] = [name_side] # дб две точки пересечения с коорд x и z
                    else:
                        segm_side[inters_points[1]].append(name_side)
                elif len(pre_inters_points) == 1:
                    inters_points = [x for x in pre_inters_points]
                    if inters_points[0] not in segm_side.keys():
                        segm_side[inters_points[0]] = [name_side]  # дб две точки пересечения с коорд x и z
                    else:
                        segm_side[inters_points[0]].append(name_side)
        return segm_side

    def get_segments(self, segm_sides):
        # возвращает словарь отрезок ((), ()): имя грани
        founded_segms = {}
        for vertex in segm_sides.keys():
            sides1 = segm_sides[vertex]
            for side in sides1:
                for vertex_2 in segm_sides.keys():
                    if vertex == vertex_2:
                        continue
                    sides2 = segm_sides[vertex_2]
                    common = list(set(sides1) & set(sides2))
                    if common:
                        ends = (vertex, vertex_2) if vertex[0] < vertex_2[0] else (vertex_2, vertex)
                        founded_segms[ends] = common[0]
        return founded_segms

    def get_segm_eqv(self, segment):
        # return A, C, D for Ax + Cz + D = 0
        x1, y1 = segment[0]
        x2, y2 = segment[1]
        x_dis = x2-x1
        y_dis = y2-y1
        # A = y_dis, C = -x_dis, D = -x1*y_dis+y1*x_dis
        return (y_dis, -x_dis, -x1*y_dis+y1*x_dis)

    def find_2_straights_inters(self, stra1, stra2):
        # point of intersection of 2 straight (use in next)
        main_det = round(numpy.linalg.det([[stra1[0], stra1[1]], [stra2[0], stra2[1]]]))
        if main_det:
            x_det = round(numpy.linalg.det([[-stra1[2], stra1[1]], [-stra2[2], stra2[1]]]))
            z_det = round(numpy.linalg.det([[stra1[0], -stra1[2]], [stra2[0], -stra2[2]]]))
            x_c = int(round(x_det / main_det))
            z_c = int(round(z_det / main_det))
            x_c_i = 0 if x_c == -0 else x_c
            z_c_i = 0 if z_c == -0 else z_c
            return x_c_i, z_c_i
        return None

    def is_between(self, end_p_1, end_p_2, point):
        return (end_p_1[0] <= point[0] <= end_p_2[0] or end_p_2[0] <= point[0] <= end_p_1[0]) and \
               (end_p_1[1] <= point[1] <= end_p_2[1] or end_p_2[1] <= point[1] <= end_p_1[1])

    def find_all_straights_intersections(self, straights, straights_with_ends, segm_on_side):
        # ищем все точки пересечения
        intersections = {}
        for i in range(len(straights)):
            for j in range(len(straights)):
                inter_v = self.find_2_straights_inters(straights[i], straights[j])
                if inter_v:
                    a, b = straights_with_ends[straights[i]]
                    if self.is_between(a, b, inter_v):
                        c, d = straights_with_ends[straights[j]]
                        if self.is_between(c, d, inter_v):
                            if inter_v not in intersections.keys():
                                intersections[inter_v] = [segm_on_side[(a, b)], segm_on_side[(c, d)]]
        return intersections

    def get_segments_intersection(self, segm_on_side):
        # return dict {(140, 0): ['front1', 'back1']...
        segm_eqv = {}  # ((140, 0), (190, 20)): (A, C, D) for Ax + Cz + D = 0
        straights = []
        straights_with_ends = {}
        straights_on_side = {}
        for segm in segm_on_side.keys():
            # segm == ((140, 0), (190, 20))
            eqv = self.get_segm_eqv(segm)
            segm_eqv[segm] = eqv
            straights.append(eqv)
            straights_with_ends[eqv] = segm
            straights_on_side[eqv] = segm_on_side[segm]
        all_plane_points = self.find_all_straights_intersections(straights, straights_with_ends, segm_on_side)
        print('str w ends: ' + str(straights_with_ends))
        print('segm on side: ' + str(segm_on_side))
        print('str on side: ' + str(straights_on_side))
        return all_plane_points, straights_with_ends, segm_on_side, straights_on_side

    def collect_z_for_x(self, x, stra_w_ends, stra_on_side):
        z_set = set()
        # z_stra_dict = {}
        z_stra_dict_side = {}
        for stra in stra_w_ends.keys():
            if stra_w_ends[stra][0][0] <= x <= stra_w_ends[stra][1][0]:
                try:
                    z_for_x = -round((stra[0] * x + stra[2]) / stra[1])
                    z_set.add(z_for_x)
                    if not z_for_x in z_stra_dict_side.keys():
                        # z_stra_dict[z_for_x] = [stra]
                        z_stra_dict_side[z_for_x] = [stra_on_side[stra]]
                    else:
                        # z_stra_dict[z_for_x].append(stra)
                        z_stra_dict_side[z_for_x].append(stra_on_side[stra])
                except ZeroDivisionError:
                    continue
        return z_set, z_stra_dict_side

    def get_segment_for_paint_with_side(self, points, stra_w_ends, stra_on_side):
        segments_on_side = {}
        for i in range(len(points)-1):
            x1 = points[i][0]
            x2 = points[i+1][0]
            if x1 == x2:
                continue
            z1_set, z1_stra_dict_side = self.collect_z_for_x(x1, stra_w_ends, stra_on_side)
            z2_set, z2_stra_dict_side = self.collect_z_for_x(x2, stra_w_ends, stra_on_side)
            z1_list = [z for z in z1_set]
            z2_list = [z for z in z2_set]
            z1_list.sort()
            z2_list.sort()
            z1_p = -1
            z2_p = -1
            flag_end = False
            common_stra = []
            for tz1 in z1_list:
                for tz2 in z2_list:
                    common_stra = list(set(z1_stra_dict_side[tz1]) & set(z2_stra_dict_side[tz2]))
                    if common_stra:
                        z1_p = tz1
                        z2_p = tz2
                        flag_end = True
                        break
                if flag_end:
                    break
            if z1_p > -1 and z2_p > -1:
                segments_on_side[(x1, x2)] = common_stra
        return segments_on_side

    def get_segment_one_vertex(self, s_vertex, segm_side_vertex, segm_sides, s_ends):
        segments_res = {}
        x_min = min(p[0] for p in s_ends)
        x_max = max(p[0] for p in s_ends)
        if s_vertex[0][0] < x_min or s_vertex[0][0] > x_max:
            segments_res[(s_vertex[0][0], s_vertex[0][0])] = segm_side_vertex[s_vertex[0]][0]
        for p_end in [end for end in s_ends if end[0] == x_min or end[0] == x_max]:
            if s_vertex[0][0] == p_end[0]:
                if s_vertex[0][1] > p_end[1]:
                    segments_res[(s_vertex[0][0], s_vertex[0][0])] = segm_side_vertex[s_vertex[0]][0]
        # критические случаи, когда точка совсем вне отрезков и на границе максимальных закончились
        # нужно достроить оставшийся кусок, где была больше чем 1 точка
        segmes_on_side = self.get_segments(segm_sides)
        vertex_on_side, str_w_ends, segm_on_side, str_on_side = self.get_segments_intersection(segmes_on_side)  # ALL vertex on plane with side DICT!
        all_points = [p for p in vertex_on_side.keys()]
        all_points.sort()
        normal_segment_res = self.get_segment_for_paint_with_side(all_points, str_w_ends, str_on_side)  # seems to dict {(x1, x2): side...
        for x1x2 in normal_segment_res.keys():
            segments_res[x1x2] = normal_segment_res[x1x2]
        return segments_res

    def find_segments(self, segm_sides_1, segm_sides_2):
        # ищет отрезки для отрисовки
        segments = {}  # dict: {(x1, x2): side_name...
        s_ends_1 = [point for point in segm_sides_1.keys()]
        s_ends_2 = [point for point in segm_sides_2.keys()]
        if len(s_ends_1) == 1 and len(s_ends_2) == 1:  # пришли две вершины (напр. пирамиды)
            print('no')
            segments[(s_ends_1[0], s_ends_1[0])] = segm_sides_1[0]
            segments[(s_ends_2[0], s_ends_2[0])] = segm_sides_2[0]
        elif len(s_ends_1) == 1:  # первые сегменты - вершина, вторые - норм
            print('yes')
            tmp_segm = self.get_segment_one_vertex(s_ends_1, segm_sides_1, segm_sides_2, s_ends_2)
            for xx in tmp_segm.keys():
                segments[xx] = tmp_segm[xx]
        elif len(s_ends_2) == 1:  # первые сегменты - норм, вторые - вершина
            print('not again')
            tmp_segm = self.get_segment_one_vertex(s_ends_2, segm_sides_2, segm_sides_1, s_ends_1)
            for xx in tmp_segm.keys():
                segments[xx] = tmp_segm[xx]
        else:  # оба сегмента - норм
            all_points_set = set([p for p in segm_sides_1.keys()] + [p for p in segm_sides_2.keys()])
            all_points = [p for p in all_points_set]
            all_points.sort()
            all_segm_sides = {}
            for p in segm_sides_1.keys():
                all_segm_sides[p] = segm_sides_1[p]
            for p in segm_sides_2.keys():
                all_segm_sides[p] = segm_sides_2[p]
            segmes_on_side = self.get_segments(all_segm_sides)
            _, str_w_ends, _, str_on_side = self.get_segments_intersection(segmes_on_side)
            tmp_segm = self.get_segment_for_paint_with_side(all_points, str_w_ends, str_on_side)
            for xx in tmp_segm.keys():
                segments[xx] = tmp_segm[xx]
        return segments

    def find_segment_for_y(self):
        # segments_pro = {}
        for y in range(self.min_y, self.max_y):
            segm_sides_poly_1 = self.find_polygon_segment(y, self.poly_1_true)
            segm_sides_poly_2 = self.find_polygon_segment(y, self.poly_2_true)
            print('ssp_1' + str(segm_sides_poly_1))
            print('ssp_2' + str(segm_sides_poly_2))
            self.y_segments[y] = self.find_segments(segm_sides_poly_1, segm_sides_poly_2)

    def set_color(self):
        d_color = {1: Qt.darkYellow, 2: Qt.darkRed, 3: Qt.darkCyan, 4: Qt.darkGreen,
                   5: Qt.darkBlue, 6: Qt.darkGray, 7: Qt.darkMagenta, 8: Qt.black, 9: Qt.blue,
                   10: Qt.red, 11: Qt.green}
        for side in self.poly_1_true:
            n_color = random.randrange(1, 11)
            self.side_color[side] = d_color[n_color]
        for side in self.poly_2_true:
            n_color = random.randrange(1, 11)
            self.side_color[side] = d_color[n_color]

    def segments_painter(self):
        for y in self.y_segments.keys():
            for x1, x2 in self.y_segments[y]:
                self.qp.setPen(QPen(self.side_color[self.y_segments[y][(x1, x2)][0]], 2))
                p1 = QPoint(x1, y)
                p2 = QPoint(x2, y)
                self.qp.drawLine(p1, p2)


if __name__ == '__main__':
    app = QApplication(sys.argv)
    window = MyMainWindow()
    window.show()
    sys.exit(app.exec_())