Circle-Line Intersection

Circle centre $c$, radius $r$; line through $a$ with direction $d=b-a$.

The method

1. Find the foot of the perpendicular from $c$ to the line.
2. Compare its distance to $r$: greater → no intersection; equal → tangent; less → two points.
3. Step along the line by $h=\sqrt{r^2-d_{\perp }^2}$ in both directions.

vector<PD> circleLine(PD c, double r, PD a, PD b) {
    PD d = b - a;
    double t = dot(c - a, d) / norm2(d);              // parameter of the foot
    PD foot = a + d * t;
    double distSq = norm2(foot - c);
    if (distSq > r * r + EPS) return {};              // no intersection
    double h = sqrt(max(0.0, r * r - distSq)) / abs_(d);
    if (h < EPS) return {foot};                       // tangent
    return {foot - d * h, foot + d * h};
}

For a segment

Compute the line intersections, then keep only those with parameter $t\in [0,1]$. Equivalently, check dot(p-a, p-b) <= 0 for each candidate point.

Exact tests without constructing points

Many questions do not need the intersection points at all:

Question	Exact test
Does the line meet the circle?	$\mathrm{cross}(d,c-a{)}^2\le r^2|d{|}^2$
Is the line tangent?	equality above
Is point $p$ inside the circle?	$|p-c{|}^2<r^2$
Does the segment meet the circle?	distToSegment(c,a,b) <= r and at least one endpoint outside (or both inside)
Is the circle entirely inside a polygon?	centre inside and distance to every edge $\ge r$

With integer input these are all exact — no epsilon required. Prefer them.

Chord length

$\ell =2\sqrt{r^2-d_{\perp }^2},$

where $d_{\perp }$ is the distance from the centre to the line. The circular segment cut off has area

$A=r^2\left(\theta -\sin \theta \right)/2,\theta =2\arccos \left(\frac{d_{\perp }}{r}\right),$

which is what you need for circle-polygon intersection areas.

Circle-polygon intersection area

A standard and genuinely useful routine: the area of the intersection of a circle with a polygon. Decompose the polygon into triangles $(c,p_i,p_{i+1})$ from the circle’s centre, and for each triangle compute the signed circle-triangle intersection area:

• both points inside → the whole triangle;
• both outside and the edge misses the circle → a circular sector;
• otherwise → a mixture of sectors and triangles, split at the chord intersections.

Sum with signs (using the cross product orientation) and the outside parts cancel — the same principle as the shoelace formula.

Numerical care

Tangency is fragile

distSq == r*r almost never holds exactly in floating point. Use max(0.0, r*r - distSq) before the square root to avoid NaN from a tiny negative value, and treat $|h|<\epsilon$ as tangency.

If the input is integral, do the decision in exact integers and only then construct the points in floating point.

Related constructions

Task	Method
Circle through 3 points	intersect two perpendicular bisectors
Circle through 2 points with radius $r$	midpoint $\pm$ perpendicular offset $\sqrt{r^2-(d/2{)}^2}$
Circle-circle intersection	radical line, then circle-line
Tangent lines from a point	see the tangents page
Smallest circle enclosing points	Welzl
Point on the circle nearest to $p$	$c+r\frac{p-c}{|p-c|}$

See also: Circle-Circle Intersection · Tangents · Distances