Graham Scan as an alternative convex hull algorithm.

[cleder]

def orientation(p, q, r):
    """
    Calculate orientation of three points (p, q, r).
    Returns:
    -1 if counterclockwise
    0 if colinear
    1 if clockwise
    """
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else -1

def graham_scan(points):
    """
    Graham's scan algorithm to find the convex hull of a set of points.
    Returns the sorted points forming the convex hull.
    """
    n = len(points)
    if n < 3:
        return points

    # Find the point with the lowest y-coordinate (and leftmost if ties)
    pivot = min(points, key=lambda p: (p[1], p[0]))

    # Sort the points based on polar angle with respect to the pivot
    sorted_points = sorted(points, key=lambda p: (math.atan2(p[1]-pivot[1], p[0]-pivot[0]), p))

    # Initialize the stack
    stack = [pivot, sorted_points[0], sorted_points[1]]

    # Iterate over the sorted points
    for i in range(2, n):
        while len(stack) > 1 and orientation(stack[-2], stack[-1], sorted_points[i]) != -1:
            stack.pop()
        stack.append(sorted_points[i])

    return stack

# Example: Collection of arbitrary points
points = [(0, 0), (3, 1), (1, 2), (2, 3), (4, 4), (3, 0), (2, 1)]

# Sort the points to form a closed linear ring
sorted_ring = graham_scan(points)

print("Original Points:", points)
print("Sorted Linear Ring Points:", sorted_ring)

This implementation uses the Graham's scan algorithm to find the convex hull of the points, and the resulting sorted_ring contains the points forming a closed linear ring without self-intersections.

[cleder]

maybe this can be used to verify the existing convex hull implementation, applied to that it should always return the same hull