Circle–Line Intersection — Interview Preparation¶

Coverage: the geometric (foot + half-chord) and algebraic (quadratic-substitution) methods, the 0/1/2-point classification, circle-segment / circle-ray clamping, the tangent case, numerical robustness, and the ray-tracing / collision applications. Questions are tiered junior → professional, followed by a 3-language coding challenge.

How to Use This File¶

Each question lists the expected answer focus — the points an interviewer wants to hear. Practice saying the answer out loud, then check yourself against the focus column. The coding challenge at the end should be solved cleanly in all three languages.

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Rapid-Fire Conceptual Checks¶

Extended Junior Questions¶

Extended Middle Questions¶

Extended Senior Questions¶

Cross-Topic Connection Questions¶

These probe whether you see circle–line intersection as part of a bigger geometry toolkit, not an isolated trick.

Whiteboard Complexity Table to Recite¶

Reciting this fluidly signals you have internalised both the per-test and the system-level complexity.

Worked Long-Form Answers¶

Interviewers often pick one question and ask you to "go deep." Here are model answers for the four most common deep-dives — spoken at length, the way you would at a whiteboard.

Deep-dive A: "Walk me through finding the two intersection points from scratch."¶

"I'll use the geometric method because it needs no equation solving. I have a circle with centre C and radius r, and a line through A and B.

First I form the direction vector dir = B - A. The key trick is projection: I want the point on the line nearest to C, called the foot of perpendicular F. I compute the parameter t = ((C - A) · dir) / (dir · dir) — that's the dot product of C - A onto dir, normalised by dir's squared length — and then F = A + t·dir.

Now d = |C - F| is the shortest distance from the centre to the line. I compare d with r. If d > r the line misses, zero points. If d equals r within an epsilon, it's tangent, one point, and that point is F. If d < r, it's a secant with two points.

For the two points I use Pythagoras: the radius r is the hypotenuse of a right triangle with one leg d (centre to foot) and the other leg h (foot to crossing point along the line). So h = sqrt(r² - d²). I take the unit direction û = dir / |dir| and step h in both directions: P1 = F + h·û, P2 = F - h·û. Done — no slopes, no vertical-line special case, one square root.

The only guard I add is sqrt(max(0, r² - d²)) so floating-point noise on a near-tangent doesn't hand me a negative radicand."

Deep-dive B: "Derive the quadratic and explain the discriminant."¶

"I parametrise the line as P(t) = O + t·D, with O a point on the line and D its direction. The circle is |P - C|² = r². Substituting and letting f = O - C, I expand |t·D + f|² = r² into (D·D)t² + 2(f·D)t + (f·f - r²) = 0. That's a quadratic a·t² + b·t + c = 0 with a = D·D, b = 2(f·D), c = f·f - r².

The discriminant Δ = b² - 4ac decides everything by its sign: negative means no real roots, so zero points; zero means a double root, the tangent; positive means two roots, a secant. And there's a beautiful identity — Δ = 4a²(r² - d²) — so the discriminant test and the distance test are literally the same fact scaled by a positive constant.

The reason graphics code prefers this form is that solving for t gives me the parameter directly, which I need for clamping to a ray (t >= 0) or a segment (t ∈ [0,1]), and it generalises to 3-D spheres with zero changes to the algebra."

Deep-dive C: "Your ray-tracer flickers on the edges of spheres. Diagnose it."¶

"Flicker on silhouettes is the classic near-tangent symptom. On the outline of a sphere, the ray grazes it, so d ≈ r and the discriminant is near zero. From frame to frame, tiny floating-point differences flip the count between one and two — or between hit and miss — and the pixel toggles.

Three fixes. First, I work in a local frame: translate so the sphere centre is at the origin before the math, and normalise the ray direction so a = 1. That minimises the magnitudes I subtract in r² - d², shrinking the cancellation error. Second, I use a relative tolerance tied to r, not an absolute epsilon, when deciding the tangent boundary. Third, if it still shimmers, I add a small temporal hysteresis band so the count doesn't oscillate on the knife-edge. The root cause is that the count is a sign test on a near-zero quantity, which is intrinsically ill-conditioned — I can't make it exact in floating point, only stable."

Deep-dive D: "A fast ball tunnels through a thin wall. Fix it."¶

