Line segment intersection detection using sweep line algorithm

Line segment intersection detection problem

Intersection detection of geometric objects is a fundamental operation in computational geometry. It has a wide range of applications, some of which are listed below:

• Collision detection in computer games and simulations.

• Ray shooting in computer graphics.

• Map overlay in geographic information systems (GIS).

• Collision avoidance in robot navigation.

Problem statement: Given a set $S = \{s_1, s_2, \dots, s_n\}$ of $n$ line segments in the plane, report all the points of intersection.

The line segments are defined by their endpoints.

Naive algorithm: Check all pairs

The number of intersections of $n$ line segments ranges from zero, in case no pair of lines intersect, to $\binom{n}{2} = O(n^2)$, in case all pairs intersect.

The simple naive method checks for intersections between all pairs of line segments. Because all pairs of line segments can potentially intersect, the naive algorithm is optimal for the worst-case inputs with a time complexity of $O(n^2)$.

For problems where the size of the output varies, output-sensitive algorithms are preferred because their time complexity depends on both the problem size and the output size. For an instance of the line segment intersection problem with $n$ line segments, let $k$ denote the number of intersections.

We’ll now discuss an $O((n+k) log(n))$ sweep line algorithm for line segment intersection detection. For a wide range of geometric problems in 2D planes, sweep line algorithms are a fundamental and efficient approach. These algorithms involve the systematic sweeping of a vertical or horizontal line across the plane to process and analyze geometric objects, such as line segments, points, or other geometric entities.

General position assumption

When solving geometric problems, certain special configurations of the geometric input can be conveniently ignored to keep the algorithm simple. These special cases are handled separately. When they are ignored, the input to the problem is considered to be in a general position, and the general position assumption defines the coincidental configurations.

For the line segment intersection problem, the following special configurations are ignored:

• No three lines intersect at the same point.

• No endpoint lies on another line segment.

• The $x$-coordinates of the endpoints and intersection points are unique.

Sweep line algorithm

A vertical sweep line scans the input from left to right. The intersection of the sweep line with the line segments is used to discover imminent intersection points.

Sweep line status and event points

Let $l$ denote the vertical sweep line. The line segments that intersect the sweep line $l$ are stored in order from top to bottom. This is known as the sweep line status.

We notice that the sweep line status only changes when the sweep line encounters certain special points in the input. These points are known as event points and are listed below, together with the changes that they trigger in the sweep line status.

• Left endpoint of a line segment $s$: Add the line segment $s$ in the correct place.

• Right endpoint of a line segment $s$: Remove the line segment $s$.

• Intersection point of a pair of line segments $s$ and $r$: Swap the order of $s$ and $r$.

Because the sweep line status only changes at the event points, instead of continuously scanning the plane, the sweep line can jump from one event point to the next one.

To ensure $O((n+k) log(n))$ time complexity, the sweep line status and the event points are stored in data structures that support $O(log \ n)$ operations.

Data structures

The sweep line status is the top-to-bottom ordered list of the line segments that intersect the sweep line and is stored in an ordered dictionary. The event points are stored in a priority queue. The following operations are supported by each of these data structures.

Ordered dictionary for the sweep line status

The following operations are supported by the ordered dictionary in $O(log \ n)$:

• Insert a line segment

• Delete a line segment

• Fetch the predecessor

• Fetch the successor

• Swap two line segments

Priority queue for the event points

The following operations are supported by the event queue in $O(log \ n)$:

• Insert an event point

• Delete an event point

• Extract the event point with the highest priority

Algorithm with case analysis

The sweep line algorithm starts with an empty event queue and an empty ordered dictionary. At the start, the endpoints of all the line segments are inserted into the event queue. In the event queue, the point with the lowest $x$-coordinate has the highest priority, indicating that the sweep line moves from left to right. The intersection points are dynamically added to the event queue and removed from it during the course of the algorithm.

Note that any two intersecting line segments are adjacent on the sweep line right before the intersection. Therefore, the algorithm only inserts intersection points between adjacent line segments into the event queue, postponing the discovery of the intersections between nonadjacent line segments to a later stage.

When a new line segment gets inserted into the priority queue, the algorithm checks for its intersection with the preceding and succeeding line segments instead of checking for its intersection with all $O(n)$ line segments on the sweep line. This ensures that $O(log \ n)$ time is spent in processing each event point.

Next, we see how the sweep line status and the event queue change for the three kinds of event points. In the next three figures, the dashed gray line is the sweep line.

• Left endpoint of line segment $s$:
  The discovery of the left endpoint marks the discovery of a new line segment triggering the following changes to the sweep line status and event points:

  • Insert $s$ on the sweep line. Let $q$ and $t$ be the line segments above and below $s$ on the sweep line.

  • Remove the intersection point between $q$ and $t$ (if applicable), shown as a red circle in the figure below, from the event queue since they are no longer adjacent.

  • Check for intersections between the pairs $q, s$ and $s,t$, and add them to the event queue if the line segments are intersecting.

• Right endpoint of line segment $s$:
  The discovery of the right endpoint triggers the following changes to the sweep line status and event points:

  • Let $q$ and $t$ be the line segments above and below $s$ on the sweep line.

  • Remove $s$ from the sweep line status.

  • Check for an intersection point between $q$ and $t$ and add it to the event queue if it exists to the right of the sweep line.

Note that possible intersections between the pairs $q,s$ or $s,t$ lie in the past and are already discovered by the algorithm.

• Intersection point of line segments $s$ and $r$:
  When an intersection point is discovered, it is added to the solution, and the following changes are made to the sweep line status and event points:

  • Let $q$ be the predecessor of $r$ and $t$ be the successor of $s$ on the sweep line.

  • Swap the line segments $r$ and $s$ on the sweep line.

  • Remove the intersection point between the pairs $q,r$ and $s,t$ (if applicable), shown as a red circle in the figure below, from the event queue since these pairs are no longer adjacent.

  • Check for intersection points between the pairs $q, s$ and $r,t$ and add them to the event queue if they exist to the right of the sweep line.

To summarize, the intersection of any pair of line segments that become adjacent on the sweep line is checked, and the intersection point is added to the event queue. The intersection point of any pair of line segments that are no longer adjacent, is removed from the event queue.

Complexity analysis

For an input with $n$ line segments and $k$ intersection points, there are $2n+k = O(n+k)$ events that are processed by the algorithm. Each event requires $O(log \ n)$ time for updating the data structures. Therefore, the time complexity of the sweep line algorithm is $O((n+k) log \ n)$.

The following course on the Educative platform helps developers learn and test their problem-solving skills.