"""
Contains the Polyogn class.

:Authors:
    - <NAME> (wmboyles)
"""

from numpy import ndarray
from functools import cmp_to_key
from math import pi, atan2

from .point import point
from .utils import orient, lex_compare, segments_cross, EPSILON, PRECISION


class Polygon:
    """
    A Polygon is a sequence of points in :math:`\mathbb{R}^2`.
    Edges are the convex closure of subsequent vertices.
    Each edge connects two vertices and each vertex is incident to two edges.
    """

    def __init__(self, points: list[ndarray]):
        """
        Create a new Polygon from a list of points.

        :param list[numpy.ndarray] points: A list of points defining the
            polygon.
        """

        self.points = points

    def __len__(self) -> int:
        """
        :return: The numer of points in the polygon
        :rtype: int
        """

        return len(self.points)

    def __getitem__(self, index: int) -> ndarray:
        """
        Gets a point in the polygon by index. point 0 is the name as point n,
        where n is the number of points in the polygon.

        :param int index: Index of point in poolygon, modulo n
        :return: The indexed point in the polygon.
        :rtype: numpy.ndarray
        """

        return self.points[index % len(self)]

    def __iter__(self):
        """
        :return: An iterator over the polygon's points
        :rtype: iterator
        """

        return iter(self.points)

    def __eq__(self, other: "Polygon") -> bool:
        """
        A two polygons A and B are equal iff their point sequences are a cyclic
        permutation of one another.

        :param Polygon other: Polygon to compare against
        :return: True iff this and other's points differ by a cyclic
            permutation, else False.
        :rtype: bool
        """

        n, m = len(self), len(other)
        if n != m:
            return False
        elif n == m == 0:
            return True

        for i in range(len(self)):
            j = 0

            while i < len(self) or j < len(other):
                if all(self[i] == other[j]):
                    i += 1
                    j += 1
                else:
                    break

            if i >= len(self) and j >= len(other):
                return True

        return False

    def equal_up_to_translation(self, other: "Polygon") -> bool:
        """
        A polygon :math:`A` is equal to a polygon :math:`B` up to translation
        iff there is some translation :math:`d` such that :math:`A = B + d`.

        :param Polygon other: Polygon to compare against
        :return: True if this polygon and other are equal to to translation,
            where equal is defined by the
            :func:`src.data_structures.polygon.Polygon.__eq__` method.
        :rtype: bool
        """

        if len(self) == len(other) == 0:
            return True

        # Find the leftmost point in self and other. These must correspond
        self_leftmost = min(self.points, key=cmp_to_key(lex_compare))
        other_leftmost = min(other.points, key=cmp_to_key(lex_compare))

        # Calculate and perform the translation that's needed
        translation = self_leftmost - other_leftmost
        other_translated = Polygon(other.points + translation)

        # Check if this translated polygon is the same as self
        return self == other_translated

    def __contains__(self, p: ndarray) -> bool:
        """
        Check if a point is contained inside a polygon.
        For simple polygons, this follows our intuition about what "inside"
        would mean: within the finite area part of the plane. We extend this
        idea to non-simple polygons by using the "ray casting" rule: If a ray
        from our query point off to infinity in any direction crosses the
        boundary edges of the polygon an odd number of times, the point is
        inside the polygon.
        """

        if len(self) == 0:
            return False
        if any(all(p == pt) for pt in self.points):
            return True

        # Find max x and max y values in the polygon
        max_x = max(abs(pt[0]) for pt in self.points)
        max_y = max(abs(pt[1]) for pt in self.points)

        # Create a far-away point we know is outside the polygon.
        # This simulates an infinite ray.
        far = point(2 * max_x - EPSILON, 2 * max_y + EPSILON, z=0)

        inside = False
        for i in range(len(self)):
            a, b = self[i], self[i + 1]

            # Perform a intersecting segments test
            # If segments intersect, then the ray crossed the polygon
            if segments_cross(p, far, a, b):
                inside = not inside

        return inside

    # Polygon is convex if walking around the polygon if both are true
    # 1) All turns in the same direction
    # 2) Sum of angle changes in the turn is -/+ 2pi, depending on cw or ccw walk
    def is_convex(self) -> bool:
        """
        A simple polygon is convex iff any line with both endpoints in or on
        the polygon is completely contained in the polygon.

        :return: True if this polygon is convex, else False
        :rtype: bool
        """

        # All triangles are convex; all colinear points are convex
        if len(self) <= 3:
            return True

        # Find the direction of the first turn
        for i in range(len(self)):
            orientation = orient(self[i - 1], self[i], self[i + 1])
            if orientation != 0:
                break
        # if not turns then it must be convex b/c it's just a line
        if orientation == 0:
            return True

        prev, cur = self[-2], self[-1]
        new_direction = atan2(cur[1] - prev[1], cur[0] - prev[0])
        angle_sum = 0
        for i, point in enumerate(self.points):
            prev, cur = cur, point
            old_direction, new_direction = new_direction, atan2(
                cur[1] - prev[1], cur[0] - prev[0]
            )

            # keep angle in (-pi, pi]
            angle = new_direction - old_direction
            if angle < -pi:
                angle += 2 * pi
            elif angle > pi:
                angle -= 2 * pi

            # if our orientation changes, then we found a "dent" ==> not convex
            if orientation * angle < 0:
                return False

            angle_sum += angle

        # if we turned exactly 2pi randians, then the polygon was convex
        return abs(round(angle_sum / (2 * pi), PRECISION)) == 1

    # Simple O(n^2)
    # Look at all pairs of line segments which don't have any points in common
    # If any cross, then the polygon isn't simple
    def is_simple(self) -> bool:
        """
        A polygon is simple if none of its edges cross each other.

        :return: True iff this polygon is simple, else False.
        :rtype: bool
        """

        n = len(self)

        for i in range(n):
            a, b = self[i], self[i + 1]

            for j in range(i + 1, n):
                c, d = self[j], self[j + 1]

                # If the points are all colinear, see if the segments overlap
                if orient(c, d, a) == orient(c, d, b) == 0:
                    ac = lex_compare(a, c)
                    ad = lex_compare(a, d)
                    bd = lex_compare(b, d)

                    # if ad != bd, then d is between a and b
                    # if ad != ac, then a is between c and d
                    if not (ac == ad == bd):
                        return False

                # If we're looking at 4 distinct points, and they are mutually on different line sides
                elif i not in {j - 1, (j + 1) % n} and segments_cross(a, b, c, d):
                    return False

        return True

