Implementing a Convex Hull Algorithm in Python: Unexpected Output with Edge Cases
I'm integrating two systems and I'm getting frustrated with I've been banging my head against this for hours. I'm working on implementing the Convex Hull algorithm in Python using the Andrew's monotone chain method. While my implementation works great with standard test cases, I've started running into issues with edge cases, particularly when my input consists of collinear points or when all points are situated in a straight line. The output is not as expected, and I suspect it might be due to how I'm handling the points during the construction of the hull. Here's my current implementation: ```python from typing import List, Tuple Point = Tuple[int, int] def convex_hull(points: List[Point]) -> List[Point]: points = sorted(set(points)) # Remove duplicates and sort points if len(points) <= 1: return points # Build the lower hull lower = [] for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # Build the upper hull upper = [] for p in reversed(points): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) return lower[:-1] + upper[:-1] # Combine lower and upper hulls def cross(o: Point, a: Point, b: Point) -> int: return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) # Test with collinear points points = [(0, 0), (1, 1), (2, 2), (3, 3), (1, 0), (1, 2)] print(convex_hull(points)) # Expected output should handle collinear points correctly ``` When I run this code with the provided test points, I get `(0, 0), (3, 3), (1, 0), (1, 2)` as the output, which doesn't form the expected convex hull shape. Additionally, when I test with points like `[(1, 1), (1, 2), (1, 3), (1, 4)]`, I'm not getting consistent results either. I also tried sorting the points differently or adjusting the cross product check, but it didn’t help. Is there a specific approach or adjustment I can make to correctly handle these edge cases while still following the monotone chain method? Any advice or best practices for managing collinear points would be greatly appreciated! Any help would be greatly appreciated! Any advice would be much appreciated. What's the best practice here?