import math
from typing import List


class StandardLine(object):
    """
    A line in a coordinate grid described in standard form (ax + by = c).
    """
    def __init__(self, x_quantifier: float, y_quantifier: float, equates: float):
        """
        A line in a coordinate grid described in standard form (ax + by = c).

        :param x_quantifier: variable a of the equation
        :param y_quantifier: variable b of the equation
        :param equates: variable c of the equation
        """
        self.x_quantifier = x_quantifier
        self.y_quantifier = y_quantifier
        self.equates = equates

    def __str__(self) -> str:
        return f"{self.A}x + {self.B}y = {self.C}"

    @property
    def A(self) -> float:
        return self.x_quantifier

    @property
    def B(self) -> float:
        return self.y_quantifier

    @property
    def C(self) -> float:
        return self.equates


class Coordinate(object):
    """
    A single x or y coordinate that doesn't have a specific value yet.
    """
    def __init__(self, _min: float, _max: float):
        self.min = _min
        self.max = _max

    @property
    def diff(self) -> float:
        return self.max - self.min

    @property
    def center(self) -> float:
        return self.min + self.diff * 0.5


class Vertex(object):
    """
    A Vertex - a point in 2D space described by an x and y value.
    """
    def __init__(self, x: float, y: float):
        """
        A Vertex - a point in 2D space described by an x and y value.

        :param x: the x coordinate of the vertex
        :param y: the y coordinate of the vertex
        """
        self.x = x
        self.y = y

    def __getitem__(self, item) -> float:
        if item == 0:
            return self.x
        elif item == 1:
            return self.y
        else:
            raise IndexError

    def __eq__(self, other) -> bool:
        if isinstance(other, Vertex):
            if self.x == other.x and self.y == other.y:
                return True
            else:
                return False
        else:
            raise AssertionError(f"Cannot compare Vertex to {other.__class__}")

    def __sub__(self, other):
        if isinstance(other, Vertex):
            return Vertex(
                x=self.x - other.x,
                y=self.y - other.y
            )
        elif isinstance(other, int):
            return Vertex(
                x=self.x - other,
                y=self.y - other,
            )
        elif isinstance(other, float):
            return Vertex(
                x=self.x - other,
                y=self.y - other,
            )
        else:
            raise SyntaxError(f"Cannot subtract {other.__class__} from Vertex")

    def __add__(self, other):
        if isinstance(other, Vertex):
            return Vertex(
                x=self.x + other.x,
                y=self.y + other.y
            )
        elif isinstance(other, int):
            return Vertex(
                x=self.x + other,
                y=self.y + other,
            )
        elif isinstance(other, float):
            return Vertex(
                x=self.x + other,
                y=self.y + other,
            )
        else:
            raise SyntaxError(f"Cannot add {other.__class__} to Vertex")

    def __truediv__(self, other):
        if isinstance(other, Vertex):
            return Vertex(
                x=self.x / other.x,
                y=self.y / other.y
            )
        elif isinstance(other, int) or isinstance(other, float):
            return Vertex(
                x=self.x / other,
                y=self.y / other,
            )
        else:
            raise SyntaxError(f"Cannot divide Vertex by {other.__class__}")

    def __abs__(self):
        return Vertex(
            x=abs(self.x),
            y=abs(self.y),
        )

    @property
    def to_tuple(self) -> tuple:
        """
        :return: the vertex represented as an (x, y) tuple
        """
        return tuple([self.x, self.y])

    def distance_to(self, other) -> float:
        """
        A helper method to calculate the distance to another vertex using pythagoras

        :param other: the vertex to calculate the distance to.
        :return: the calculated distance.
        """
        if isinstance(other, Vertex):
            pythagorean_vertex = self - other
            square_distance = pythagorean_vertex.x ** 2 + pythagorean_vertex.y ** 2
            rooted_distance = math.sqrt(square_distance)
            return rooted_distance
        else:
            raise SyntaxError(f"Cannot calculate distance between Vertex and {other.__class__}")

    def __str__(self):
        return f"({self.x},{self.y})"
        
