geometry.graham_scan
====================

.. py:module:: geometry.graham_scan

.. autoapi-nested-parse::

   Graham Scan algorithm for finding the convex hull of a set of points.

   The Graham scan is a method of computing the convex hull of a finite set of points
   in the plane with time complexity O(n log n). It is named after Ronald Graham, who
   published the original algorithm in 1972.

   The algorithm finds all vertices of the convex hull ordered along its boundary.
   It uses a stack to efficiently identify and remove points that would create
   non-convex angles.

   References:
   - https://en.wikipedia.org/wiki/Graham_scan
   - Graham, R.L. (1972). "An Efficient Algorithm for Determining the Convex Hull of a
     Finite Planar Set"



Attributes
----------

.. autoapisummary::

   geometry.graham_scan.T
   geometry.graham_scan.points


Classes
-------

.. autoapisummary::

   geometry.graham_scan.Point


Functions
---------

.. autoapisummary::

   geometry.graham_scan.graham_scan


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

.. py:class:: Point(x_coordinate: float, y_coordinate: float)

   A point in 2D space.

   >>> Point(0, 0)
   Point(x=0.0, y=0.0)
   >>> Point(1.5, 2.5)
   Point(x=1.5, y=2.5)


   .. py:method:: __eq__(other: object) -> bool

      Check if two points are equal.

      >>> Point(1, 2) == Point(1, 2)
      True
      >>> Point(1, 2) == Point(2, 1)
      False



   .. py:method:: __lt__(other: Point) -> bool

      Compare two points for sorting (bottom-most, then left-most).

      >>> Point(1, 2) < Point(1, 3)
      True
      >>> Point(1, 2) < Point(2, 2)
      True
      >>> Point(2, 2) < Point(1, 2)
      False



   .. py:method:: consecutive_orientation(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



   .. py:method:: euclidean_distance(other: Point) -> float

      Calculate Euclidean distance between two points.

      >>> Point(0, 0).euclidean_distance(Point(3, 4))
      5.0
      >>> Point(1, 1).euclidean_distance(Point(4, 5))
      5.0



   .. py:attribute:: x
      :type:  float


   .. py:attribute:: y
      :type:  float


.. py:function:: graham_scan(points: collections.abc.Sequence[Point]) -> list[Point]

   Find the convex hull of a set of points using the Graham scan algorithm.

   The algorithm works as follows:
   1. Find the bottom-most point (or left-most in case of tie)
   2. Sort all other points by polar angle with respect to the bottom-most point
   3. Process points in order, maintaining a stack of hull candidates
   4. Remove points that would create a clockwise turn

   Args:
       points: A sequence of Point objects

   Returns:
       A list of Point objects representing the convex hull in counter-clockwise order.
       Returns an empty list if there are fewer than 3 distinct points or if all
       points are collinear.

   Time Complexity: O(n log n) due to sorting
   Space Complexity: O(n) for the output hull

   >>> graham_scan([])
   []
   >>> graham_scan([Point(0, 0)])
   []
   >>> graham_scan([Point(0, 0), Point(1, 1)])
   []
   >>> hull = graham_scan([Point(0, 0), Point(1, 0), Point(0.5, 1)])
   >>> len(hull)
   3
   >>> Point(0, 0) in hull and Point(1, 0) in hull and Point(0.5, 1) in hull
   True


.. py:data:: T

.. py:data:: points