Sweep Line Algorithm - CSU083 | Shoolini University

Sweep Line Algorithm

1. Prerequisites

Before understanding the Sweep Line Algorithm, you should be familiar with the following foundational concepts:

2. What is the Sweep Line Algorithm?

The Sweep Line Algorithm is a computational geometry technique that processes a set of geometric objects by sweeping a conceptual vertical or horizontal line across a plane. It efficiently solves problems by handling events in a sorted order.

2.1 Key Components

2.2 Working Mechanism

The algorithm operates as follows:

3. Why Does This Algorithm Exist?

The Sweep Line Algorithm exists to solve problems that involve processing geometric objects efficiently. Instead of brute-force pairwise comparisons, it leverages event ordering to reduce computational complexity.

3.1 Real-World Applications

4. When Should You Use It?

The Sweep Line Algorithm is best used when:

4.1 Best Use Cases

5. How Does It Compare to Alternatives?

The Sweep Line Algorithm competes with other geometric algorithms. Below is a comparison of its strengths and weaknesses:

5.1 Strengths

5.2 Weaknesses

5.3 Alternatives

6. Basic Implementation

Below is a Python implementation of the Sweep Line Algorithm for detecting intersections among a set of line segments. It utilizes an event queue and a balanced tree to maintain active segments.


import heapq
from sortedcontainers import SortedList

class Event:
    def __init__(self, x, segment, is_start):
        self.x = x
        self.segment = segment
        self.is_start = is_start
    
    def __lt__(self, other):
        return self.x < other.x  # Sorting events by x-coordinate

def do_intersect(seg1, seg2):
    """ Check if two line segments intersect using orientation test. """
    def orientation(p, q, r):
        val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
        return 0 if val == 0 else (1 if val > 0 else -1)
    
    p1, q1 = seg1
    p2, q2 = seg2
    
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    return o1 != o2 and o3 != o4

def sweep_line_intersection(segments):
    """ Detect intersections using Sweep Line Algorithm. """
    events = []
    for seg in segments:
        events.append(Event(seg[0][0], seg, True))  # Start event
        events.append(Event(seg[1][0], seg, False)) # End event

    events.sort()  # Sorting events by x-coordinate

    active_segments = SortedList(key=lambda seg: seg[0][1])  # Sort by y-coordinate
    intersections = []

    for event in events:
        seg = event.segment
        if event.is_start:
            idx = active_segments.bisect(seg)
            if idx > 0 and do_intersect(active_segments[idx - 1], seg):
                intersections.append((active_segments[idx - 1], seg))
            if idx < len(active_segments) and do_intersect(active_segments[idx], seg):
                intersections.append((active_segments[idx], seg))
            active_segments.add(seg)
        else:
            idx = active_segments.index(seg)
            if 0 < idx < len(active_segments) - 1 and do_intersect(active_segments[idx - 1], active_segments[idx + 1]):
                intersections.append((active_segments[idx - 1], active_segments[idx + 1]))
            active_segments.remove(seg)

    return intersections

# Example input: List of line segments (defined by two endpoints)
segments = [
    ((1, 1), (5, 5)),
    ((2, 5), (6, 1)),
    ((3, 3), (7, 7)),
]

# Running the algorithm
intersections = sweep_line_intersection(segments)
print("Intersections:", intersections)

This implementation:

7. Dry Run of the Algorithm

Let's dry-run the algorithm for the input:


Segments: 
1. ((1, 1), (5, 5))
2. ((2, 5), (6, 1))
3. ((3, 3), (7, 7))

Sorted Events:
(1, Start of Segment 1)
(2, Start of Segment 2)
(3, Start of Segment 3)
(5, End of Segment 1)
(6, End of Segment 2)
(7, End of Segment 3)

Step-by-step execution:

Step 1: Process (1, Start of Segment 1)
  - Add segment ((1,1) to (5,5)) to active set.

Step 2: Process (2, Start of Segment 2)
  - Add segment ((2,5) to (6,1)) to active set.
  - Check for intersection with existing segment ((1,1) to (5,5)).
  - Intersection found → Store result.

Step 3: Process (3, Start of Segment 3)
  - Add segment ((3,3) to (7,7)) to active set.
  - Check for intersections with neighbors.
  - No new intersection.

Step 4: Process (5, End of Segment 1)
  - Remove segment ((1,1) to (5,5)) from active set.
  - Check if neighboring segments intersect.
  - No new intersection.

Step 5: Process (6, End of Segment 2)
  - Remove segment ((2,5) to (6,1)) from active set.

Step 6: Process (7, End of Segment 3)
  - Remove segment ((3,3) to (7,7)) from active set.

Final Output:
Intersections: [((1,1) to (5,5)), ((2,5) to (6,1))]

Observations:

8. Time & Space Complexity Analysis

8.1 Time Complexity Breakdown

The Sweep Line Algorithm involves three main operations:

8.2 Complexity Derivation

9. Space Complexity Analysis

The space complexity of the Sweep Line Algorithm depends on:

9.1 Growth with Input Size

9.2 Space Complexity Summary

