cswork / libraryOpen practice workspace

Coding questions · Applied Intuition

Find intersection of two line segments

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

Closed Line Segment Intersection

Return whether two closed 2D line segments intersect, including endpoint touches and collinear overlap.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.