other.graham_scan

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

Direction

Create a collection of name/value pairs.

Functions

angle_comparer(→ float)

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

check_direction(→ Direction)

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

graham_scan(→ list[tuple[int, int]])

Pure implementation of graham scan algorithm in Python

Module Contents

class other.graham_scan.Direction(*args, **kwds)

Bases: 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.

__repr__()
left = 1
right = 3
straight = 2
other.graham_scan.angle_comparer(point: tuple[int, int], minx: int, miny: int) → float

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

Parameters:

point – The target point minx: The starting point’s x miny: The starting point’s y

Returns:

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
other.graham_scan.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

Parameters:

starting – The starting point via: The via point target: The target point

Returns:

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
other.graham_scan.graham_scan(points: list[tuple[int, int]]) → list[tuple[int, int]]

Pure implementation of graham scan algorithm in Python

Parameters:

points – The unique points on coordinates.

Returns:

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)]