Find intersection of two line segments

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Return true/false indicating whether the two closed segments intersect.
(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

Find intersection of two line segments

Quick Overview

Problem

Tasks

Requirements / Edge cases to handle

Example

Comments (0)