ddt's blog

Merging overlapping line-segments
By ddt, 9 years ago, In English

Help needed in the following problem :

There are N (1<=N<=200000) line segments (end-point coordinates are positive integers less than 1e9). The task is to merge the line segments that are overlapping and finally print the coordinates of all the merged line-segments.

Sample Test Case

N = 4
Line segments:
[(1,1) (5,1)]
[(4,1) (7,1)]
[(3,3) (9,3)]
[(5,3) (8,3)]

The answer for this test case would be :
[(1,1) (7,1)]
[(3,3) (9,3)]

My Approach : Consider each line segment as a vertex and make edges between segments U and V if U and V overlaps. Then, find the connected components. For each connected components, answer can be calculated by taking the min of left coordinates and maximum of right coordinates. But this approach is O(N^2) and will not work for N=200000.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You could group segments on the same line together (by creating a map from a slope-intercept pair to a list of segments). Then, you just have to solve the merging intervals problem on each group.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Simple and neat !!! Thanks a lot :)
    I feared that we may have to use line-sweep techniques.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If your segments are all straight lines on X axis (as your example case) then i think you can group them by Y dimension and solve each separately. For solving each one you first sort them by X axis then you iterate from left to right and add +1 if you encounter an opening of a segment and -1 if you encountered a closing. When you come to 0, your interval stops (this works because every point starts on the left and ends on the right, you can think of that as having a nice form of nested parenthesis and you want to find the outer one)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, the segments are not parallel to x-axis. They can have any slope.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      oh i see, well the same idea applies here aswell. You just need to group them differently, they must have the same slope and another information (for instance from a slope you can calculate at which point it would intersect the X axis) if you find two segments with the both informations the same, they can overlap. From then on, it's really the same problem.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That is exactly what mkirsche has described in the first comment !! Simple and elegant.

        → Reply