I need to efficiently find the intersections between a set of vertical line segments and a set of horizontal ones. The segments in both families can overlap (but there are no duplicates). Presumably this is done in time $O(n\log n+k)$ for $n$ segments and $k$ intersections.
Can someone describe an ad-hoc solution or provide a reference ?
The ad-hoc algorithm for the problem with $m$ horizontal and $n$ vertical line segments might be the following one:
Step 1. Project beginning and ending points of all segments on the $OX$ axis and create an array of events, corresponding to $x$-coordinates of these points. Each event consists of three components - the point $x$-coordinate, a pointer to the segment it belongs to, and the event type from the set {"beginning of horizontal segment", "ending of horizontal segment", "vertical segment"}. The size of this array is $2m+n$. Sort this array by the $x$-coordinate of events (for simplicity we'll assume that all the $x$-coordinates are unique).
Step 2. Sweep the set of segments from left to right using the array of events, created earlier. Each step of the sweeping loop will update or use the status $S$. This status is simply a set of horizontal segments, ordered by their $y$-coordinate, and it can be represented by any type of balanced binary tree. The status is initially empty, and its size never exceeds $m$. Actions, taken on each step of the sweeping loop, depend on the current event type:
As you can see, this algorithm doesn't need any complex geometric data structures (segment tree etc.).