class Edge(object):
    """
    An Edge - a line(AB) in 2D space described by 2 vertices
    """
    def __init__(self, a: Vertex, b: Vertex):
        """
        An Edge - a line in 2D space described by by 2 vertices

        :param a: vertex a of the line
        :param b: vertex b of the line
        """
        self.a = a
        self.b = b

    def __getitem__(self, item) -> Vertex:
        if item == 0:
            return self.a
        elif item == 1:
            return self.b
        else:
            raise IndexError

    def __eq__(self, other) -> bool:
        if isinstance(other, Edge):
            if self.a == other.a and self.b == other.b:
                return True
            elif self.b == other.a and self.a == other.b:
                return True
            return False
        else:
            raise AssertionError(f"Cannot compare Edge to {other.__class__}")

    @property
    def vertices(self) -> List[Vertex]:
        """
        :return: a list containing the edges vertices
        """
        return [self.a, self.b]


class Triangle(object):
    """
    A Triangle represented as 3 vertices a, b, c
    """

    def __init__(self, a: Vertex, b: Vertex, c: Vertex, is_super: bool = False):
        """
        A Triangle represented as as 3 vertices a, b, c

        :param a: vertex a of the triangle
        :param b: vertex b of the triangle
        :param c: vertex c of the triangle
        :param is_super: triangle is a super triangle
        """
        self.a = a
        self.b = b
        self.c = c
        self.is_super = is_super

    def __getitem__(self, item) -> Vertex:
        if item == 0:
            return self.a
        elif item == 1:
            return self.b
        elif item == 2:
            return self.c
        else:
            raise IndexError

    def __eq__(self, other) -> bool:
        if isinstance(other, Triangle):
            if self.a == other.a and self.b == other.b and self.c == other.c:
                return True
            return False
        else:
            raise AssertionError(f"Cannot compare Triangle to {other.__class__}")

    @property
    def ab_center(self) -> Vertex:
        """
        :return: the center vertex of the triangles Edge(AB)
        """
        return (self.a + self.b) / 2

    @property
    def bc_center(self) -> Vertex:
        """
        :return: the center vertex of the triangles Edge(BA)
        """
        return (self.b + self.c) / 2

    @property
    def ca_center(self) -> Vertex:
        """
        :return: the center vertex of the triangles Edge(CA)
        """
        return (self.c + self.a) / 2

    @property
    def ab_edge(self) -> Edge:
        """
        :return: the triangles Edge(AB)
        """
        return Edge(a=self.a, b=self.b)

    @property
    def bc_edge(self) -> Edge:
        """
        :return: the triangles Edge(BA)
        """
        return Edge(a=self.b, b=self.c)

    @property
    def ca_edge(self) -> Edge:
        """
        :return: the triangles Edge(CA)
        """
        return Edge(a=self.c, b=self.a)

    @property
    def vertices(self) -> List[Vertex]:
        """
        :return: a list of all vertices contained in this triangle
        """
        return [self.a, self.b, self.c]

    @property
    def edges(self) -> List[Edge]:
        """
        :return: a list of all edges contained in this triangle
        """
        return [self.ab_edge, self.bc_edge, self.ca_edge]

    @property
    def circumcenter(self) -> Vertex:
        """
        :return: the circumcenter of this triangle
        """
        ab = get_standard_line(p=self.a, q=self.b)
        bc = get_standard_line(p=self.b, q=self.c)

        pb_ab = get_perpendicular_bisector(p=self.a, q=self.b, line=ab)
        pb_bc = get_perpendicular_bisector(p=self.b, q=self.c, line=bc)

        return get_line_intersection(l1=pb_ab, l2=pb_bc)

    @property
    def circumradius(self) -> float:
        """
        :return: the circumradius of this triangle
        """
        return self.circumcenter.distance_to(self.a)

    @property
    def circumcircle(self):
        """
        :return: the circumcircle of this triangle
        """
        return Circle(center=self.circumcenter, radius=self.circumradius)


