maths.ear_clipping_polygon_triangulation

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

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

Functions

cross_product(→ float)	This function computes the product of two vectors, with 3 points.
direction(→ str)	Determine the orientation (clockwise or counterclockwise) of a polygon defined
is_convex(→ bool)	Determine with the ccw, if 3 points are convex.
is_ear(→ bool)	This function determines whether three points form an ear.
is_point_inside_triangle(→ bool)	Determine whether a given point is located inside a triangle
triangulate_polygon(→ list[list[tuple[float, float]]])	Triangulate a polygon and provide the points of the resulting triangles.

Module Contents

maths.ear_clipping_polygon_triangulation.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

maths.ear_clipping_polygon_triangulation.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’

maths.ear_clipping_polygon_triangulation.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

maths.ear_clipping_polygon_triangulation.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

maths.ear_clipping_polygon_triangulation.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

maths.ear_clipping_polygon_triangulation.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)]]