Function convex_hull_recursive

divide_and_conquer/convex_hull.py:295–362

Constructs the convex hull of a set of 2D points using a divide-and-conquer strategy The algorithm exploits the geometric properties of the problem by repeatedly partitioning the set of points into smaller hulls, and finding the convex hull of these smaller hulls. The union of the

(points: list[Point])

def convex_hull_recursive(points: list[Point]) -> list[Point]:
    """
    Constructs the convex hull of a set of 2D points using a divide-and-conquer strategy
    The algorithm exploits the geometric properties of the problem by repeatedly
    partitioning the set of points into smaller hulls, and finding the convex hull of
    these smaller hulls.  The union of the convex hull from smaller hulls is the
    solution to the convex hull of the larger problem.

    Parameter
    ---------
    points: array-like of object of Points, lists or tuples.
    The set of  2d points for which the convex-hull is needed

    Runtime: O(n log n)

    Returns
    -------
    convex_set: list, the convex-hull of points sorted in non-decreasing order.

    Examples
    ---------
    >>> convex_hull_recursive([[0, 0], [1, 0], [10, 1]])
    [(0.0, 0.0), (1.0, 0.0), (10.0, 1.0)]
    >>> convex_hull_recursive([[0, 0], [1, 0], [10, 0]])
    [(0.0, 0.0), (10.0, 0.0)]
    >>> convex_hull_recursive([[-1, 1],[-1, -1], [0, 0], [0.5, 0.5], [1, -1], [1, 1],
    ...                        [-0.75, 1]])
    [(-1.0, -1.0), (-1.0, 1.0), (1.0, -1.0), (1.0, 1.0)]
    >>> convex_hull_recursive([(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3),
    ...                        (2, -1), (2, -4), (1, -3)])
    [(0.0, 0.0), (0.0, 3.0), (1.0, -3.0), (2.0, -4.0), (3.0, 0.0), (3.0, 3.0)]

    """
    points = sorted(_validate_input(points))
    n = len(points)

    # divide all the points into an upper hull and a lower hull
    # the left most point and the right most point are definitely
    # members of the convex hull by definition.
    # use these two anchors to divide all the points into two hulls,
    # an upper hull and a lower hull.

    # all points to the left (above) the line joining the extreme points belong to the
    # upper hull
    # all points to the right (below) the line joining the extreme points below to the
    # lower hull
    # ignore all points on the line joining the extreme points since they cannot be
    # part of the convex hull

    left_most_point = points[0]
    right_most_point = points[n - 1]

    convex_set = {left_most_point, right_most_point}
    upper_hull = []
    lower_hull = []

    for i in range(1, n - 1):
        det = _det(left_most_point, right_most_point, points[i])