The Algorithms - Python Python TheAlgorithms/Python

Geometry Algorithms in TheAlgorithms/Python

Four stops from primitive shapes to convex hull algorithms, with cross-product orientation as the shared computational primitive.

4 stops ~10 min Verified 2026-05-05

What you will learn

How Python dataclasses with __post_init__ enforce geometric invariants at construction time
How the Polygon class chains side additions to build arbitrary polygons from validated Side objects
Why the cross product of two vectors determines whether three points make a left turn, right turn, or are collinear
How Graham scan sorts points by polar angle using the cross product as the comparison key
How Jarvis march wraps around the point set by always selecting the most counter-clockwise next point
Why the two convex hull algorithms have different time complexity trade-offs depending on the number of hull points

Prerequisites

Basic understanding of 2D Cartesian coordinates
Familiarity with Python dataclasses and class methods
Knowledge of what a convex hull is conceptually

1 / 4

Geometry primitives: dataclasses enforce invariants at construction time

geometry/geometry.py:11

Python dataclasses with __post_init__ make invalid geometric states unrepresentable at construction, not at use.

The geometry module models shapes through a hierarchy of validated building blocks. Rather than accepting raw floats everywhere and failing at computation time, the design uses dataclasses whose __post_init__ methods enforce geometric invariants immediately after the default __init__ runs. The Angle class requires its degrees field to be a numeric value between 0 and 360 inclusive; any other input raises TypeError before the object is stored anywhere. The Side class (lines 38-75) applies the same pattern: length must be a positive numeric value, angle must be an Angle object, and next_side must be either a Side or None. The doctests document the rejection behavior, which doubles as the test suite for the validation logic. This pattern means a Side or Angle that exists is always valid, eliminating a category of runtime errors downstream.

Key takeaway

Using __post_init__ in a dataclass makes invalid geometric states unrepresentable: construction either succeeds with a valid object or raises immediately.

@dataclass
class Angle:
    """
    An Angle in degrees (unit of measurement)

    >>> Angle()
    Angle(degrees=90)
    >>> Angle(45.5)
    Angle(degrees=45.5)
    >>> Angle(-1)
    Traceback (most recent call last):
        ...
    TypeError: degrees must be a numeric value between 0 and 360.
    >>> Angle(361)
    Traceback (most recent call last):
        ...
    TypeError: degrees must be a numeric value between 0 and 360.
    """

    degrees: float = 90

    def __post_init__(self) -> None:
        if not isinstance(self.degrees, (int, float)) or not 0 <= self.degrees <= 360:
            raise TypeError("degrees must be a numeric value between 0 and 360.")

2 / 4

Polygon: a mutable chain of validated sides with index-safe accessors

geometry/geometry.py:170

Polygon wraps a list of Side objects and exposes only three mutation methods, delegating index bounds checking to the underlying list.

Once the primitive types are validated, the Polygon class composes them into a sequence of Side objects. The design is minimal: sides defaults to an empty list via field(default_factory=list) to avoid the classic mutable-default-argument bug in dataclasses. Three methods provide the only interface to the sides list. add_side appends a Side and returns self, enabling method chaining as shown in the doctest. get_side and set_side delegate directly to list indexing, which means they raise IndexError on out-of-bounds access without any extra guard code. The doctests document both the happy path and the error path. The class is marked abstract in its docstring because the repository also defines concrete subclasses like Rectangle and Square later in the file, each adding computed properties for area and perimeter on top of this validated foundation.

Key takeaway

Polygon uses field(default_factory=list) to avoid the mutable-default bug and delegates bounds checking to the underlying list for get_side and set_side.

