Line Sweep

Line sweep algorithms process a set of points or segments by sweeping a conceptual line across the plane, stopping to handle events as the sweep line hits endpoints. This reduces problems to 1D.

Java example for rectangle intersection:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

List<Rect> findOverlaps(List<Rect> rects) {
  
  // Sort rectangles by top y coordinate
  Collections.sort(rects, (a, b) -> Integer.compare(a.y1, b.y1));

  TreeSet<Rect> sweepLine = new TreeSet<Rect>(
      (a, b) -> Integer.compare(a.x1, b.x1));

  List<Rect> result = new ArrayList<>();
  for (Rect r : rects) {
    Rect floor = sweepLine.floor(r);
    if (floor != null && floor.overlaps(r)) {
      result.add(floor);
      result.add(r);
    } 
    sweepLine.add(r);
  }

  return result;
}

C++ example for interval intersection:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

vector<pair<int, int>> lineSweep(vector<pair<int, int>> segments) {

  sort(segments.begin(), segments.end()); 

  set<pair<int, int>> sweepLine; 
  vector<pair<int, int>> intersections;

  for (auto segment : segments) {
    auto floor = sweepLine.floor(segment);
    if (floor != sweepLine.end() && floor->second > segment.first) {
      intersections.push_back(*floor);
      intersections.push_back(segment);
    }
    sweepLine.insert(segment);
  }

  return intersections;
}

Python example for closest pair:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from sortedcontainers import SortedList

def closestPair(points):

  points.sort()

  sweepLine = SortedList() 
  closest = float('inf')

  for p in points:
    neighbor = sweepLine.find_le(p[0])
    if neighbor:
      closest = min(closest, distance(p, neighbor)) 

    sweepLine.add(p)
  
  return closest

Line sweep reduces problems to 1D while handling events, often speeding up computational geometry algorithms.

Line sweep is an algorithmic technique where a virtual line moves across the plane to solve geometric problems, such as finding intersections, calculating union length, and more. Let’s explore a simple example to understand the concept: finding all intersecting pairs of a given set of line segments on a plane.

Problem

You have a set of horizontal line segments, and you want to find all the pairs that intersect at their endpoints.

Line Sweep Solution

1. Sort the Endpoints: First, you need to sort the endpoints of the line segments based on their x-coordinates.
2. Sweep Line: Imagine a vertical line (called the sweep line) that moves from left to right across the plane.
3. Handle Events: As the sweep line encounters the endpoints of the segments, it performs specific actions:
   • When the sweep line reaches the left endpoint of a segment, add that segment to a set (e.g., a balanced binary tree).
   • When the sweep line reaches the right endpoint of a segment, remove that segment from the set and check if its neighbors in the set intersect with it.
4. Record Intersections: If two neighboring segments intersect, record this intersection.

Pseudocode

sort(endpoints)

for endpoint in endpoints:
    if endpoint is left:
        add segment to set
    else:
        check intersection with neighbors in set
        remove segment from set

Visual Explanation

Segments:  ___________   ________    ____________

Sweep Line:  |        |        |         |         |

Events:     Left    Right   Left     Right   Left    Right

Key Takeaway

• The line sweep algorithm efficiently handles geometric problems by sorting events and processing them as a virtual line sweeps across the plane.
• In this simple example, line sweep is used to find intersecting pairs of horizontal line segments, making the problem more tractable by breaking it down into a sequence of simple events.