Intersections, Line Segments

A line segment is the convex hull of two points, called the endpoints (or vertices) of the segment. We are given a set of \(n\) line segments, each specified by the x- and y-coordinates of its endpoints, for a total of \(4n\) real numbers,and we want to know whether any two segments intersect.

In a standard line intersection problem a list of line segments in the Euclidean plane are given if they cross each other.Simple algorithms examine each pair of segments. However, if a large number of possibly intersecting segments are to be checked, this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence. The most common, more efficient way to solve this problem for a high number of segments is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on binary search trees.

A common way to simplify a proximity related problem such as computing the Voronoi diagram is to use a sweep line.The algorithm first sorts the end points along the \(x\) axis from left to right, then it passes a vertical line through all points from left to right and checks for intersections.

The status of the sweep line is the set of segments intersecting it. The status changes while the sweep line moves downwards, but not continuously. Only at particular points is an update of the status required. We call these points event points of the plane sweep algorithm. The moments at which the sweep lien reaches an end point are the only moments when the algorithm actually does something: it updates the status of the sweep line and performs some intersection tests. In particular, if the vent point is the upper endpoint of a segment, then a new segment starts intersecting the sweep line and must be added to the status. This segment is tested for intersection against the ones already intersecting the sweep line and must be deleted from the status. This segment is tested for intersection against the ones already intersecting the sweep line. If the even point is a lower endpoint, a segment stops intersecting the sweep line and must be deleted from the status. This way we only test pairs of segments for which there is a horizontal line that intersects both segments. Unfortunately, this is not enough: there are still situations where we test a quadratic number of pairs, where as there is only a small number of intersection points. A simple example is a set of vertical segments that all intersect the x-axis. So the algorithm is not output-sensitive. The problem is that two segments that intersect the sweep line can still be far apart from each other.

Considering all the above problems, there is a way of turning the ideas into an efficient algorithm:

Following are detailed steps.

1) Let there be \(n\) given lines. There must be \(2n\) end points to represent the \(n\) lines. Sort all points according to x coordinates. While sorting maintain a flag to indicate whether this point is left point of its line or right point.

2) Start from the leftmost point. Do following for every point

…..a) If the current point is a left point of its line segment, check for intersection of its line segment with the segments just above and below it. And add its line to active line segments (line segments for which left end point is seen, but right end point is not seen yet). Note that we consider only those neighbors which are still active.

….b) If the current point is a right point, remove its line segment from active list and check whether its two active neighbors (points just above and below) intersect with each other.