class Circle(object):
    """
    A Circle described by its center and its radius
    """
    def __init__(self, center: Vertex, radius: float):
        """
        A Circle described by its center and its radius

        :param center: the center of the circle
        :param radius: the radius of the circle
        """
        self.center = center
        self.radius = radius

    def encompasses_vertex(self, vertex: Vertex) -> bool:
        if self.radius >= self.center.distance_to(vertex):
            return True
        else:
            return False

    @property
    def top_left_circumsquare_corner(self):
        return tuple([self.center.x - self.radius, self.center.y - self.radius])

    @property
    def bottom_right_circumsquare_corner(self):
        return tuple([self.center.x + self.radius, self.center.y + self.radius])


def get_standard_line(p: Vertex, q: Vertex) -> StandardLine:
    """
    Create a StandardLine from 2 vertices

    :param p: vertex p of the StandardLine
    :param q: vertex q of the StandardLine
    :return: a StandardLine created from the given 2 vertices
    """

    a = q.y - p.y
    b = p.x - q.x
    c = a * p.x + b * p.y
    return StandardLine(
        x_quantifier=a,
        y_quantifier=b,
        equates=c
    )


def get_perpendicular_bisector(p: Vertex, q: Vertex, line: StandardLine) -> StandardLine:
    mid_point = (p + q) / 2
    c = -line.B * mid_point.x + line.A * mid_point.y
    a = -line.B
    b = line.A
    return StandardLine(
        x_quantifier=a,
        y_quantifier=b,
        equates=c
    )


def get_line_intersection(l1: StandardLine, l2: StandardLine) -> Vertex:
    """
    Get the intersection Vertex of 2 StandardLines

    :param l1: StandardLine l1
    :param l2: StandardLine l2
    :return: the intersection Vertex between l1 and l2
    """
    determinant = l1.A * l2.B - l2.A * l1.B
    if determinant == 0:  # The lines are parallel
        raise ValueError(f"The lines {l1} and {l2} do not intersect.")
    else:
        return Vertex(
            x=(l2.B * l1.C - l1.B * l2.C) / determinant,
            y=(l1.A * l2.C - l2.A * l1.C) / determinant
        )


import math
import random
from typing import List, NoReturn


def _remove_triangles(triangles: List[Triangle], pre_remove: List[Triangle]) -> NoReturn:
    """
    Helper method to remove triangles from triangle list

    :param triangles: the list items should be removed from
    :param pre_remove: the list of items that should be removed from triangles
    :return: nothing. the list is being altered in place.
    """

    for triangle in pre_remove:
        try:
            triangles.remove(triangle)
        except ValueError:
            pass


def scatter_vertices(plane_width: int, plane_height: int, spacing: int, scatter: float) -> List[Vertex]:
    """
    helper method to scatter random vertices on a specified plane.
    Distance is calculated using the given spacing and scatter.

    :param plane_width: the width of the plane.
    :param plane_height: the height of the plane.
    :param spacing: the spacing between the vertices.
    :param scatter: the scatter multiplier amount the spacing differs from its given value.
    :return: vertex list
    """

    vertices: List[Vertex] = []
    x_offset = (plane_width % spacing) / 2
    y_offset = (plane_height % spacing) / 2
    for x in range(math.floor((plane_width / spacing) + 1)):
        for y in range(math.floor((plane_height / spacing) + 1)):
            vertices.append(
                Vertex(
                    x=x_offset + spacing * (x + scatter * (random.random() - 0.5)),
                    y=y_offset + spacing * (y + scatter * (random.random() - 0.5))
                )
            )
    return vertices


def get_super_triangle(vertices: List[Vertex]) -> Triangle:
    """
    Get super triangle for vertices

    :param vertices: the vertices the super triangle should encompass.
    :return: the super triangle.
    """

    x = Coordinate(_min=math.inf, _max=-math.inf)
    y = Coordinate(_min=math.inf, _max=-math.inf)

    for vertex in vertices:
        if vertex.x < x.min:
            x.min = vertex.x
        if vertex.x > x.max:
            x.max = vertex.x
        if vertex.y < y.min:
            y.min = vertex.y
        if vertex.y > y.max:
            y.max = vertex.y

    max_diff = max(x.diff, y.diff)

    return Triangle(
        Vertex(
            x=x.center - 20 * max_diff,
            y=y.center - max_diff
        ),
        Vertex(
            x=x.center,
            y=y.center + 20 * max_diff
        ),
        Vertex(
            x=x.center + 20 * max_diff,
            y=y.center - max_diff
        ),
        is_super=True
    )


