Katkat
Back

Merge collinear overlapping 2D segments

Applied IntuitionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle geometric data by identifying and merging overlapping segments that lie on the same infinite line.

Problem Statement

You are given a list of 2D line segments, where each segment is defined by its endpoints ((x1, y1), (x2, y2)). Two segments are considered 'mergeable' if they are collinear (lie on the same infinite line) and they overlap or touch. Your task is to merge all such segments into a minimal set of non-overlapping segments.

Function Signature

def merge_collinear_segments(segments):
    # segments is a list of tuples: [((x1, y1), (x2, y2)), ...]
    pass

Input Constraints

  • Number of segments: up to 10,000.
  • Coordinates: integers in the range [-10^6, 10^6].
  • A segment always has distinct endpoints.

Examples

Example 1: Input: [((0, 0), (2, 2)), ((1, 1), (3, 3)), ((5, 5), (6, 6))] Output: [((0, 0), (3, 3)), ((5, 5), (6, 6))] Explanation: The first two segments share the same slope and lie on the same line, so they are merged. The third is separate.

Example 2: Input: [((0, 0), (0, 5)), ((0, 2), (0, 7)), ((1, 1), (1, 4))] Output: [((0, 0), (0, 7)), ((1, 1), (1, 4))]

Edge Cases

  • Vertical lines (slope is undefined).
  • Segments that touch at a single point.
  • Segments that are identical.

Hints

Hint 1

Represent each line in its canonical form, such as ax + by + c = 0, to easily group collinear segments.

Hint 2

For segments on the same line, project them onto a 1D coordinate system based on the line's orientation (e.g., use x if the line is not vertical, otherwise use y).

Hint 3

Once projected to 1D, the problem reduces to the classic 'merge intervals' algorithm.

Follow-up questions

  • How would you handle floating-point precision issues if the input coordinates were floats?
  • What is the time complexity of your solution, and can you optimize the grouping process?
  • If the segments were allowed to have a small 'gap' tolerance (e.g., they should be merged if within 0.1 units of each other), how would you modify the approach?