Finding combination of line segments

Question

How would I go on about finding a combination of colinear line segments? Here's what I mean:

Example input #1:
line_1 (0,4)
line_2 (3,5)
line_3 (6,10)
line_4 (7,10)
line_5 (11,12)

(The line segments in the input are presented in the increasing order of the value of their starting point)

Example output #1:
line_1 (0,5)
line_2 (6,10)
line_3 (11,12)

I was hoping to find a clean algorithm to do this but couldn't come up with anything

What I have tried:

The solution could be to cycle through the items in the input, and if the value of current segment's starting point is larger than the value of the previous segment's ending point (current and previous segments do not intersect), then you should add this as a new starting point to the output

Then, once you have added the starting point, if the value of current segment's ending point is smaller than the value of the next segment's starting point (current and next segments do not intersect), then you should add this as an ending point to the previously added starting point in the output

By using this method, the line segments that do not have an intersection with the previous or the next segment in the input will be added to the output normally, and if two line segments intersect with each other, only the starting point of the first one and the ending point of the second one will be added to the output as a new line segment

This method however fails if one line segment is contained entirely within another line segment

Working solution found:

After some trial and error I am fairly certain that I found a working algorithm for this problem. Only adding the starting and the ending points of each segment if they are not contained within any other segment in the input seems to do the trick.

Each point has to be checked against every other segment in the input. For each segment, if the value of the current point is strictly larger than the start of the segment and strictly smaller than the end of the segment, it shouldn't be added to the output

Additionnaly, a starting point of one segment should not be added to the output if there is a segment with the ending point of same value, and an ending point of one segment should not be added to the output if there is a segment with the starting point of same value.

Note: this solution introduces duplicate points being added to the output if any segments from the input share a starting point or an ending point

Once you remove the duplicate points (leaving only one instance of every group of duplicate points), you will be left with a list of points that define starts and ends of the line segments that define the combination of the line segments from the input

Answer 1

You have a list of closed intervals sorted by increasing start, and want to find their union as a set of disjoint closed intervals. This can be done in one pass by a greedy algorithm: check whether the current interval $c$ overlaps with the next interval $n$ and

• if there is overlap, set $c\leftarrow c\cup n$
• otherwise output $c$ and set $c\leftarrow n$

Because the input is sorted, as soon as $n$ is disjoint from $c$ we know that all further intervals yet to be processed are also disjoint from $c$, so we can output $c$ and move on.