Traversing Line Segments

Question

I have a question on this algorithmic problem; I'll paste the problem then go over my current thoughts and solution.

There are N (up to 100,000) line segments defined as [(x1, y1), (x2, y2)], where x1 < x2 and y1 < y2 (e.g. The line segments have positive slope). No line segments touch or intersect, even at endpoints. The first segment has (x1, y1) = (0, 0). Imagine each segment as a 2-D hill a person has to climb.

A person starts at (0, 0) and lands on the first hill. Whenever a person lands on a hill, he climbs to the end, which is (x2, y2) and jumps straight down. If he lands on another hill (anywhere on the segment), the process continues: he climbs that hill and jumps. If there are no more hills, he falls to -INFINITY and the process is over. Each hill (x1, y1) -> (x2, y2) should be regarded as containing the point (x1, y1) but not containing the point (x2, y2), so that the person will land on the hill if he falls on it from above at a position with x = x1, but he will not land on the hill if he falls on it from above at x = x2.

The objective is to count how many hills he touches.

My current thoughts

I'm thinking of sweeping a line across the plane along the x-axis. Each segment consists of a BEGIN and END event; everytime we encounter the beginning of a line segment, we add it into a set. Every time we encounter the ending of a line segment, we remove it from the set. And when we hit the END point of the current hill we are on, we should check the set for the highest hill that we can land on. However, I don't know how to determine how to check this quickly, because there could be potentially N entries inside the set. Also, after jumping on to another hill, the order of these will change because the slopes of each segment are probably different, and I don't know how to account for this difference.

Any thoughts?

Answer 1

Barron, your algorithm is perfectly correct. The order of elements in your sorted list will not change as the sweep line moves, because if that happened you would have an intersection of line segments.

You just need a way to keep track of the sorted line segments. One way to do this would be to keep a map of line segments, in which the comparison operator compares line segments by the y value on the segment as calculated by the current x value of the current sweep location. Inserting, deleting, and querying from this map is O(log(n)).

Answer 2

In pre-processing you can traverse all segments and add points in an stl multimap< pair, linesegment> or something similar. Cost of this pre-processing would be O(NlogN). Then you can continue with your sweep line method. You need iterate points from multimap. Because all points are sorted, and contains reference to line the point corresponds to, it would cost O(N).

Answer 3

I think a line sweep algorithm is a good idea here. Let me summarize your algorithm so far and add my improvements:

• You are sweeping a line from left to right.
• You have an active list which lists all currently active segments. These are segments intersecting with the sweepline
• Every endpoint of every line segment is considered an 'event'
• when the line sweeps across the 'start' of a segment, the segment gets added into the list of active segments
• When the line sweeps across the 'end' of a segment, the segment gets removed from the list of active segments
• If there are no line segments in the active set upon removal of a line segment, the process ends
• If there are line segments in the active set upon removal of a line segment, we need to determine
  • A) Whether there are any line segments in the active set with portions 'below' the previously removed end vertex, and
  • B) Which of these line segments the person will land on.

The idea is to sort your line segments in the 'active set' such that this query is efficient. What I'm thinking is that if we know a line's slope and y intercept we can compute intersection points for a start vertex's x position

GreaterThan(segment1,segment2){ // is segment 1 higher than segment 2?
//y = mx + b; compute y value of point on segment 2 for a given x value from s1
//that is, m and b are slope and y-intercept of s2
yVal = m * (segment1.first.x) + b
if (yVal < segment1.first.y)
   return true //the point on s2 corresponding to s1.first is lower than s1.first
return false
}

Because lines don't intersect, then you can assume no other line will 'go through and over' this line.

If we avoid adding any line segments whose start vertices are higher than the end vertex of our "person's" current line, then we should successfully avoid adding any extraneous line segments to the active set (i.e. line segments "above" our current one)

Now we just need to worry about the special case of the vertex of the last line segment not being 'landable'. Because vertices are events, we will process all events before we do our segment testing. this way, you will not accidentally land on the end vertex of a line in the active set, but you WILL land on a line segment that has just been added.

Now that we have a sorted list of line segments in the active set, we can query it in constant time to just get the top one, and adding a new one should only take logarithmic time.

How does this sound?

Answer 4

Here's a rough direction in Haskell. "segments" are the line segments. (In this example, the third segment is slightly above the second segment in order to test the code.) "matches" finds the hills/segments that place the top of the last segment, pt (x0,y0), within their x bounds and above or equal to the y corresponding to their affine transformation of x0 ("affine" calculates the affine function for the segment -- the ax+b, so to speak). Finally, countHills tests the possible matches for the next hill and chooses the one with the closest y to y0 (calculated by the affine a*x0+b), and outputs the result, accumulating the hills climbed on in order. Clearly this idea may need optimization for much longer segment lists.

The result output below shows the first and third segments. The second hill/segment is not in the result because it is lower than the third - we land on the third instead:

*Main> countHills segments
[((0.0,0.0),(2.0,5.0)),((1.0,1.5),(5.0,3.0))]

import Data.List

segments = [((0,0),(2,5)),((1,1),(5,2)),((1,1.5),(5,3))]

top segment = snd segment

matches pt = 
  let x0 = fst pt 
      y0 = snd pt
  in filter (\x -> x0 >= fst (fst x) 
                   && x0 < fst (snd x) 
                   && (affine x) x0 <= y0) segments  

affine segment = 
  let x1 = fst $ fst segment
      y1 = snd $ fst segment
      x2 = fst $ snd segment
      y2 = snd $ snd segment
  in (+ ((x1*y2-x2*y1) / (x1-x2))) . (* ((y2-y1) / (x2-x1)))

countHills segments = countHills' (head segments) [] where
  countHills' x result = 
    let hills = matches $ top x
        x0 = fst (top x)
        y0 = snd (top x)
    in if null hills 
          then result ++ [x]
          else let nextHill = 
                     minimumBy (\a b -> compare 
                                        (y0 - (affine a) x0) 
                                        (y0 - (affine b) x0)) hills
               in countHills' nextHill (result ++ [x])