"Static tests sample only the ball's position each frame. If the ball moves more than its diameter between frames, it can be on one side at frame N and the far side at frame N+1, never overlapping the wall in any sampled frame — that's tunnelling.

The fix is continuous collision. Instead of testing a point against the wall, I treat the ball's centre as moving along a segment from its old position C0 to its new position C1. I inflate the wall by the ball's radius r — that's a Minkowski sum of the wall with a disc — and intersect the centre's swept segment against the inflated wall. The earliest parameter t ∈ [0,1] where they meet is the time of impact; I advance the ball only to that point and resolve the collision there. For the rounded ends of the inflated wall I fall back to a circle–segment test against the wall's endpoints. This reduces directly to the circle–line machinery — the difference is only that the centre is a moving segment instead of a static point."

Scenario / Whiteboard Prompts¶

Mock Interview Dialogue¶

A realistic back-and-forth, so you can rehearse the flow, not just isolated facts.

Interviewer: Given a circle and a line, how many ways can they intersect?

You: Zero, one, or two points. Two when the line cuts through, one when it's tangent — just grazing — and zero when it passes outside.

Interviewer: How would you decide which case without computing the points?

You: Compute the perpendicular distance d from the centre to the line and compare it with the radius r. If d > r it misses, d == r is tangent, d < r is two points. I'd actually compare d² with r² to skip a square root.

Interviewer: Good. Now find the actual points.

You: I project the centre onto the line to get the foot of perpendicular F — that's the closest point on the line to the centre, and also the midpoint of the chord. Then the half-chord length is h = sqrt(r² - d²) by Pythagoras, and the two points are F ± h·û where û is the line's unit direction.

Interviewer: What if it's a segment, not an infinite line?

You: Each point corresponds to a parameter t along the line. For a segment I keep only points with t ∈ [0,1]; for a ray, t >= 0. So a line crossing twice might give zero, one, or two points once clamped.

Interviewer: Your ray-tracer renders fine but flickers on sphere edges. Why?

You: Those are grazing rays — near tangent, so the discriminant is near zero and the count flips frame to frame from floating-point noise. I'd work in the sphere's local frame, normalise the direction, use a relative epsilon tied to r, and add a small hysteresis band so the count doesn't oscillate. The count is a sign test on a near-zero number, which is intrinsically ill-conditioned.

Interviewer: Can you make the count exact?

You: Yes, for integer inputs. a = D·D, b' = f·D, c = f·f - r², and Δ' = b'² - a·c are all exact integers, so sign(Δ') gives the count with no rounding. I'd use a wide integer type to avoid overflow. The point coordinates are irrational, but the count — the hard part — is exact.

Interviewer: Last one: a fast ball passes through a thin wall. Fix it.

You: Tunnelling. Static tests sample positions; a fast ball jumps the wall between frames. I'd do continuous collision: treat the ball's centre as a moving segment, inflate the wall by the radius, and find the earliest time of impact t ∈ [0,1]. That reduces right back to the circle–line machinery.

Rehearsing this dialogue trains you to lead — volunteering the d² optimisation, the clamp, the robustness story, and the exact-count option before being asked.

Common Pitfalls Interviewers Watch For¶

1. Dividing by the slope (y = mx + b) and forgetting vertical lines exist.
2. sqrt without a sign check — crashes or NaN on a miss.
3. == for tangency on floats — the case is then never detected.
4. Returning infinite-line points for a segment query — forgetting to clamp t.
5. Two coincident points at tangency instead of collapsing to one.
6. Negative entry root on a ray — mishandling the origin-inside case.
7. O(n) over all circles with no broad-phase when n is large.
8. Absolute magic epsilons that silently break under a unit change.

Say these before the interviewer points them out — it signals production experience.

Coding Challenge (3 Languages)¶

Challenge: Circle–Segment Intersection¶

Problem. Given a circle (centre (cx, cy), radius r) and a line segment from A = (ax, ay) to B = (bx, by), return the intersection points that lie on the segment (parameter t ∈ [0, 1]), sorted by t. Return 0, 1, or 2 points. Use the quadratic method, clamp to the segment, collapse the tangent case to a single point, and guard all sqrt/division.

