Compute the convex hull using the monotone chain algorithm. Sort points by X-coordinate…
- User
Compute the convex hull using the monotone chain algorithm. Sort points by X-coordinate then build the upper hull and lower hull separately in O(n) time after sorting.
Assistant
The user wants me to implement the monotone chain algorithm for computing the convex hull. This is a classic computational geometry algorithm that:
- Sorts points by x-coordinate (and by y-coordinate as tiebreaker)
- Builds the lower hull by processing points left to right
- Builds the upper hull by processing points right to left
- Combines them to get the complete convex hull
Let me write a comprehensive implementation with good documentation and examples.
Key points:
- Time complexity: O(n log n) for sorting, O(n) for hull construction = O(n log n) overall
- Space complexity: O(n)
- The algorithm uses the cross product to determine if we need to make a left turn (keep point) or right turn (remove point)
- Cross product > 0: counterclockwise (left turn)
- Cross product < 0: clockwise (right turn)
- Cross product = 0: collinear
Let me implement this properly:
def monotone_chain(points): """ Compute convex hull using monotone chain algorithm. Args: points: List of (x, y) tuples Returns: List of points on convex hull in counterclockwise order """ # Sort points lexicographically (first by x, then by y) points = sorted(set(points)) if len(points) <= 1: return points def cross(o, a, b): """Calculate cross product of vectors OA and OB""" return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) # Build 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 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) # Remove last point of each half because it's repeated return lower[:-1] + upper[:-1]I should also provide detailed explanation, step-by-step walkthrough, and test cases to demonstrate how the algorithm works in practice.
Monotone Chain Algorithm for Convex Hull
Here's a complete implementation with detailed explanation and test cases:
Core Algorithm
def monotone_chain(points): """ Compute convex hull using monotone chain algorithm. Time: O(n log n) - dominated by sorting Space: O(n) - for output hull Args: points: List of (x, y) tuples Returns: List of points forming convex hull (counterclockwise order) """ # Step 1: Remove duplicates and sort by x, then y points = sorted(set(points)) n = len(points) if n <= 2: return points def cross(o, a, b): """ Cross product of vectors OA and OB. > 0: counterclockwise turn (left) < 0: clockwise turn (right) = 0: collinear """ return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) # Step 2: Build lower hull (left to right) lower = [] for p in points: # Remove points that make right turn or are collinear while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # Step 3: Build upper hull (right to left) upper = [] for p in reversed(points): # Remove points that make right turn or are collinear while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) # Step 4: Concatenate and remove duplicate endpoints return lower[:-1] + upper[:-1]Detailed Implementation with Visualization
from typing import List, Tuple class ConvexHullMonotoneChain: """Compute convex hull using monotone chain algorithm.""" def __init__(self, points: List[Tuple[float, float]]): self.original_points = points.copy() self.hull = None self.steps = [] # For visualization def cross_product(self, o, a, b): """Calculate cross product of vectors OA and OB.""" return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def compute(self, verbose=False): """Compute convex hull with optional step tracking.""" # Sort points points = sorted(set(self.original_points)) if len(points) <= 2: self.hull = points return self.hull if verbose: print(f"Sorted points: {points}\n") # Build lower hull lower = [] if verbose: print("Building LOWER hull (left to right):") for i, p in enumerate(points): while len(lower) >= 2 and self.cross_product(lower[-2], lower[-1], p) <= 0: removed = lower.pop() if verbose: print(f" Removed {removed} (right turn)") lower.append(p) if verbose: print(f" Added {p} -> Lower: {lower}") if verbose: print(f"\nLower hull: {lower}\n") # Build upper hull upper = [] if verbose: print("Building UPPER hull (right to left):") for i, p in enumerate(reversed(points)): while len(upper) >= 2 and self.cross_product(upper[-2], upper[-1], p) <= 0: removed = upper.pop() if verbose: print(f" Removed {removed} (right turn)") upper.append(p) if verbose: print(f" Added {p} -> Upper: {upper}") if verbose: print(f"\nUpper hull: {upper}\n") # Combine hulls self.hull = lower[:-1] + upper[:-1] if verbose: print(f"Final hull: {self.hull}") return self.hull def visualize(self, title="Convex Hull"): """Visualize the convex hull using matplotlib.""" try: import matplotlib.pyplot as plt import numpy as np fig, ax = plt.subplots(1, 1, figsize=(10, 8)) # Plot all points if self.original_points: xs, ys = zip(*self.original_points) ax.scatter(xs, ys, c='blue', s=50, label='Input points', zorder=3) # Label points for x, y in self.original_points: ax.annotate(f'({x},{y})', (x, y), fontsize=8, xytext=(5, 5), textcoords='offset points') # Plot hull if self.hull: hull_closed = self.hull + [self.hull[0]] # Close the polygon hx, hy = zip(*hull_closed) ax.plot(hx, hy, 'r-', linewidth=2, label='Convex hull') ax.scatter(*zip(*self.hull), c='red', s=100, zorder=4) ax.set_xlabel('X') ax.set_ylabel('Y') ax.set_title(title) ax.legend() ax.grid(True, alpha=0.3) ax.axis('equal') plt.tight_layout() plt.show() except ImportError: print("Matplotlib not installed. Skipping visualization.") # Alternative implementation without class (simpler) def convex_hull(points: List[Tuple[float, float]]) -> List[Tuple[float, float]]: """Simple implementation of monotone chain algorithm.""" points = sorted(set(points)) if len(points) <= 2: return points def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) lower = [] for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) 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]Test Cases
def test_convex_hull(): """Comprehensive test cases.""" # Test 1: Simple square print("=" * 60) print("TEST 1: Square") print("=" * 60) points1 = [(0, 0), (1, 0), (1, 1), (0, 1)] hull1 = convex_hull(points1) print(f"Points: {points1}") print(f"Hull: {hull1}") print(f"Hull size: {len(hull1)}\n") # Test 2: Triangle with interior point print("=" * 60) print("TEST 2: Triangle with interior point") print("=" * 60) points2 = [(0, 0), (4, 0), (2, 3), (2, 1)] # (2,1) is interior hull2 = convex_hull(points2) print(f"Points: {points2}") print(f"Hull: {hull2}") print(f"Hull size: {len(hull2)}\n") # Test 3: Collinear points print("=" * 60) print("TEST 3: Collinear points") print("=" * 60) points3 = [(0, 0), (1, 1), (2, 2), (3, 3)] hull3 = convex_hull(points3) print(f"Points: {points3}") print(f"Hull: {hull3}") print(f"Hull size: {len(hull3)}\n") # Test 4: Complex polygon print("=" * 60) print("TEST 4: Complex polygon with duplicates") print("=" * 60) points4 = [ (0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0), (0.5, 0.5), (1, 2), (2, 1), (0, 0) # Has duplicates ] hull4 = convex_hull(points4) print(f"Points (with duplicates): {points4}") print(f"Hull: {hull4}") print(f"Hull size: {len(hull4)}\n") # Test 5: Random points with detailed output print("=" * 60) print("TEST 5: Detailed trace through algorithm") print("=" * 60) points5 = [(2, 0), (0, 2), (0, 0), (2, 2), (1, 1)] hull_obj = ConvexHullMonotoneChain(points5) hull5 = hull_obj.compute(verbose=True) print("\n") # Test 6: Edge cases print("=" * 60) print("TEST 6: Edge cases") print("=" * 60) # Single point print("Single point:") hull_single = convex_hull([(0, 0)]) print(f"Hull: {hull_single}\n") # Two points print("Two points:") hull_two = convex_hull([(0, 0), (1, 1)]) print(f"Hull: {hull_two}\n") # All identical points print("All identical points:") hull_identical = convex_hull([(0, 0), (0, 0), (0, 0)]) print(f"Hull: {hull_identical}\n") def verify_hull(points, hull): """Verify that hull is correct convex hull.""" if len(hull) < 3: return True # Can't verify def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) # Check all hull edges turn counterclockwise for i in range(len(hull)): o = hull[i] a = hull[(i + 1) % len(hull)] b = hull[(i + 2) % len(hull)] if cross(o, a, b) < 0: # Right turn or collinear return False # Check all points are on or inside hull for p in points: if p not in hull: is_inside = True for i in range(len(hull)): a = hull[i] b = hull[(i + 1) % len(hull)] if cross(a, b, p) < 0: # Point is on right side is_inside = False break if not is_inside: return False return True # Run tests if __name__ == "__main__": test_convex_hull() # Verify test cases print("\n" + "=" * 60) print("VERIFICATION") print("=" * 60) test_cases = [ [(0, 0), (1, 0), (1, 1), (0, 1)], [(0, 0), (4, 0), (2, 3), (2, 1)], [(0, 0), (1, 1), (2, 2), (3, 3)], ] for points in test_cases: hull = convex_hull(points) is_valid = verify_hull(points, hull) print(f"Points: {points}") print(f"Hull: {hull}") print(f"Valid: {is_valid}\n")Algorithm Analysis
def explain_algorithm(): """Explain the monotone chain algorithm step by step.""" explanation = """ MONOTONE CHAIN ALGORITHM - HOW IT WORKS ===================================== 1. SORTING PHASE: O(n log n) - Sort all points by x-coordinate - Use y-coordinate as tiebreaker - Result: Points ordered left to right, bottom to top 2. LOWER HULL CONSTRUCTION: O(n) - Process points from left to right - Maintain a list (stack) of candidates - For each new point: * While last 2 points + new point make right turn: - Remove the middle point (it's interior) * Add new point - Result: Lower boundary of hull 3. UPPER HULL CONSTRUCTION: O(n) - Process points from right to left - Same logic as lower hull - Result: Upper boundary of hull 4. COMBINE: O(1) - Concatenate lower and upper hulls - Remove duplicate endpoints WHY IT WORKS: - By processing monotonically (always left→right or right→left), we can determine locally if a point is on the hull - Cross product tells us turn direction - Only counterclockwise turns keep points on the hull KEY INSIGHT: - Each point is added and removed at most once - This gives O(n) time for hull construction - Sorting dominates: O(n log n) overall """ print(explanation) explain_algorithm()Complexity Analysis
Aspect Complexity Notes Time O(n log n) O(n log n) sorting + O(n) hull construction Space O(n) Output hull stores up to n points Per-point processing O(1) amortized Each point added/removed once Best case Ω(n log n) Dominated by sorting Worst case O(n log n) All points on hull This implementation is production-ready with O(n log n) time complexity and handles edge cases correctly!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.