10. Trade-offs in Using the Sweep Line Algorithm

10.1 Strengths

10.2 Weaknesses

10.3 Alternative Approaches

Conclusion: The Sweep Line Algorithm is best when \(k\) is significantly smaller than \(n^2\), making it a practical choice for real-world applications where spatial relationships need to be analyzed efficiently.

11. Optimizations & Variants

11.1 Common Optimizations

Several optimizations can improve the efficiency of the Sweep Line Algorithm:

11.2 Variants of the Sweep Line Algorithm

The Sweep Line Algorithm has multiple versions designed for different geometric problems:

11.3 Memory Optimization

To reduce memory footprint:

12. Iterative vs. Recursive Implementations

12.1 Iterative Approach

The iterative implementation of the Sweep Line Algorithm uses an explicit loop to process events:


def sweep_line_iterative(segments):
    events = []
    for seg in segments:
        events.append((seg[0][0], seg, True))  # Start event
        events.append((seg[1][0], seg, False)) # End event

    events.sort()  # Sort events by x-coordinate
    active_segments = SortedList(key=lambda seg: seg[0][1])
    
    intersections = []
    for event in events:
        x, seg, is_start = event
        if is_start:
            idx = active_segments.bisect(seg)
            if idx > 0 and do_intersect(active_segments[idx - 1], seg):
                intersections.append((active_segments[idx - 1], seg))
            if idx < len(active_segments) and do_intersect(active_segments[idx], seg):
                intersections.append((active_segments[idx], seg))
            active_segments.add(seg)
        else:
            idx = active_segments.index(seg)
            if 0 < idx < len(active_segments) - 1 and do_intersect(active_segments[idx - 1], active_segments[idx + 1]):
                intersections.append((active_segments[idx - 1], active_segments[idx + 1]))
            active_segments.remove(seg)

    return intersections

12.2 Recursive Approach

The recursive implementation typically follows a divide-and-conquer strategy:


def sweep_line_recursive(events, active_segments, index, intersections):
    if index >= len(events):
        return intersections

    x, seg, is_start = events[index]
    if is_start:
        idx = active_segments.bisect(seg)
        if idx > 0 and do_intersect(active_segments[idx - 1], seg):
            intersections.append((active_segments[idx - 1], seg))
        if idx < len(active_segments) and do_intersect(active_segments[idx], seg):
            intersections.append((active_segments[idx], seg))
        active_segments.add(seg)
    else:
        idx = active_segments.index(seg)
        if 0 < idx < len(active_segments) - 1 and do_intersect(active_segments[idx - 1], active_segments[idx + 1]):
            intersections.append((active_segments[idx - 1], active_segments[idx + 1]))
        active_segments.remove(seg)

    return sweep_line_recursive(events, active_segments, index + 1, intersections)

def start_sweep_line_recursive(segments):
    events = [(seg[0][0], seg, True) for seg in segments] + [(seg[1][0], seg, False) for seg in segments]
    events.sort()
    return sweep_line_recursive(events, SortedList(key=lambda seg: seg[0][1]), 0, [])

12.3 Comparison

Aspect Iterative Recursive
Memory Usage Lower, no stack overhead Higher, due to recursive stack
Readability More intuitive for large inputs Compact but harder to debug
Performance Better, avoids function call overhead Slower, recursive calls add overhead
Best Use Case Large datasets Divide-and-conquer-based problems

Conclusion: The iterative approach is preferred for efficiency and scalability, while recursion is useful in problems where divide-and-conquer is beneficial.

13. Edge Cases & Failure Handling

The Sweep Line Algorithm must handle various edge cases to avoid incorrect results or infinite loops.

13.1 Common Edge Cases

13.2 Failure Handling Strategies

14. Test Cases to Verify Correctness

Testing is crucial to ensure the correctness of the Sweep Line Algorithm.

14.1 Basic Test Cases


def test_sweep_line():
    segments = [
        ((1, 1), (5, 5)),  # Diagonal
        ((2, 5), (6, 1)),  # Crossing first segment
        ((3, 3), (7, 7)),  # Parallel
    ]
    expected_intersections = [(((1, 1), (5, 5)), ((2, 5), (6, 1)))]
    assert sweep_line_intersection(segments) == expected_intersections

def test_no_intersection():
    segments = [
        ((1, 1), (2, 2)),
        ((3, 3), (4, 4))
    ]
    assert sweep_line_intersection(segments) == []

def test_overlapping_segments():
    segments = [
        ((1, 1), (5, 5)),
        ((2, 2), (4, 4)),  # Overlapping within first segment
    ]
    assert sweep_line_intersection(segments) == []

def test_vertical_segment():
    segments = [
        ((2, 1), (2, 5)),  # Vertical segment
        ((1, 3), (3, 3)),  # Horizontal segment crossing vertical one
    ]
    expected_intersections = [(((2, 1), (2, 5)), ((1, 3), (3, 3)))]
    assert sweep_line_intersection(segments) == expected_intersections

