Computational Geometry

Why Should You Care About Computational Geometry?

🎮

Game Physics & Collision Detection

Every time Mario jumps on a platform or a bullet hits a target, computational geometry determines if objects collide. Games use convex hulls and intersection algorithms millions of times per second!

🗺️

GPS Navigation & Maps

Your GPS uses point-in-polygon tests to know which country/city you're in, and line intersection to find where roads meet. Uber uses geometric algorithms to match riders with drivers!

🤖

Robotics & Autonomous Vehicles

Self-driving cars use computational geometry to detect obstacles, plan paths, and avoid collisions. Convex hulls help robots understand the shape of objects they need to grasp.

🎨

Computer Graphics & 3D Rendering

Pixar movies, video games, and CAD software use geometric algorithms for ray tracing, shadow calculation, and determining what's visible to the camera.

📱

Touch Gestures & UI

When you pinch to zoom or swipe on your phone, geometric algorithms detect the gesture pattern. Drawing apps use line smoothing and curve fitting algorithms.

🏗️

Architecture & Engineering

CAD software uses computational geometry for designing buildings, calculating structural loads, and optimizing material usage. 3D printing relies on geometric slicing algorithms.

Level 1: The Basics (Start Here!)

Level 1

What is Computational Geometry? Think of Drawing on Graph Paper!

Imagine you're drawing on graph paper. Every point has coordinates (x, y), and you can connect points to make lines, triangles, and other shapes. Computational geometry is about teaching computers to understand and manipulate these shapes!

Interactive Point Plotter

Click anywhere on the canvas to add points. Watch how we calculate distances!

Click to add points!

Points and Vectors - The Building Blocks

Everything in computational geometry starts with points and vectors. A point is a location, while a vector represents direction and distance.

Creating Points in Python 🐍

# Think of a point like a pin on a map!
class Point:
    def __init__(self, x, y):
        self.x = x  # How far right (like street number)
        self.y = y  # How far up (like avenue number)
    
    def distance_to(self, other):
        # Pythagorean theorem - remember from school?
        # It's like measuring the straight-line distance on a map
        dx = self.x - other.x
        dy = self.y - other.y
        return (dx**2 + dy**2)**0.5

# Example: Distance between two locations
home = Point(0, 0)      # Your home at origin
store = Point(3, 4)     # Store 3 blocks east, 4 blocks north
distance = home.distance_to(store)  # Returns 5.0 (3-4-5 triangle!)
                                

The Magic of Cross Product - Which Way to Turn?

The cross product tells us if we're turning left or right. It's like having a GPS that says "turn left" or "turn right" at intersections!

Understanding Cross Product

def cross_product(p1, p2, p3):
    """
    Imagine walking from p1 to p2, then to p3.
    Are you turning left, right, or going straight?
    
    Positive result = Left turn (counterclockwise) ↺
    Zero = Straight line
    Negative result = Right turn (clockwise) ↻
    """
    # This formula is like a magical direction detector!
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)

# Example: Are these points turning left or right?
p1 = Point(0, 0)
p2 = Point(1, 0)
p3 = Point(1, 1)

result = cross_product(p1, p2, p3)
if result > 0:
    print("Left turn! ↺")
elif result < 0:
    print("Right turn! ↻")
else:
    print("Straight line!")
                                

Common Mistake #1: Floating Point Precision

# ❌ WRONG - Exact equality with floats is dangerous!
if cross_product(p1, p2, p3) == 0:
    print("Points are collinear")
                            

Why it's wrong: Floating point math isn't exact. 0.1 + 0.2 ≠ 0.3 in computers!

The Right Way

# ✅ CORRECT - Use epsilon for floating point comparison
EPSILON = 1e-10  # Very small number
if abs(cross_product(p1, p2, p3)) < EPSILON:
    print("Points are collinear (within tolerance)")
                            

Level 2: Common Patterns

Level 2

Pattern 1: Convex Hull - Finding the Outer Boundary

Imagine wrapping a rubber band around a set of nails on a board. The shape it makes is the convex hull!

Interactive Convex Hull Builder

Click to add points and watch the convex hull update in real-time!

Click to add points, or generate random points!

Graham Scan Algorithm - Step by Step

1

Find the bottom point: Start with the lowest point (like the south pole)

2

