Merge Overlapping Collinear Lane Segments Given as Integer Point Lists

Lane geometry is given as a list of straight lane segments. Each segment is a list of integer points [x, y] that all lie on one straight line, listed in order along it. Several segments may lie on the same line and overlap. Merge every group of overlapping segments that lie on the same line into one segment containing all of their points, and return the resulting segments.

The interviewer specifically asked how the approach handles a segment whose slope is 0. Your function must handle every orientation, including horizontal and vertical segments.

Function Signature

def merge_lane_segments(segments: list[list[list[int]]]) -> list[list[list[int]]]:

segments[i] is the list of points of segment i, and each point is [x, y].

Rules

• Two segments lie on the same line when all of their points are collinear. Segments on different lines are never merged, even if they cross, touch or are parallel.
• The extent of a segment is the closed stretch of its line from its first point to its last point. Two segments on the same line overlap when their extents share at least one point; touching at a single endpoint counts.
• Merging is transitive: if A overlaps B and B overlaps C, all three become one segment, even when A and C do not overlap.
• Each output segment, merged or not, is the list of the distinct points of its member segments, sorted by x ascending and then by y ascending.
• Output order: group the output segments by line, and order the lines by the index of the first input segment that lies on each line. Within one line, order the output segments by their first point, by x and then by y.

Constraints

• 1 <= len(segments) <= 10^4
• 2 <= len(segments[i]) <= 100, and the total number of points over all segments is at most 10^5.
• Every coordinate is an integer in [-10^4, 10^4].
• Within a segment, the points are distinct, collinear, and sorted by x ascending and then by y ascending.
• Different segments may share points or be identical.

Examples

Example 1

Input: segments = [[[1, 1], [2, 2], [4, 4]], [[2, 1], [4, 2]], [[3, 3], [6, 6]], [[7, 7], [8, 8]]]
Output: [[[1, 1], [2, 2], [3, 3], [4, 4], [6, 6]], [[7, 7], [8, 8]], [[2, 1], [4, 2]]]

Segments 0, 2 and 3 lie on the line y = x, and segment 1 lies on y = x / 2. On y = x, segment 0 spans x from 1 to 4 and segment 2 spans 3 to 6, so they merge into one segment holding the points of both; segment 3 spans 7 to 8 and stays separate. The line y = x holds input segment 0, so its output segments come before the one on y = x / 2.

Example 2

Input: segments = [[[0, 0], [2, 0]], [[1, -2], [1, 0]], [[2, 0], [5, 0]], [[1, 3], [1, 5]], [[6, 0], [7, 0]]]
Output: [[[0, 0], [2, 0], [5, 0]], [[6, 0], [7, 0]], [[1, -2], [1, 0]], [[1, 3], [1, 5]]]

Segments 0 and 2 lie on the horizontal line y = 0 and touch at (2, 0), so they merge; segment 4 starts at x = 6, after the merged extent ends at x = 5, so it stays separate. Segments 1 and 3 lie on the vertical line x = 1 and do not overlap. Segment 1 ends at (1, 0), a point inside segment 0, but it lies on a different line, so the two are not merged.

Example 3

Input: segments = [[[0, 0], [2, 1], [6, 3]], [[0, 1], [2, 2]], [[2, 1], [4, 2]]]
Output: [[[0, 0], [2, 1], [4, 2], [6, 3]], [[0, 1], [2, 2]]]

Segments 0 and 2 lie on y = x / 2, and segment 2 lies inside segment 0's extent, so they merge and the point (4, 2) is added. Segment 1 lies on the parallel line y = x / 2 + 1 and is not merged.