Examples. - Circle (0,0), r=5, segment (-6,3)→(6,3) → two points (-4,3) and (4,3). - Circle (0,0), r=5, segment (0,0)→(3,0) → zero points (segment ends inside the circle). - Circle (0,0), r=5, segment (0,0)→(10,0) → one point (5,0). - Circle (0,0), r=5, segment (-6,5)→(6,5) → one point (0,5) (tangent).

Go¶

package main

import (
    "fmt"
    "math"
    "sort"
)

const EPS = 1e-9

type Pt struct{ X, Y float64 }

// circleSegment returns the intersection points of segment A-B with circle (C,r)
// that lie on the segment, sorted by parameter t along A→B.
func circleSegment(cx, cy, r float64, A, B Pt) []Pt {
    dx, dy := B.X-A.X, B.Y-A.Y
    fx, fy := A.X-cx, A.Y-cy
    a := dx*dx + dy*dy
    if a < EPS { // A == B: degenerate "segment"
        // it's a point; intersects iff that point is on the circle
        if math.Abs(fx*fx+fy*fy-r*r) < EPS {
            return []Pt{A}
        }
        return nil
    }
    bHalf := fx*dx + fy*dy
    c := fx*fx + fy*fy - r*r
    disc := bHalf*bHalf - a*c
    if disc < -EPS {
        return nil // miss
    }
    if disc < 0 {
        disc = 0 // round-off → tangent
    }
    sq := math.Sqrt(disc)

    var ts []float64
    if sq < EPS {
        ts = []float64{-bHalf / a} // tangent: single root
    } else {
        ts = []float64{(-bHalf - sq) / a, (-bHalf + sq) / a}
    }

    var out []Pt
    for _, t := range ts {
        if t >= -EPS && t <= 1+EPS {
            out = append(out, Pt{A.X + t*dx, A.Y + t*dy})
        }
    }
    // already in t-order for the two-root case; sort defensively
    sort.Slice(out, func(i, j int) bool {
        ti := (out[i].X-A.X)*dx + (out[i].Y-A.Y)*dy
        tj := (out[j].X-A.X)*dx + (out[j].Y-A.Y)*dy
        return ti < tj
    })
    return out
}

func main() {
    fmt.Println(circleSegment(0, 0, 5, Pt{-6, 3}, Pt{6, 3}))   // 2 points
    fmt.Println(circleSegment(0, 0, 5, Pt{0, 0}, Pt{3, 0}))    // 0 points
    fmt.Println(circleSegment(0, 0, 5, Pt{0, 0}, Pt{10, 0}))   // 1 point (5,0)
    fmt.Println(circleSegment(0, 0, 5, Pt{-6, 5}, Pt{6, 5}))   // tangent (0,5)
}

Java¶

import java.util.*;

public class CircleSegment {
    static final double EPS = 1e-9;
    record Pt(double x, double y) {}

    static List<Pt> circleSegment(double cx, double cy, double r, Pt A, Pt B) {
        double dx = B.x() - A.x(), dy = B.y() - A.y();
        double fx = A.x() - cx, fy = A.y() - cy;
        double a = dx * dx + dy * dy;
        List<Pt> out = new ArrayList<>();
        if (a < EPS) { // degenerate segment = point
            if (Math.abs(fx * fx + fy * fy - r * r) < EPS) out.add(A);
            return out;
        }
        double bHalf = fx * dx + fy * dy;
        double c = fx * fx + fy * fy - r * r;
        double disc = bHalf * bHalf - a * c;
        if (disc < -EPS) return out;     // miss
        if (disc < 0) disc = 0;          // round-off → tangent
        double sq = Math.sqrt(disc);

        double[] ts = (sq < EPS)
            ? new double[]{-bHalf / a}
            : new double[]{(-bHalf - sq) / a, (-bHalf + sq) / a};

        for (double t : ts)
            if (t >= -EPS && t <= 1 + EPS)
                out.add(new Pt(A.x() + t * dx, A.y() + t * dy));

        out.sort(Comparator.comparingDouble(
            p -> (p.x() - A.x()) * dx + (p.y() - A.y()) * dy));
        return out;
    }