Sort by angle: Order all other points by their angle from the start point

3

Walk the boundary: Keep only points that turn left (counterclockwise)

Graham Scan Implementation

def convex_hull_graham(points):
    """Find the convex hull - like finding fence posts for the smallest fence!"""
    if len(points) < 3:
        return points  # Need at least 3 points for a hull
    
    # Step 1: Find the starting point (bottom-most, then left-most)
    start = min(points, key=lambda p: (p.y, p.x))
    
    # Step 2: Sort points by polar angle (like clock positions)
    def polar_angle_key(p):
        import math
        angle = math.atan2(p.y - start.y, p.x - start.x)
        distance = ((p.x - start.x)**2 + (p.y - start.y)**2)**0.5
        return (angle, distance)  # Sort by angle, then distance
    
    sorted_points = sorted([p for p in points if p != start], 
                          key=polar_angle_key)
    
    # Step 3: Build the hull by keeping left turns only
    hull = [start, sorted_points[0]]
    
    for point in sorted_points[1:]:
        # Remove points that would make a right turn
        while len(hull) > 1 and cross_product(hull[-2], hull[-1], point) <= 0:
            hull.pop()  # This point is "inside" the hull
        hull.append(point)
    
    return hull

# Example usage
points = [Point(0,0), Point(1,1), Point(2,0), Point(1,-1), Point(1,0)]
hull = convex_hull_graham(points)
print(f"Hull has {len(hull)} vertices")  # Forms the outer boundary!
                                

Pattern 2: Line Intersection Detection

Do two line segments cross? Essential for collision detection and map routing!

Line Intersection Tester

Draw two line segments and see if they intersect!

Click two points to draw the first line segment

Line Intersection Algorithm

def segments_intersect(p1, q1, p2, q2):
    """
    Check if line segment p1-q1 intersects with p2-q2.
    Like checking if two roads cross!
    """
    def orientation(p, q, r):
        # Which way do we turn at q when going from p to r?
        val = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)
        if abs(val) < 1e-10: return 0  # Collinear
        return 1 if val > 0 else 2  # CCW or CW
    
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
    
    # General case: segments intersect if orientations differ
    if o1 != o2 and o3 != o4:
        return True
    
    # Special cases for collinear points...
    return False  # (simplified for clarity)
                                

Practice Problems (From Easy to Hard)

Easy

Problem 1: Point in Triangle

Check if a point is inside a triangle using cross products.

Think About It First!

Hint: A point is inside a triangle if it's on the same side of all three edges!

Show Solution

def point_in_triangle(p, a, b, c):
    """Check if point p is inside triangle abc"""
    # Calculate cross products for each edge
    cp1 = cross_product(a, b, p)
    cp2 = cross_product(b, c, p)
    cp3 = cross_product(c, a, p)
    
    # All same sign = point is inside
    has_neg = (cp1 < 0) or (cp2 < 0) or (cp3 < 0)
    has_pos = (cp1 > 0) or (cp2 > 0) or (cp3 > 0)
    
    return not (has_neg and has_pos)
                                    

Medium

Problem 2: Polygon Area

Calculate the area of any polygon using the Shoelace formula.

Strategy Hint

Sum up the cross products of consecutive edges!

Show Solution

def polygon_area(vertices):
    """Calculate area using Shoelace formula"""
    n = len(vertices)
    area = 0
    
    for i in range(n):
        j = (i + 1) % n
        area += vertices[i].x * vertices[j].y
        area -= vertices[j].x * vertices[i].y
    
    return abs(area) / 2
                                    

Hard

Problem 3: Closest Pair of Points

Find the two closest points in O(n log n) time using divide and conquer.

Advanced Strategy

Divide points by x-coordinate, solve recursively, then check the middle strip!

Show Solution

def closest_pair(points):
    """Find closest pair using divide & conquer"""
    def closest_recursive(px, py):
        n = len(px)
        if n <= 3:
            return brute_force(px)
        
        mid = n // 2
        midpoint = px[mid]
        
        # Divide
        pyl = [p for p in py if p.x <= midpoint.x]
        pyr = [p for p in py if p.x > midpoint.x]
        
        # Conquer
        dl = closest_recursive(px[:mid], pyl)
        dr = closest_recursive(px[mid:], pyr)
        
        # Combine
        d = min(dl, dr)
        strip = [p for p in py if abs(p.x - midpoint.x) < d]
        
        # Check strip
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and (strip[j].y - strip[i].y) < d:
                d = min(d, distance(strip[i], strip[j]))
                j += 1
        
        return d
    
    px = sorted(points, key=lambda p: p.x)
    py = sorted(points, key=lambda p: p.y)
    return closest_recursive(px, py)
                                    