"""
Contains the Polyogn class.

:Authors:
    - <NAME> (wmboyles)
"""

from numpy import ndarray
from functools import cmp_to_key
from math import pi, atan2

from .point import point
from .utils import orient, lex_compare, segments_cross, EPSILON, PRECISION


class Polygon:
    """
    A Polygon is a sequence of points in :math:`\mathbb{R}^2`.
    Edges are the convex closure of subsequent vertices.
    Each edge connects two vertices and each vertex is incident to two edges.
    """

    def __init__(self, points: list[ndarray]):
        """
        Create a new Polygon from a list of points.

        :param list[numpy.ndarray] points: A list of points defining the
            polygon.
        """

        self.points = points

    def __len__(self) -> int:
        """
        :return: The numer of points in the polygon
        :rtype: int
        """

        return len(self.points)

    def __getitem__(self, index: int) -> ndarray:
        """
        Gets a point in the polygon by index. point 0 is the name as point n,
        where n is the number of points in the polygon.

        :param int index: Index of point in poolygon, modulo n
        :return: The indexed point in the polygon.
        :rtype: numpy.ndarray
        """

        return self.points[index % len(self)]

    def __iter__(self):
        """
        :return: An iterator over the polygon's points
        :rtype: iterator
        """

        return iter(self.points)

    def __eq__(self, other: "Polygon") -> bool:
        """
        A two polygons A and B are equal iff their point sequences are a cyclic
        permutation of one another.

        :param Polygon other: Polygon to compare against
        :return: True iff this and other's points differ by a cyclic
            permutation, else False.
        :rtype: bool
        """

        n, m = len(self), len(other)
        if n != m:
            return False
        elif n == m == 0:
            return True

        for i in range(len(self)):
            j = 0

            while i < len(self) or j < len(other):
                if all(self[i] == other[j]):
                    i += 1
                    j += 1
                else:
                    break

            if i >= len(self) and j >= len(other):
                return True

        return False

    def equal_up_to_translation(self, other: "Polygon") -> bool:
        """
        A polygon :math:`A` is equal to a polygon :math:`B` up to translation
        iff there is some translation :math:`d` such that :math:`A = B + d`.

        :param Polygon other: Polygon to compare against
        :return: True if this polygon and other are equal to to translation,
            where equal is defined by the
            :func:`src.data_structures.polygon.Polygon.__eq__` method.
        :rtype: bool
        """

        if len(self) == len(other) == 0:
            return True

        # Find the leftmost point in self and other. These must correspond
        self_leftmost = min(self.points, key=cmp_to_key(lex_compare))
        other_leftmost = min(other.points, key=cmp_to_key(lex_compare))

        # Calculate and perform the translation that's needed
        translation = self_leftmost - other_leftmost
        other_translated = Polygon(other.points + translation)

        # Check if this translated polygon is the same as self
        return self == other_translated

    def __contains__(self, p: ndarray) -> bool:
        """
        Check if a point is contained inside a polygon.
        For simple polygons, this follows our intuition about what "inside"
        would mean: within the finite area part of the plane. We extend this
        idea to non-simple polygons by using the "ray casting" rule: If a ray
        from our query point off to infinity in any direction crosses the
        boundary edges of the polygon an odd number of times, the point is
        inside the polygon.
        """

        if len(self) == 0:
            return False
        if any(all(p == pt) for pt in self.points):
            return True

        # Find max x and max y values in the polygon
        max_x = max(abs(pt[0]) for pt in self.points)
        max_y = max(abs(pt[1]) for pt in self.points)

        # Create a far-away point we know is outside the polygon.
        # This simulates an infinite ray.
        far = point(2 * max_x - EPSILON, 2 * max_y + EPSILON, z=0)

        inside = False
        for i in range(len(self)):
            a, b = self[i], self[i + 1]

            # Perform a intersecting segments test
            # If segments intersect, then the ray crossed the polygon
            if segments_cross(p, far, a, b):
                inside = not inside

        return inside

    # Polygon is convex if walking around the polygon if both are true
    # 1) All turns in the same direction
    # 2) Sum of angle changes in the turn is -/+ 2pi, depending on cw or ccw walk
    def is_convex(self) -> bool:
        """
        A simple polygon is convex iff any line with both endpoints in or on
        the polygon is completely contained in the polygon.

        :return: True if this polygon is convex, else False
        :rtype: bool
        """

        # All triangles are convex; all colinear points are convex
        if len(self) <= 3:
            return True

        # Find the direction of the first turn
        for i in range(len(self)):
            orientation = orient(self[i - 1], self[i], self[i + 1])
            if orientation != 0:
                break
        # if not turns then it must be convex b/c it's just a line
        if orientation == 0:
            return True

        prev, cur = self[-2], self[-1]
        new_direction = atan2(cur[1] - prev[1], cur[0] - prev[0])
        angle_sum = 0
        for i, point in enumerate(self.points):
            prev, cur = cur, point
            old_direction, new_direction = new_direction, atan2(
                cur[1] - prev[1], cur[0] - prev[0]
            )

            # keep angle in (-pi, pi]
            angle = new_direction - old_direction
            if angle < -pi:
                angle += 2 * pi
            elif angle > pi:
                angle -= 2 * pi

            # if our orientation changes, then we found a "dent" ==> not convex
            if orientation * angle < 0:
                return False

            angle_sum += angle

        # if we turned exactly 2pi randians, then the polygon was convex
        return abs(round(angle_sum / (2 * pi), PRECISION)) == 1

    # Simple O(n^2)
    # Look at all pairs of line segments which don't have any points in common
    # If any cross, then the polygon isn't simple
    def is_simple(self) -> bool:
        """
        A polygon is simple if none of its edges cross each other.

        :return: True iff this polygon is simple, else False.
        :rtype: bool
        """

        n = len(self)

        for i in range(n):
            a, b = self[i], self[i + 1]

            for j in range(i + 1, n):
                c, d = self[j], self[j + 1]

                # If the points are all colinear, see if the segments overlap
                if orient(c, d, a) == orient(c, d, b) == 0:
                    ac = lex_compare(a, c)
                    ad = lex_compare(a, d)
                    bd = lex_compare(b, d)

                    # if ad != bd, then d is between a and b
                    # if ad != ac, then a is between c and d
                    if not (ac == ad == bd):
                        return False

                # If we're looking at 4 distinct points, and they are mutually on different line sides
                elif i not in {j - 1, (j + 1) % n} and segments_cross(a, b, c, d):
                    return False

        return True

