maths.ear_clipping_polygon_triangulation
========================================

.. py:module:: maths.ear_clipping_polygon_triangulation

.. autoapi-nested-parse::

   An implementation of the ear clipping method for triangulating a simple polygon.

   Wikipedia : https://en.wikipedia.org/wiki/Polygon_triangulation



Functions
---------

.. autoapisummary::

   maths.ear_clipping_polygon_triangulation.cross_product
   maths.ear_clipping_polygon_triangulation.direction
   maths.ear_clipping_polygon_triangulation.is_convex
   maths.ear_clipping_polygon_triangulation.is_ear
   maths.ear_clipping_polygon_triangulation.is_point_inside_triangle
   maths.ear_clipping_polygon_triangulation.triangulate_polygon


Module Contents
---------------

.. py:function:: cross_product(p1: tuple[float, float], p2: tuple[float, float], p3: tuple[float, float]) -> float

   This function computes the product of two vectors, with 3 points.
   If the vectors are collinear, the output is 0.
   If the three points rotate counterclockwise, the output is positive.
   If three points rotate clockwise, the output is negative.

   >>> cross_product((0, 0), (1, 0), (1.5, 0.5))
   0.5
   >>> cross_product((1.5, 0.5), (1, 1), (1.5, 1.5))
   -0.5
   >>> cross_product((0, 0), (1, 1), (2, 2))
   0


.. py:function:: direction(polygon: list[tuple[float, float]]) -> str

   Determine the orientation (clockwise or counterclockwise) of a polygon defined
   by a list of points.
   >>> direction([(1, 1), (2, 2), (3, 4)])
   'clockwise'
   >>> direction([(1, 1), (2, 2), (3, -1)])
   'counter-clockwise'


.. py:function:: is_convex(point: tuple[float, float], prev_p: tuple[float, float], next_p: tuple[float, float], direction: str) -> bool

   Determine with the ccw, if 3 points are convex.
   >>> is_convex((1,1), (2, 2), (1, 2), "clockwise")
   True
   >>> is_convex((1,1), (2, 2), (1, 2), "counter-clockwise")
   False
   >>> is_convex((1,1), (2, 2), (3, 3), "clockwise")
   True
   >>> is_convex((1,1), (2, 2), (3, 3), "counter-clockwise")
   True


.. py:function:: is_ear(polygon: list[tuple[float, float]], point_idx: int, direction: str) -> bool

   This function determines whether three points form an ear.

   >>> is_ear([(0, 2), (2, 2), (2,0), (1, 0), (1, 1), (0, 1)], 4,
   ... "counter-clockwise")
   False
   >>> is_ear([(0, 2), (2, 2), (2,0), (1, 0), (1, 1), (0, 1)], 3,
   ... "counter-clockwise")
   True
   >>> is_ear([(0, 3), (2, 2), (3, 0), (3, 3)], 3, "clockwise")
   False
   >>> is_ear([(0, 0), (1, 0), (1, 1), (0, 1)], 0, "clockwise")
   True


.. py:function:: is_point_inside_triangle(p1: tuple[float, float], p2: tuple[float, float], p3: tuple[float, float], test_point: tuple[float, float]) -> bool

   Determine whether a given point is located inside a triangle
   formed by three other points.

   This function calculates the area of both the triangle formed by
   the three input points (p1, p2, p3)
   and the sub-triangles formed by replacing one vertex of the main
   triangle with the test_point.
   If the sum of the areas of the sub-triangles is equal to the area of
   the main triangle, the test_point
   is considered to be inside the triangle. Otherwise, it is considered outside.

   >>> is_point_inside_triangle((0, 0), (0, 2), (2, 0), (3, 3))
   False
   >>> is_point_inside_triangle((0, 0), (0, 2), (2, 0), (1, 1))
   True
   >>> is_point_inside_triangle((0, 0), (2, 1), (2, 0), (1, 1))
   False
   >>> is_point_inside_triangle((0, 0), (2, 1), (2, 0), (2, 0))
   True
   >>> is_point_inside_triangle((0, 0), (1, 1), (2, 0), (1, 0))
   True


.. py:function:: triangulate_polygon(coordinates: list[tuple[float, float]]) -> list[list[tuple[float, float]]]

   Triangulate a polygon and provide the points of the resulting triangles.
   This function takes a list of coordinates that represent the vertices of a polygon.
   It iteratively finds and removes 'ears' from the polygon to create a list
   of triangles that triangulate the entire polygon.
   The order of vertices in the coordinates list is assumed to be
   consistent (either clockwise or counterclockwise).
   The function uses helper functions 'direction' to determine the polygon's
   orientation and 'is_ear' to identify 'ear' vertices.

   Note: The function assumes that the input coordinates form a valid simple polygon.

   >>> triangulate_polygon([(0, 2), (2, 2), (2, 0), (1, 0), (1, 1), (0, 1)])
   [[(0, 1), (0, 2), (2, 2)], [(2, 2), (2, 0), (1, 0)], [(2, 2), (1, 0), (1, 1)], [(0, 1), (2, 2), (1, 1)]]
   >>> triangulate_polygon([(0, 3), (2, 2), (3, 0), (3, 3)])
   [[(3, 3), (0, 3), (2, 2)], [(3, 3), (2, 2), (3, 0)]]
   >>> triangulate_polygon([(0, 0),(2, 0), (1, 1), (2, 2), (0,2)])
   [[(0, 0), (2, 0), (1, 1)], [(0, 2), (0, 0), (1, 1)], [(0, 2), (1, 1), (2, 2)]]