Merge overlapping 2D line segments

Problem Statement

You are given a list of line segments in a 2D plane. Each segment is defined by two endpoints (x1, y1) and (x2, y2). Two segments are considered "mergeable" if they are collinear and overlap or touch.

Your task is to write a function that takes a list of segments and returns a new list of segments where all overlapping or touching collinear segments have been merged into the longest possible continuous segments.

Function Signature

def merge_segments(segments: List[List[Tuple[float, float]]]) -> List[List[Tuple[float, float]]]

Constraints

• Each input segment is defined as [(x1, y1), (x2, y2)].
• You may assume segments are not degenerate (i.e., x1 != x2 or y1 != y2).
• Coordinates are floating-point numbers.

Example 1

Input: [[(0, 0), (2, 2)], [(1, 1), (3, 3)], [(5, 0), (6, 0)]] Output: [[(0, 0), (3, 3)], [(5, 0), (6, 0)]] Explanation: The first two segments share the same slope and intersect, so they merge. The third is separate.

Example 2

Input: [[(0, 0), (1, 0)], [(2, 0), (3, 0)]] Output: [[(0, 0), (1, 0)], [(2, 0), (3, 0)]] Explanation: These are collinear but do not touch or overlap, so they remain separate.

Edge Cases

• Vertical segments (where x1 == x2).
• Segments provided in reverse order (e.g., [(2, 2), (0, 0)]).
• A single point or single segment input.