def test_collinear_segments():
    segments = [
        ((1, 1), (5, 5)),
        ((3, 3), (7, 7))  # Collinear but non-overlapping
    ]
    assert sweep_line_intersection(segments) == []

14.2 Key Testing Considerations

15. Real-World Failure Scenarios

Failure scenarios occur when the algorithm is applied in real-world applications. Understanding these helps in designing more robust solutions.

15.1 Example Failure Scenarios

15.2 Strategies to Mitigate Failures

16. Real-World Applications & Industry Use Cases

The Sweep Line Algorithm is widely used in computational geometry, computer graphics, and real-world problem-solving. Below are its key applications:

16.1 Geographic Information Systems (GIS)

16.2 Computer Graphics & Rendering

16.3 Robotics & Path Planning

16.4 Computational Biology

16.5 VLSI Design & Circuit Layout

17. Open-Source Implementations

Several open-source projects use the Sweep Line Algorithm for different applications. Below are a few:

18. Practical Project: Road Intersection Detector

This project uses the Sweep Line Algorithm to detect intersections in road networks.

18.1 Project Overview

We will build a Python script that takes road segments as input and finds intersections using the Sweep Line Algorithm.

18.2 Implementation


import matplotlib.pyplot as plt
from sortedcontainers import SortedList

class Event:
    def __init__(self, x, segment, is_start):
        self.x = x
        self.segment = segment
        self.is_start = is_start

    def __lt__(self, other):
        return self.x < other.x

def do_intersect(seg1, seg2):
    def orientation(p, q, r):
        val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
        return 0 if val == 0 else (1 if val > 0 else -1)

    p1, q1 = seg1
    p2, q2 = seg2

    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    return o1 != o2 and o3 != o4

def sweep_line_intersection(segments):
    events = []
    for seg in segments:
        events.append(Event(seg[0][0], seg, True))
        events.append(Event(seg[1][0], seg, False))

    events.sort()
    active_segments = SortedList(key=lambda seg: seg[0][1])
    intersections = []

    for event in events:
        seg = event.segment
        if event.is_start:
            idx = active_segments.bisect(seg)
            if idx > 0 and do_intersect(active_segments[idx - 1], seg):
                intersections.append((active_segments[idx - 1], seg))
            if idx < len(active_segments) and do_intersect(active_segments[idx], seg):
                intersections.append((active_segments[idx], seg))
            active_segments.add(seg)
        else:
            idx = active_segments.index(seg)
            if 0 < idx < len(active_segments) - 1 and do_intersect(active_segments[idx - 1], active_segments[idx + 1]):
                intersections.append((active_segments[idx - 1], active_segments[idx + 1]))
            active_segments.remove(seg)

    return intersections

# Example road network (segments)
road_segments = [
    ((1, 1), (5, 5)),
    ((2, 5), (6, 1)),
    ((3, 3), (7, 7)),
    ((4, 1), (8, 5))
]

# Detect intersections
intersections = sweep_line_intersection(road_segments)

# Visualization
plt.figure(figsize=(6, 6))
for seg in road_segments:
    plt.plot([seg[0][0], seg[1][0]], [seg[0][1], seg[1][1]], 'b')

# Mark intersections
for intersect in intersections:
    x, y = intersect[0][1]
    plt.scatter(x, y, color='red', zorder=3)

plt.xlabel("X-axis")
plt.ylabel("Y-axis")
plt.title("Road Intersection Detection")
plt.grid(True)
plt.show()

18.3 How It Works

18.4 Potential Enhancements

19. Competitive Programming & System Design Integration

19.1 Competitive Programming

The Sweep Line Algorithm is commonly used in coding competitions due to its efficiency in handling geometric and interval-based problems. Here are some problem categories where it excels:

19.2 System Design Integration

The Sweep Line Algorithm is used in large-scale systems for efficient geometric computations. Some applications include:

19.3 Challenges in System Design

20. Assignments

20.1 Solve 10 Problems Using the Sweep Line Algorithm

Complete the following problems to develop proficiency in implementing the Sweep Line Algorithm:

  1. Find all intersections among a given set of line segments.
  2. Compute the union of multiple rectangles and determine the total covered area.
  3. Given a list of time intervals, find the maximum number of overlapping intervals at any given time.
  4. Find the skyline silhouette of a city based on building height coordinates.
  5. Determine the closest pair of points in a 2D plane efficiently.
  6. Find the largest empty rectangle inside a given set of boundaries.
  7. Detect road intersections using GIS data.
  8. Optimize rendering in a graphics engine by removing hidden surfaces.
  9. Analyze stock price fluctuations using an event-based approach.
  10. Simulate drone flight paths to avoid mid-air collisions.

20.2 Use the Sweep Line Algorithm in a System Design Problem

Design a system for handling a massive dataset of time-based logs and optimize querying overlapping log entries efficiently.

Requirements:

20.3 Implement the Algorithm Under Time Constraints

Set up a competitive programming environment and aim to solve each of the following problems within 30 minutes:

By completing these assignments, you will develop a strong command over the Sweep Line Algorithm, making you proficient in both competitive programming and system design applications.