geometry.jarvis_march
=====================

.. py:module:: geometry.jarvis_march

.. autoapi-nested-parse::

   Jarvis March (Gift Wrapping) algorithm for finding the convex hull of a set of points.

   The convex hull is the smallest convex polygon that contains all the points.

   Time Complexity: O(n*h) where n is the number of points and h is the number of
   hull points.
   Space Complexity: O(h) where h is the number of hull points.

   USAGE:
       -> Import this file into your project.
       -> Use the jarvis_march() function to find the convex hull of a set of points.
       -> Parameters:
           -> points: A list of Point objects representing 2D coordinates

   REFERENCES:
       -> Wikipedia reference: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm
       -> GeeksforGeeks:
          https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/



Attributes
----------

.. autoapisummary::

   geometry.jarvis_march.points


Classes
-------

.. autoapisummary::

   geometry.jarvis_march.Point


Functions
---------

.. autoapisummary::

   geometry.jarvis_march._add_point_to_hull
   geometry.jarvis_march._cross_product
   geometry.jarvis_march._find_leftmost_point
   geometry.jarvis_march._find_next_hull_point
   geometry.jarvis_march._is_point_on_segment
   geometry.jarvis_march._is_valid_polygon
   geometry.jarvis_march.jarvis_march


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

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

   Represents a 2D point with x and y coordinates.


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


   .. py:method:: __hash__() -> int


   .. py:method:: __repr__() -> str


   .. py:attribute:: x


   .. py:attribute:: y


.. py:function:: _add_point_to_hull(hull: list[Point], point: Point) -> None

   Add a point to hull, removing collinear intermediate points.


.. py:function:: _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)


.. py:function:: _find_leftmost_point(points: list[Point]) -> int

   Find index of leftmost point (and bottom-most in case of tie).


.. py:function:: _find_next_hull_point(points: list[Point], current_idx: int) -> int

   Find the next point on the convex hull.


.. py:function:: _is_point_on_segment(p1: Point, p2: Point, point: Point) -> bool

   Check if a point lies on the line segment between p1 and p2.


.. py:function:: _is_valid_polygon(hull: list[Point]) -> bool

   Check if hull forms a valid polygon (has at least one non-collinear turn).


.. py:function:: jarvis_march(points: list[Point]) -> list[Point]

   Find the convex hull of a set of points using the Jarvis March algorithm.

   The algorithm starts with the leftmost point and wraps around the set of
   points, selecting the most counter-clockwise point at each step.

   Args:
       points: List of Point objects representing 2D coordinates

   Returns:
       List of Points that form the convex hull in counter-clockwise order.
       Returns empty list if there are fewer than 3 non-collinear points.


.. py:data:: points