def delaunay(vertices: List[Vertex], delete_super_shared: bool = True) -> List[Triangle]:
    """
    Delaunay Triangulate a list of vertices using the Bowyer-Watson algorithm.

    :param vertices: the vertices to triangulate.
    :param delete_super_shared: delete triangles that share vertices with the super triangle
    :return: the list of created triangles.
    """

    # sort vertices by their x-coordinate to improve performance.
    vertices = sorted(vertices, key=lambda vertex: vertex.x)

    # create super triangle from vertices
    super_triangle = get_super_triangle(vertices=vertices)

    # initialise triangle list
    triangles: List[Triangle] = [super_triangle]

    # add super triangle vertices to vertex list
    vertices += super_triangle.vertices

    # initialise triangle removal list
    pre_removed_triangles: List[Triangle] = []

    for vertex in vertices:  # for each vertex

        # initialise list for illegal triangles
        # (triangles whose circumcircle encompasses the vertex)
        illegal_triangles = []

        for triangle in triangles:  # for each triangle
            try:
                # try to create circumcircle
                circumcircle = triangle.circumcircle

                # if the triangle of the current iteration encompasses the vertex
                # -> add triangle to illegal triangles
                if circumcircle.encompasses_vertex(vertex=vertex):
                    illegal_triangles.append(triangle)
            except ValueError:
                # cannot draw circumcircle because the perpendicular bisectors don't intersect
                # -> add the triangle to removal list
                pre_removed_triangles.append(triangle)

        # remove all triangles from triangle list that were added to triangle removal list
        _remove_triangles(triangles=triangles, pre_remove=pre_removed_triangles)

        # initialise shell polygon edge list
        polygon: List[Edge] = []

        # initialise illegal edge list
        illegal_edges = []

        # add all triangle edges from illegal triangles to illegal edges
        for triangle in illegal_triangles:
            illegal_edges += triangle.edges

        for triangle in illegal_triangles:  # for each triangle in illegal triangles
            for edge in triangle.edges:  # for each edge in illegal edges

                # if the edge is unique
                # -> add the edge to the shell polygon
                if illegal_edges.count(edge) == 1:
                    polygon.append(edge)

        # remove all illegal triangles from triangle list
        for triangle in illegal_triangles:
            triangles.remove(triangle)

        for edge in polygon:  # for each edge in shell polygon
            # create new triangles from edge and vertex
            new_triangle = Triangle(
                a=edge.a,
                b=edge.b,
                c=vertex
            )

            # add the newly created triangle to triangle iterator
            triangles.append(new_triangle)

    # delete all triangles that share vertices with the super triangle
    if delete_super_shared:
        for triangle in triangles:  # for each triangle

            # if the triangle is the super triangle
            # -> add the triangle to removal list
            if triangle.is_super:
                pre_removed_triangles.append(triangle)

            for vertex in triangle.vertices:  # for each vertex in the triangle

                # if the super triangle contains this vertex
                # -> remove the triangle
                if vertex in super_triangle.vertices:
                    try:
                        pre_removed_triangles.append(triangle)
                    except ValueError:
                        pass

    # remove all triangles from triangle list that were added to triangle removal list
    _remove_triangles(triangles=triangles, pre_remove=pre_removed_triangles)

    return triangles  # return triangles

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
xs = np.random.randint(20, size=100)
ys = np.random.randint(20, size=100)
tris = delaunay([Vertex(x, y) for x, y in zip(xs, ys)])
fig, ax = plt.subplots()
for tri in tris:
    cs = [(tri.a.x, tri.a.y), (tri.b.x, tri.b.y), (tri.c.x, tri.c.y)]
    p = Polygon(cs, facecolor = 'b')
    
    ax.add_patch(p)

plt.scatter(xs, ys)
plt.show()