Katkat
Back

Find intersection of two line segments

Applied IntuitionSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's skills in computational geometry and numerical robustness, focusing on line-segment intersection reasoning, endpoint touching, collinearity, and precision handling.

Problem

Given two 2D line segments AB and CD, determine whether they intersect.

Each segment is defined by its endpoints:

  • A(x1, y1), B(x2, y2)
  • C(x3, y3), D(x4, y4)

Tasks

  1. Return true/false indicating whether the two closed segments intersect.
  2. (Optional follow-up) If they intersect at a single point, return that intersection point. If they overlap over an interval (collinear overlap), return an appropriate representation (e.g., "overlap" or the overlapping segment).

Requirements / Edge cases to handle

  • Vertical segments (infinite slope) and horizontal segments.
  • Touching at endpoints counts as intersection.
  • Collinear segments that overlap partially or fully.
  • Large coordinates (avoid floating-point precision bugs if possible).

Example

  • A(0,0), B(2,2) and C(0,2), D(2,0) → intersect at (1,1)
  • A(0,0), B(0,2) and C(1,0), D(1,2) → do not intersect (parallel vertical)
  • A(0,0), B(2,0) and C(1,0), D(3,0) → collinear overlap