@dataclass
class Polygon:
    """
    An abstract class which represents Polygon on a 2D surface.

    >>> Polygon()
    Polygon(sides=[])
    >>> polygon = Polygon()
    >>> polygon.add_side(Side(5)).get_side(0)
    Side(length=5, angle=Angle(degrees=90), next_side=None)
    >>> polygon.get_side(1)
    Traceback (most recent call last):
        ...
    IndexError: list index out of range
    >>> polygon.set_side(0, Side(10)).get_side(0)
    Side(length=10, angle=Angle(degrees=90), next_side=None)
    >>> polygon.set_side(1, Side(10))
    Traceback (most recent call last):
        ...
    IndexError: list assignment index out of range
    """

    sides: list[Side] = field(default_factory=list)

    def add_side(self, side: Side) -> Self:
        """
        >>> Polygon().add_side(Side(5))
        Polygon(sides=[Side(length=5, angle=Angle(degrees=90), next_side=None)])
        """
        self.sides.append(side)

3 / 4

The cross-product orientation test: the primitive that convex hull algorithms share

geometry/graham_scan.py:91

The 2D cross product sign encodes turn direction: positive for counter-clockwise, negative for clockwise, zero for collinear.

Both Graham scan and Jarvis march need to answer the same question at every step: given three ordered points, does the path turn left, turn right, or go straight? The signed cross product of the two edge vectors answers this. The expression on lines 108-110 computes (A - self) cross (B - A) where the 2D cross product is the scalar dx1 dy2 - dy1 dx2. A positive result means a counter-clockwise turn, a negative result means clockwise, and zero means collinear. The doctest encodes all three cases: origin to (1,0) to (1,1) returns 1.0, to (1,-1) returns -1.0, and to (2,0) returns 0.0. Both hull algorithms in this category directory rely on consecutive_orientation without reimplementing it, showing how one geometric primitive composes cleanly into different algorithms.

Key takeaway

The signed 2D cross product (A - O) x (B - A) encodes turn direction: positive for counter-clockwise, negative for clockwise, zero for collinear.

    def consecutive_orientation(self, point_a: Point, point_b: Point) -> float:
        """
        Calculate the cross product of vectors (self -> point_a) and
        (point_a -> point_b).

        Returns:
        - Positive value: counter-clockwise turn
        - Negative value: clockwise turn
        - Zero: collinear points

        >>> Point(0, 0).consecutive_orientation(Point(1, 0), Point(1, 1))
        1.0
        >>> Point(0, 0).consecutive_orientation(Point(1, 0), Point(1, -1))
        -1.0
        >>> Point(0, 0).consecutive_orientation(Point(1, 0), Point(2, 0))
        0.0
        """
        return (point_a.x - self.x) * (point_b.y - point_a.y) - (point_a.y - self.y) * (
            point_b.x - point_a.x
        )

4 / 4

Jarvis march: gift-wrapping the hull by always selecting the most counter-clockwise next point

geometry/jarvis_march.py:44

Jarvis march scans all points at each step to find the most counter-clockwise next hull vertex, running in O(n*h) time.

Jarvis march, also called gift wrapping, builds the convex hull by finding the most counter-clockwise point relative to the current hull edge at each step. Its time complexity is O(n times h) where n is the number of points and h is the hull vertex count, which makes it faster than Graham scan when h is small relative to n. The private helper _cross_product at line 44 computes the same signed area formula as consecutive_orientation in graham_scan.py. The main loop in _find_next_hull_point (line 83) scans all points and replaces the current candidate whenever a new point produces a positive cross product, meaning it is more counter-clockwise. Starting from the leftmost point and repeating until wrap-back produces hull vertices in counter-clockwise order.

Key takeaway

Jarvis march selects the most counter-clockwise next point at each step, wrapping the hull in O(n times h) where h is the number of hull vertices.

def _cross_product(origin: Point, point_a: Point, point_b: Point) -> float:
    """
    Calculate the cross product of vectors OA and OB.

    Returns:
        > 0: Counter-clockwise turn (left turn)
        = 0: Collinear
        < 0: Clockwise turn (right turn)
    """
    return (point_a.x - origin.x) * (point_b.y - origin.y) - (point_a.y - origin.y) * (
        point_b.x - origin.x
    )

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free