Contains the Polyogn class.  :Authors:     - <NAME> (wmboyles) A Polygon is a sequence of points in :math:`\mathbb{R}^2`.     Edges are the convex closure of subsequent vertices.     Each edge connects two vertices and each vertex is incident to two edges. Create a new Polygon from a list of points.          :param list[numpy.ndarray] points: A list of points defining the             polygon. :return: The numer of points in the polygon         :rtype: int Gets a point in the polygon by index. point 0 is the name as point n,         where n is the number of points in the polygon.          :param int index: Index of point in poolygon, modulo n         :return: The indexed point in the polygon.         :rtype: numpy.ndarray :return: An iterator over the polygon's points         :rtype: iterator A two polygons A and B are equal iff their point sequences are a cyclic         permutation of one another.          :param Polygon other: Polygon to compare against         :return: True iff this and other's points differ by a cyclic             permutation, else False.         :rtype: bool A polygon :math:`A` is equal to a polygon :math:`B` up to translation         iff there is some translation :math:`d` such that :math:`A = B + d`.          :param Polygon other: Polygon to compare against         :return: True if this polygon and other are equal to to translation,             where equal is defined by the             :func:`src.data_structures.polygon.Polygon.__eq__` method.         :rtype: bool # Find the leftmost point in self and other. These must correspond # Calculate and perform the translation that's needed # Check if this translated polygon is the same as self Check if a point is contained inside a polygon.         For simple polygons, this follows our intuition about what "inside"         would mean: within the finite area part of the plane. We extend this         idea to non-simple polygons by using the "ray casting" rule: If a ray         from our query point off to infinity in any direction crosses the         boundary edges of the polygon an odd number of times, the point is         inside the polygon. # Find max x and max y values in the polygon # Create a far-away point we know is outside the polygon. # This simulates an infinite ray. # Perform a intersecting segments test # If segments intersect, then the ray crossed the polygon # Polygon is convex if walking around the polygon if both are true # 1) All turns in the same direction # 2) Sum of angle changes in the turn is -/+ 2pi, depending on cw or ccw walk A simple polygon is convex iff any line with both endpoints in or on         the polygon is completely contained in the polygon.          :return: True if this polygon is convex, else False         :rtype: bool # All triangles are convex; all colinear points are convex # Find the direction of the first turn # if not turns then it must be convex b/c it's just a line # keep angle in (-pi, pi] # if our orientation changes, then we found a "dent" ==> not convex # if we turned exactly 2pi randians, then the polygon was convex # Simple O(n^2) # Look at all pairs of line segments which don't have any points in common # If any cross, then the polygon isn't simple A polygon is simple if none of its edges cross each other.          :return: True iff this polygon is simple, else False.         :rtype: bool # If the points are all colinear, see if the segments overlap # if ad != bd, then d is between a and b # if ad != ac, then a is between c and d # If we're looking at 4 distinct points, and they are mutually on different line sides