Let $S = \{ s_1, s_2, \dots , s_n\}$ be a set of line segments in the plane such that the intersection of any two segments is either empty or a single point. We want to find an effective algorithm which looks for all intersections of these segments. Moreover, we ask the algorithm to assign to every intersection the list of all segments on which it lies.
How to compute the intersection of two segments $ab$ a $cd$? Every point of the segment $ab$ is of the form
$$ p= \lambda a + (1-\lambda) b\,, \quad \mbox{where} \quad \lambda \in [0,1]\,. $$Similarly a point on $cd$ is
$$ q= \mu c +(1-\mu) d\,, \quad \mbox{where}\quad \mu\in [0,1]\,. $$The intersection is obtained by solving the equation
$$ \lambda a+ (1-\lambda)b = \mu c +(1-\mu) d\,. $$Comparing $x$ and a $y$-coordinates we get the following system of two linear equations with two unknowns $\lambda$ a $\mu$
\begin{align*} \lambda a_x +(1-\lambda)b_x &= \mu c_x + (1-\mu)d_x\\[3pt] \lambda a_y +(1-\lambda)b_y &= \mu c_y + (1-\mu)d_y \end{align*}If there is a solution of this system such that $\lambda \in [0,1]$ and $\mu \in [0,1]$, the segments have an intersection. In opposite case the segments do not have an intersection.
A trivial algorithm takes all pairs of segments $(s_i, s_j)$, $1\leq i\lt j\leq n$, and computes their intersections. Since the number of all pairs is $\binom{n}{2}$, the time complexity of such an algorithm is $O(n^2)$. In many cases it happens that the number of intersections is much less than $n^2$ which makes this algorithm (in these cases) ineffective. Hence we deal with an algorithm which is much more suitable for such cases and works in time
$$ O\big((n+k)\log n\big), $$where $k$ is the number of intersections found. This algorithm uses the method of sweep line.
The method of sweep line is based on the following geometric concept: A horizontal line - called a sweep line - moves in the plane, its path begins above all the segments of $ S $ and ends below them. The algorithm slowly moves the line from the top to bottom and along the way performs some actions. These actions occur only when the sweep line passes through prominent points, so-called events. Only two type of points are considered as events. Each endpoint of all the given segments is an event and all the intersections already calculated by the algorithm are events. The algorithm detects whether the segments from the nearest left and right neighborhoods of the event have an intersection below the sweep line. If they do, the algorithm classifies the intersection among events into so called queue.
Two structures are usually associated with the sweep line method - an event queue and a binary balanced tree. The queue of events $Q$ is a ordered sequence of points of interest (events) for the algorithm. The layout is "from top to bottom" and "from left to right", which is formally lexicographic ordering: a point $p$ is stored before a point $q$ if
$$p_y\gt q_y \quad \text{or} \quad \left( p_y=q_y \text{ and }p_x\lt q_x\right).$$Basically, the event queue determines the order in which the sweep line passes our events. When the sweep line passes an event, this event is removed from the queue, while some other events may be queued. In our algorithm, all the endpoints of the segments from the set $S$ are initially stored in the queue.
A further structure associated with the sweep line algorithm is a binary balanced tree ${\mathcal T}$. It describes the order of segments which intersect the sweep line $l$. This order is taken from the left to the right and it is captured in the leaves of the tree ${\mathcal T}$. The nodes of the tree are named after leaves which are rightmost in the left subtree of this node.
Denote $L(p)$ the set of the segments from the set $S$ which have $p$ as its lower endpoint, denote $C(p)$ the set of the segments from $S$ which contain $p$ as its inner point, and finally, let $U(p)$ be the set of the segments which have $p$ as its upper endpoint.
If the position of the sweep line is just above the event $p$, the tree ${\mathcal T}$ contains the segments from $L(p)\cup C(p)$ in its leaves. It can contain additional segments but surely not from the set $U(p)$. When the sweep line passes the point $p$, the segments $L(p)$ will disappear from the tree ${\mathcal T}$, while the segments from $U(p)$ will be added and the segments from $C(p)$ will change their order. We formally do this in the following way: at first, we remove the leaves in $L(p)\cup C(p)$ from the tree ${\mathcal T}$ and rebalance the tree after each removal. Then we add the segments in $C(p)\cup U(p)$ between the leaves of the tree in the right order and we rebalance the tree again. (In fact, we rebalance the tree after adding any single segment.) If the union $L(p)\cup C(p)\cup U(p)$ contains at least two segments, we mark $p$ as an intersection. In any case we discard the point $p$ from the event queue $Q$.
When the sweep line passes through the point $p$ other actions of the algorithm consist of computing the intersections of the segments passing through the point $p$ and adjacent segments (which are the nearest left and right segments to $p$). We use the order of segments just under the event $p$, eg. a moment after the sweep line passes $p.$
If $C(p)\cup U(p)=\emptyset$, we find out whether the nearest segment to the left of $p$ (denote it as $s_l$) and the nearest segment to the right of $p$ (denote it as $s_p$) have an intersection under the sweep line. If they do, we put the intersection into the queue.
If $C(p)\cup U(p)\ne\emptyset$, denote $s'$ and $s''$ the leftmost segment and the rightmost segment from $C(p)\cup U(p)$, respectively. Let $s_l$ be the nearest left neighbour of the segment $s'$ and let $s_p$ be the nearest right neighbour of the segment $s''$. We look for the intersections $s' \cap s_l$ and $s''\cap s_p$ under the sweep line $l$. If some of them exist we put them into the event queue $Q$.
Algorithm FindIntersections(\(S\))
Input. A set \(S\) of line segments in the plane.
Output. The set of intersection points among the segments in $S$ such that each intersection point is associated with the segments which contain it.
Algorithm HandleEventPoint(\(p\))
Let \(U(p)\) be the set of segments whose upper endpoint is \(p\); these segments are stored with the event point \(p\). (For horizontal segments, the upper endpoint is by definition the left endpoint.)
Find all segments stored in \({\mathcal T}\) that contain \(p\); they are adjacent in \({\mathcal T}\). Let \(L(p)\) denote the subset of segments found whose lower endpoint is \(p\), and let \(C(p)\) denote the subset of segments found that contain \(p\) in their interior.
if \(L(p) \cup U(p) \cup C(p)\) contains more than one segment
then Report \(p\) as an intersection, together with \(L(p)\), \(U(p)\), and \(C(p)\).
Delete the segments in \(L(p) \cup C(p)\) from \({\mathcal T}\).
Insert the segments in \(U(p) \cup C(p)\) into \({\mathcal T}\). The order of the segments in \({\mathcal T}\) should correspond to the order in which they are intersected by a sweep line just below \(p\). If there is a horizontal segment, it comes last among all segments containing \(p\).
(∗ Deleting and re-inserting the segments of \(C(p)\) reverses their order. ∗)
if \(U(p) \cup C(p) = \emptyset\)
then Let \(s_l\) and \(s_p\) be the left and right neighbors of \(p\) in \({\mathcal T}\).
FindNewEvent \((s_l, s_p, p)\)
else Let \(s'\) be the leftmost segment of \(U(p) \cup C(p)\) in \({\mathcal T}\).
Let \(s_l\) be the left neighbor of \(s'\) in \({\mathcal T}\).
FindNewEvent \((s_l, s', p)\)
Let \(s''\) be the rightmost segment of \(U(p) \cup C(p)\) in \({\mathcal T}\).
Let \(s_p\) be the right neighbor of \(s''\) in \({\mathcal T}\).
FindNewEvent \((s'', s_p, p)\)
if \(s_l\) and \(s_p\) intersect below the sweep line, or on it and to the right of the current event point \(p\), and the intersection is not yet present as an event in \({\mathcal Q}\)
then Insert the intersection point as an event into \({\mathcal Q}\).
We have to show that every intersection is computed when the sweep line passes an event. Let $p$ be an intersection of two or more segments. Suppose that all the intersections above the point $p$ have been already computed and included into the event queue.
In the picture the events in which $p$ is detected as the intersection are denoted by the red colour.
We need the Euler Formula from graph theory to prove it.
Every bounded face is bordered at least by three edges, every edge is adjacent to at most two faces. That is why the number of all faces (included the unbounded one) is
$$n_f\le \frac{2n_e}{3}+1.$$Substituting this inequality into the Euler inequality, we get
$$n_v-n_e+\frac{2n_e}{3}+1\ge 2.$$From here we get the required inequality.
To order $2n$ endpoints of given segments lexicographicly into a queue it takes time $O(n\log n)$. To rebalance a binary tree with at most $n$ leaves after discarding or adding a leaf needs the time $O(\log n)$.
For an event $p$ denote $m(p)$ the number of elements of the set $L(p)\cup C(p)\cup U(p)$. The running time of the algorithm HANDLE EVENT POINT in the event $p$ is
$$ O\big(m(p)\log n\big)\,. $$Hence the running time of the whole algorithm is
$$ O\big( n\log n\big) + O\big(\sum_p m(p) \log n\big)\,. $$To compute this sum we apply the Euler Formula to the planar graph determined by the set $S$. Verteces of this graph are all endpoints and intersections of segments from the set $S$. Denote $s(p)$ the degree of the vertex $p$, i.~e. the number of edges coming from $p$. Obviously, $m(p)\le s(p)$.
Now it is sufficient to realize that $\sum_p s(p) = 2n_e$ and $n_v \leq 2n +k$. Applying Corollary 2.4 we get
\begin{align*} \sum m(p) &\leq \sum s(p) = 2n_e \leq 6(n_v-1) \leq 6(2n+k-1)\\ & = 12n+6k-6\leq 12(n+k)\,. \end{align*}So the running time of the algorithm is $O\big((n+k)\log n\big)$.