geometry.jarvis_march

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

points

Classes

Point

Represents a 2D point with x and y coordinates.

Functions

_add_point_to_hull(→ None)	Add a point to hull, removing collinear intermediate points.
_cross_product(→ float)	Calculate the cross product of vectors OA and OB.
_find_leftmost_point(→ int)	Find index of leftmost point (and bottom-most in case of tie).
_find_next_hull_point(→ int)	Find the next point on the convex hull.
_is_point_on_segment(→ bool)	Check if a point lies on the line segment between p1 and p2.
_is_valid_polygon(→ bool)	Check if hull forms a valid polygon (has at least one non-collinear turn).
jarvis_march(→ list[Point])	Find the convex hull of a set of points using the Jarvis March algorithm.

Module Contents

class geometry.jarvis_march.Point(x_coordinate: float, y_coordinate: float)

Represents a 2D point with x and y coordinates.

__eq__(other: object) → bool

__hash__() → int

__repr__() → str

x

y

geometry.jarvis_march._add_point_to_hull(hull: list[Point], point: Point) → None

Add a point to hull, removing collinear intermediate points.

geometry.jarvis_march._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)

geometry.jarvis_march._find_leftmost_point(points: list[Point]) → int

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

geometry.jarvis_march._find_next_hull_point(points: list[Point], current_idx: int) → int

Find the next point on the convex hull.

geometry.jarvis_march._is_point_on_segment(p1: Point, p2: Point, point: Point) → bool

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

geometry.jarvis_march._is_valid_polygon(hull: list[Point]) → bool

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

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

geometry.jarvis_march.points