Merge Overlapping Collinear Segments
Company: Applied Intuition
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a list of 2D geometric segments:
`vector<vector<pair<double, double>>> segments`
Each inner list represents one segment and contains at least two points. All points within the same segment are collinear, but:
- the points may appear in any order,
- a segment may include interior points in addition to its endpoints,
- the segment may be horizontal, vertical, or diagonal.
Two segments should be merged if they lie on the same infinite line and their 1D projections on that line overlap or touch. If multiple segments can be merged transitively, merge them into one result.
For each merged segment, return all unique points that appeared in any of the original segments that were merged, ordered along the line from one end of the merged segment to the other.
Do not merge segments that merely intersect at a point but are not on the same line.
Example:
Input:
`[
[(1,1), (2,2), (4,4)],
[(4,2), (2,1)],
[(7,7), (8,8)],
[(3,3), (5,5)]
]`
Output:
`[
[(1,1), (2,2), (3,3), (4,4), (5,5)],
[(2,1), (4,2)],
[(7,7), (8,8)]
]`
Assume exact geometric comparisons are acceptable for this problem.
Overview: This question evaluates computational geometry and algorithm design skills, focusing on collinearity testing, projecting points onto a line, merging overlapping 1D intervals generalized to arbitrary lines, ordering points along a line, and handling duplicates and edge cases.