Merge overlapping 2D line segments
You are given a list of 2D line segments. Each segment is represented as a list of 2D points [(x1,y1), (x2,y2), ...] that all lie on the same straight line.
Within a segment, the points are already sorted along the segment. Different segments are not sorted relative to each other.
Two segments should be merged if they are collinear (lie on the same infinite line) AND their geometric segments intersect (they share at least one point in common, including touching at endpoints).
When merging multiple segments, the result for that merged group should contain all distinct points that appear in any of the original segments in the group, sorted along the line.
Your task is to return a list of merged segments, where each merged segment is represented as a sorted list of its distinct points. The order of merged segments in the output does not matter.
Example:
Input
[
[(1, 1), (2, 2), (4, 4)],
[(2, 1), (4, 2)],
[(3, 3), (6, 6)],
[(7, 7), (8, 8)]
]
Output (one valid ordering)
[
[(1, 1), (2, 2), (3, 3), (4, 4), (6, 6)],
[(7, 7), (8, 8)],
[(2, 1), (4, 2)]
]
Assumptions:
- Coordinates are integers.
- Each input segment contains at least 2 points.
- You should remove duplicate points within a merged segment.
AI interview prep
Core dilemma
Efficiently identifying and grouping collinear and intersecting line segments while managing geometric calculations and point deduplication.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Merge overlapping 2D line segments
You are given a list of 2D line segments. Each segment is represented as a list of 2D points [(x1,y1), (x2,y2), ...] that all lie on the same straight line.
Within a segment, the points are already sorted along the segment. Different segments are not sorted relative to each other.
Two segments should be merged if they are collinear (lie on the same infinite line) AND their geometric segments intersect (they share at least one point in common, including touching at endpoints).
When merging multiple segments, the result for that merged group should contain all distinct points that appear in any of the original segments in the group, sorted along the line.
Your task is to return a list of merged segments, where each merged segment is represented as a sorted list of its distinct points. The order of merged segments in the output does not matter.
Example:
Input
[
[(1, 1), (2, 2), (4, 4)],
[(2, 1), (4, 2)],
[(3, 3), (6, 6)],
[(7, 7), (8, 8)]
]
Output (one valid ordering)
[
[(1, 1), (2, 2), (3, 3), (4, 4), (6, 6)],
[(7, 7), (8, 8)],
[(2, 1), (4, 2)]
]
Assumptions:
- Coordinates are integers.
- Each input segment contains at least 2 points.
- You should remove duplicate points within a merged segment.