Merge Overlapping Collinear Segments
Problem Description
You are given a list of 2D geometric segments. Each segment is represented by a list of 2D points, where each point is a pair of (double, double) coordinates.
Segment Properties:
- Each segment contains at least two points.
- All points within the same segment are guaranteed to be collinear.
- Points within a segment may appear in any order.
- A segment may include interior points in addition to its endpoints.
- Segments can be horizontal, vertical, or diagonal.
Merging Criteria:
Two segments should be merged if they satisfy both of the following conditions:
- They lie on the same infinite line.
- Their 1D projections on that line overlap or touch.
If multiple segments can be merged transitively (e.g., segment A merges with B, and B merges with C, then A, B, and C all merge), they should all be combined into a single result segment.
Segments that merely intersect at a single point but do not lie on the same infinite line should not be merged.
Output Requirements:
For each resulting merged segment, return all unique points that appeared in any of the original segments that were part of the merge. These points must be ordered along the line from one end of the merged segment to the other.
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)] ]
Assumption:
Assume exact geometric comparisons are acceptable for this problem, meaning floating-point precision issues do not need to be explicitly handled.
AI interview prep
Core dilemma
Balancing robust geometric predicate evaluation (collinearity, line identity, 1D overlap) with efficient graph-based merging and precise ordering of unique points.
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 Collinear Segments
Problem Description
You are given a list of 2D geometric segments. Each segment is represented by a list of 2D points, where each point is a pair of (double, double) coordinates.
Segment Properties:
- Each segment contains at least two points.
- All points within the same segment are guaranteed to be collinear.
- Points within a segment may appear in any order.
- A segment may include interior points in addition to its endpoints.
- Segments can be horizontal, vertical, or diagonal.
Merging Criteria:
Two segments should be merged if they satisfy both of the following conditions:
- They lie on the same infinite line.
- Their 1D projections on that line overlap or touch.
If multiple segments can be merged transitively (e.g., segment A merges with B, and B merges with C, then A, B, and C all merge), they should all be combined into a single result segment.
Segments that merely intersect at a single point but do not lie on the same infinite line should not be merged.
Output Requirements:
For each resulting merged segment, return all unique points that appeared in any of the original segments that were part of the merge. These points must be ordered along the line from one end of the merged segment to the other.
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)] ]
Assumption:
Assume exact geometric comparisons are acceptable for this problem, meaning floating-point precision issues do not need to be explicitly handled.