2
$\begingroup$

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 ?

$\endgroup$
5
  • 1
    $\begingroup$ Segment trees + scanline? $\endgroup$
    – Dmitry
    May 6, 2023 at 20:33
  • $\begingroup$ Why do you have "Red-blue" in the title? You don't mention colors in the body of your question $\endgroup$
    – HEKTO
    May 18, 2023 at 4:37
  • $\begingroup$ @HEKTO: that's a set expression to denote two sets of entities in computational geometry. $\endgroup$
    – user16034
    May 18, 2023 at 16:49
  • $\begingroup$ So, vertical segments have one color, and horizontal ones - another color, right? $\endgroup$
    – HEKTO
    May 18, 2023 at 18:04
  • $\begingroup$ @HEKTO: absolutely, and you only care about intersections between one color and the other. $\endgroup$
    – user16034
    May 19, 2023 at 6:15

1 Answer 1

0
$\begingroup$

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:

  • "beginning of horizontal segment" - add this segment to the status $S$.
  • "ending of horizontal segment" - remove this segment from the status $S$.
  • "vertical segment" - make two binary searches in the status $S$, using two $y$-coordinates ($y_{min}$ and $y_{max}$) of this segment, and find the range of horizontal segments, intersecting this vertical segment. Calculate intersection points for all segments in this range.

As you can see, this algorithm doesn't need any complex geometric data structures (segment tree etc.).

$\endgroup$
1
  • $\begingroup$ Makes sense, thank you. $\endgroup$
    – user16034
    May 21, 2023 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.