Python convex hull

import math import sys from typing import List from typing import Tuple EPSILON = sys.float_info.epsilon Point = Tuple[int, int] def y_intercept(p1: Point, p2: Point, x: int) -> float: """ Given two points, p1 and p2, an x coordinate from a vertical line, compute and return the the y-intercept of the line segment p1->p2 with the vertical line passing through x. """ x1, y1 = p1 x2, y2 = p2 slope = (y2 - y1) / (x2 - x1) return y1 + (x - x1) * slope def triangle_area(a: Point, b: Point, c: Point) -> float: """ Given three points a,b,c, computes and returns the area defined by the triangle a,b,c. Note that this area will be negative if a,b,c represents a clockwise sequence, positive if it is counter-clockwise, and zero if the points are collinear. """ ax, ay = a bx, by = b cx, cy = c return ((cx - bx) * (by - ay) - (bx - ax) * (cy - by)) / 2 def is_clockwise(a: Point, b: Point, c: Point) -> bool: """ Given three points a,b,c, returns True if and only if a,b,c represents a clockwise sequence (subject to floating-point precision) """ return triangle_area(a, b, c) < -EPSILON def is_counter_clockwise(a: Point, b: Point, c: Point) -> bool: """ Given three points a,b,c, returns True if and only if a,b,c represents a counter-clockwise sequence (subject to floating-point precision) """ return triangle_area(a, b, c) > EPSILON def collinear(a: Point, b: Point, c: Point) -> bool: """ Given three points a,b,c, returns True if and only if a,b,c are collinear (subject to floating-point precision) """ return abs(triangle_area(a, b, c)) <= EPSILON def clockwise_sort(points: List[Point]): """ Given a list of points, sorts those points in clockwise order about their centroid. Note: this function modifies its argument. """ # get mean x coord, mean y coord x_mean = sum(p[0] for p in points) / len(points) y_mean = sum(p[1] for p in points) / len(points) def angle(point: Point): return (math.atan2(point[1] - y_mean, point[0] - x_mean) + 2 * math.pi) % (2 * math.pi) points.sort(key=angle) return def base_case_hull(points: List[Point]) -> List[Point]: """ Base case of the recursive algorithm. """ #Implement base case for recursive call def compute_hull(points: List[Point]) -> List[Point]: """ Given a list of points, computes the convex hull around those points and returns only the points that are on the hull. """ #sort the points based on x coordinate points = sorted(points, key=lambda k: k[0]) right_most = max(points, key=lambda k: k[0]) left_most = min(points, key=lambda k: k[0]) midpoint = (right_most[0] + left_most[0]) / 2 # Splits the points into 2 sets for i in points: if i[0] < midpoint: left_half.append(i) else: right_half.append(i) #recursive call of compute_hull left_copy = compute_hull(left_half) right_copy = compute_hull(right_half) points = merge(left_copy, right_copy, midpoint) return points def merge(left, right, midpoint): # Right most point of left hull lh_right = max(left, key=lambda point: point[0]) # Left most point of right hull rh_left = min(right, key=lambda point: point[0]) return points