    public static void main(String[] args) {
        System.out.println(circleSegment(0, 0, 5, new Pt(-6, 3), new Pt(6, 3)));
        System.out.println(circleSegment(0, 0, 5, new Pt(0, 0), new Pt(3, 0)));
        System.out.println(circleSegment(0, 0, 5, new Pt(0, 0), new Pt(10, 0)));
        System.out.println(circleSegment(0, 0, 5, new Pt(-6, 5), new Pt(6, 5)));
    }
}

Python¶

import math

EPS = 1e-9


def circle_segment(cx, cy, r, A, B):
    """Intersection points of segment A-B with circle (cx,cy,r), on the
    segment (t in [0,1]), sorted by t."""
    ax, ay = A
    bx, by = B
    dx, dy = bx - ax, by - ay
    fx, fy = ax - cx, ay - cy
    a = dx * dx + dy * dy
    if a < EPS:                          # degenerate segment = point
        if abs(fx * fx + fy * fy - r * r) < EPS:
            return [A]
        return []
    b_half = fx * dx + fy * dy
    c = fx * fx + fy * fy - r * r
    disc = b_half * b_half - a * c
    if disc < -EPS:
        return []                        # miss
    if disc < 0:
        disc = 0.0                       # round-off → tangent
    sq = math.sqrt(disc)

    ts = [-b_half / a] if sq < EPS else [(-b_half - sq) / a, (-b_half + sq) / a]

    out = []
    for t in ts:
        if -EPS <= t <= 1 + EPS:
            out.append((ax + t * dx, ay + t * dy))

    out.sort(key=lambda p: (p[0] - ax) * dx + (p[1] - ay) * dy)
    return out


if __name__ == "__main__":
    print(circle_segment(0, 0, 5, (-6, 3), (6, 3)))  # 2 points
    print(circle_segment(0, 0, 5, (0, 0), (3, 0)))   # 0 points
    print(circle_segment(0, 0, 5, (0, 0), (10, 0)))  # 1 point (5,0)
    print(circle_segment(0, 0, 5, (-6, 5), (6, 5)))  # tangent (0,5)

Evaluation criteria:

• Correct count for secant / tangent / miss, and correct clamping to [0,1].
• Tangent collapses to a single point (not two coincident ones).
• All sqrt radicands and divisions are guarded (no NaN, no divide-by-zero).
• Degenerate segment (A == B) handled.
• Points returned sorted by t for determinism.

Follow-up questions an interviewer may ask:

1. Change it to a ray (t >= 0) and return only the nearest hit. (Handle the origin-inside case → exit root.)
2. Make the count exact for integer inputs. (Integer Δ' = b'² - a·c; sign test; wide integer type.)
3. Replace the naive roots with the cancellation-free form (q = -(b' + sign(b')√Δ'); t1 = q/a; t2 = c/q) and explain why.
4. Extend to a 3-D sphere — what changes? (Nothing in the algebra; Pt gains a z and dot sums three terms.)

Self-Assessment Checklist¶

Before you walk into an interview on this topic, confirm you can do each of these without notes:

If any box is unchecked, re-read the corresponding level file (junior → professional) before the interview. The single most common failure is fumbling the clamp (segment/ray) and the near-tangent robustness story — drill those two hardest.

One-Page Summary to Memorise¶

COUNT:   sign of (r² − d²)   ≡   sign of discriminant Δ
         d>r → 0,  d=r → 1,  d<r → 2

GEOMETRIC (points):
  dir = B − A
  t   = (C−A)·dir / dir·dir
  F   = A + t·dir            # foot = chord midpoint
  d   = |C − F|
  h   = sqrt(max(0, r² − d²))
  P   = F ± h·(dir/|dir|)

ALGEBRAIC (quadratic, gives t):
  f = O − C
  a = D·D,  b = 2(f·D),  c = f·f − r²
  Δ = b² − 4ac
  t = (−b ± sqrt(Δ)) / (2a)
  STABLE: q = −(b + sign(b)√Δ)/2;  t1 = q/a;  t2 = c/q

CLAMP:   line: any t;  ray: t≥0;  segment: 0≤t≤1
NORMAL:  (P − C)/r
ROBUST:  local frame, normalise D, relative eps, integer count for exactness

Carry this in your head; everything else is derivable from it.

Next step: tasks.md — graded practice tasks (beginner / intermediate / advanced) plus a cross-language benchmark.