Level 3: Advanced Techniques

Advanced

Sweep Line Algorithm

Imagine a vertical line sweeping across the plane from left to right!

Line Segment Intersection with Sweep Line

def find_intersections(segments):
    """
    Find all intersections among line segments.
    Like a radar sweeping across the screen!
    """
    from heapq import heappush, heappop
    
    events = []
    # Create events for segment endpoints
    for i, seg in enumerate(segments):
        # Left endpoint: segment starts
        heappush(events, (min(seg.p1.x, seg.p2.x), 'start', i))
        # Right endpoint: segment ends
        heappush(events, (max(seg.p1.x, seg.p2.x), 'end', i))
    
    active_segments = set()
    intersections = []
    
    while events:
        x, event_type, seg_id = heappop(events)
        
        if event_type == 'start':
            # Check new segment against all active segments
            for other_id in active_segments:
                if segments_intersect(segments[seg_id], segments[other_id]):
                    intersections.append((seg_id, other_id))
            active_segments.add(seg_id)
        else:
            active_segments.remove(seg_id)
    
    return intersections
                                

Voronoi Diagrams

Divide the plane into regions based on the nearest point - like territories on a map!

Interactive Voronoi Diagram

Add points to see how the plane gets divided into regions!

Click to add Voronoi sites!

Rotating Calipers

Find the diameter of a point set - like measuring with adjustable calipers!

def rotating_calipers(hull):
    """Find diameter (farthest pair) of convex hull"""
    n = len(hull)
    if n < 2:
        return 0
    
    max_dist = 0
    j = 1
    
    for i in range(n):
        # Find the farthest point from hull[i]
        while True:
            next_j = (j + 1) % n
            # Check if next point is farther
            if distance(hull[i], hull[next_j]) > distance(hull[i], hull[j]):
                j = next_j
            else:
                break
        
        max_dist = max(max_dist, distance(hull[i], hull[j]))
    
    return max_dist
                        

Quick Reference Guide

Geometric Operations Complexity

Operation	Time Complexity	Space	When to Use
Distance between points	O(1)	O(1)	⚡ Basic measurement
Cross product	O(1)	O(1)	⚡ Orientation tests
Line intersection	O(1)	O(1)	⚡ Two segments only
Convex Hull (Graham)	O(n log n)	O(n)	🎯 Finding outer boundary
Point in Polygon	O(n)	O(1)	🎯 Containment test
Closest Pair (D&C)	O(n log n)	O(n)	🎯 Nearest neighbors
All intersections	O((n+k) log n)	O(n)	📊 k = intersections
Voronoi Diagram	O(n log n)	O(n)	🗺️ Territory division

Essential Formulas

Distance: √((x₂-x₁)² + (y₂-y₁)²)
Cross Product: (x₂-x₁)(y₃-y₁) - (y₂-y₁)(x₃-x₁)
Polygon Area: ½|Σ(xᵢyᵢ₊₁ - xᵢ₊₁yᵢ)|
Line Equation: ax + by + c = 0
Point-Line Distance: |ax₀ + by₀ + c|/√(a² + b²)

Common Applications

✅ Collision detection in games
✅ Route planning in maps
✅ Computer graphics rendering
✅ Robotics path planning
✅ GIS and mapping software
✅ CAD/CAM applications
✅ Image processing

Algorithm Choice Guide

Convex Hull: Use Graham for simplicity, Andrew's for robustness
Intersections: Sweep line for many segments
Nearest Point: KD-tree for multiple queries
Inside Test: Ray casting for complex polygons
Triangulation: Ear clipping for simple polygons

💡 Pro Tips:

Always handle floating-point precision with epsilon comparisons
Consider degenerate cases (collinear points, zero-length segments)
Use integer coordinates when possible to avoid precision issues
Visualize your algorithms - geometry is inherently visual!
Test with edge cases: duplicate points, aligned points, extreme coordinates