other.graham_scan
=================

.. py:module:: other.graham_scan

.. autoapi-nested-parse::

   This is a pure Python implementation of the Graham scan algorithm
   Source: https://en.wikipedia.org/wiki/Graham_scan

   For doctests run following command:
   python3 -m doctest -v graham_scan.py



Classes
-------

.. autoapisummary::

   other.graham_scan.Direction


Functions
---------

.. autoapisummary::

   other.graham_scan.angle_comparer
   other.graham_scan.check_direction
   other.graham_scan.graham_scan


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

.. py:class:: Direction(*args, **kwds)

   Bases: :py:obj:`enum.Enum`


   Create a collection of name/value pairs.

   Example enumeration:

   >>> class Color(Enum):
   ...     RED = 1
   ...     BLUE = 2
   ...     GREEN = 3

   Access them by:

   - attribute access:

     >>> Color.RED
     <Color.RED: 1>

   - value lookup:

     >>> Color(1)
     <Color.RED: 1>

   - name lookup:

     >>> Color['RED']
     <Color.RED: 1>

   Enumerations can be iterated over, and know how many members they have:

   >>> len(Color)
   3

   >>> list(Color)
   [<Color.RED: 1>, <Color.BLUE: 2>, <Color.GREEN: 3>]

   Methods can be added to enumerations, and members can have their own
   attributes -- see the documentation for details.


   .. py:method:: __repr__()


   .. py:attribute:: left
      :value: 1



   .. py:attribute:: right
      :value: 3



   .. py:attribute:: straight
      :value: 2



.. py:function:: angle_comparer(point: tuple[int, int], minx: int, miny: int) -> float

   Return the angle toward to point from (minx, miny)

   :param point: The target point
          minx: The starting point's x
          miny: The starting point's y
   :return: the angle

   Examples:
   >>> angle_comparer((1,1), 0, 0)
   45.0

   >>> angle_comparer((100,1), 10, 10)
   -5.710593137499642

   >>> angle_comparer((5,5), 2, 3)
   33.690067525979785


.. py:function:: check_direction(starting: tuple[int, int], via: tuple[int, int], target: tuple[int, int]) -> Direction

   Return the direction toward to the line from via to target from starting

   :param starting: The starting point
          via: The via point
          target: The target point
   :return: the Direction

   Examples:
   >>> check_direction((1,1), (2,2), (3,3))
   Direction.straight

   >>> check_direction((60,1), (-50,199), (30,2))
   Direction.left

   >>> check_direction((0,0), (5,5), (10,0))
   Direction.right


.. py:function:: graham_scan(points: list[tuple[int, int]]) -> list[tuple[int, int]]

   Pure implementation of graham scan algorithm in Python

   :param points: The unique points on coordinates.
   :return: The points on convex hell.

   Examples:
   >>> graham_scan([(9, 6), (3, 1), (0, 0), (5, 5), (5, 2), (7, 0), (3, 3), (1, 4)])
   [(0, 0), (7, 0), (9, 6), (5, 5), (1, 4)]

   >>> graham_scan([(0, 0), (1, 0), (1, 1), (0, 1)])
   [(0, 0), (1, 0), (1, 1), (0, 1)]

   >>> graham_scan([(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)])
   [(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)]

   >>> graham_scan([(-100, 20), (99, 3), (1, 10000001), (5133186, -25), (-66, -4)])
   [(5133186, -25), (1, 10000001), (-100, 20), (-66, -4)]