geometry.graham_scan

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

T
points

Classes

Point

A point in 2D space.

Functions

graham_scan(→ list[Point])

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

Module Contents

class geometry.graham_scan.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)

__eq__(other: object) → bool

Check if two points are equal.

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

__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

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

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

x: float

y: float

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

geometry.graham_scan.T

geometry.graham_scan.points