Katkat
Back

Merge Overlapping Collinear Segments

Applied IntuitionSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.