xii. Circles and Inversion

Circle-Line

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 $\to$ no intersection; equal $\to$ tangent; less $\to$ 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 `onSegment`-style 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?	[[19-geometry/01-primitives
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.

Proof: the squared line-distance test

$\mathrm{cross}(d,c-a)=|d|d_{\perp }$ up to sign, where $d_{\perp }$ is the perpendicular distance from $c$ to the line (the cross product is base $\times$ height of the parallelogram spanned by $d$ and $c-a$, proved in Primitives). So $\mathrm{cross}(d,c-a{)}^2=|d{|}^2{d}_{\perp }^2$, and “the line meets the circle” is $d_{\perp }\le r$, i.e. $d_{\perp }^2\le r^2$, i.e. $|d{|}^2{d}_{\perp }^2\le r^2|d{|}^2$ — the stated test, with every quantity a sum of integer products when the input is integral. $■$

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(\theta -\sin \theta )/2,\theta =2\arccos \left(\frac{d_{\perp }}{r}\right),$

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

Proof: chord length and segment area

The half-chord has length $\sqrt{r^2-d_{\perp }^2}$ by Pythagoras in the right triangle formed by the centre, the foot of the perpendicular, and one chord endpoint (hypotenuse $r$, one leg $d_{\perp }$) — doubling gives $\ell$. The half-angle subtended at the centre by the half-chord satisfies $\cos (\theta /2)=d_{\perp }/r$ (adjacent over hypotenuse in the same right triangle), giving $\theta =2\arccos (d_{\perp }/r)$. The segment’s area is the circular sector’s area ($\frac{1}{2}{r}^2\theta$) minus the triangle formed by the centre and the two chord endpoints ($\frac{1}{2}{r}^2\sin \theta$, since that triangle is isosceles with the two radius sides and included angle $\theta$) — giving $A=\frac{1}{2}{r}^2(\theta -\sin \theta )$. $■$

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 $\to$ the whole triangle;
• both outside and the edge misses the circle $\to$ a circular sector;
• otherwise $\to$ a mixture of sectors and triangles, split at the chord intersections (found by circleLine above).

Sum with signs (using the cross product orientation) and the outside parts cancel — the same principle as the shoelace formula. The full case analysis, generalised to a union of circles, is its own note.

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 — circumcenter
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	Tangents
Smallest circle enclosing points	Welzl
Point on the circle nearest to $p$	$c+r\frac{p-c}{|p-c|}$

Circle-Circle

Circles $(c_1,r_1)$ and $(c_2,r_2)$ with $d=|c_1-c_2|$.

The cases

Condition	Result
$d>r_1+r_2$	separate — 0 points
$d=r_1+r_2$	externally tangent — 1 point
$|r_1-r_2|<d<r_1+r_2$	2 points
$d=|r_1-r_2|$, $d>0$	internally tangent — 1 point
$d<|r_1-r_2|$	one inside the other — 0 points
$d=0$, $r_1=r_2$	identical — infinitely many

Test with squared distances to stay exact: compare $d^2$ against $(r_1+r_2{)}^2$ and $(r_1-r_2{)}^2$.

The construction

Both intersection points lie on the radical line, perpendicular to $c_1{c}_2$. Let
$a=\frac{d^2+r_1^2-r_2^2}{2d},h=\sqrt{r_1^2-a^2}.$
Then the base point is $p=c_1+a\hat{u}$ with $\hat{u}=(c_2-c_1)/d$, and the intersections are $p\pm h{\hat{u}}^{\perp }$.

vector<PD> circleCircle(PD c1, double r1, PD c2, double r2) {
    PD u = c2 - c1;
    double d2 = norm2(u), d = sqrt(d2);
    if (d < EPS) return {};                                  // concentric
    if (d > r1 + r2 + EPS) return {};
    if (d < fabs(r1 - r2) - EPS) return {};
 
    double a = (d2 + r1 * r1 - r2 * r2) / (2 * d);
    double h2 = r1 * r1 - a * a;
    PD base = c1 + u * (a / d);
    if (h2 < EPS) return {base};                             // tangent
    double h = sqrt(h2);
    PD perpU = perp(u) * (h / d);
    return {base - perpU, base + perpU};
}

Proof: the circle-circle construction

Place the intersection point $x$ so $|x-c_1|=r_1$, $|x-c_2|=r_2$. Writing $x=c_1+a\hat{u}+h{\hat{u}}^{\perp }$ for the unit vector $\hat{u}$ along $c_1{c}_2$ (so $a$ is the component along the centre line and $h$ perpendicular to it): $|x-c_1{|}^2=a^2+h^2=r_1^2$ and $|x-c_2{|}^2=(a-d{)}^2+h^2=r_2^2$. Subtracting: $a^2-(a-d{)}^2=r_1^2-r_2^2\Rightarrow 2ad-d^2=r_1^2-r_2^2\Rightarrow a=\frac{d^2+r_1^2-r_2^2}{2d}$, matching the formula; then $h=\sqrt{r_1^2-a^2}$ from the first equation. Both signs of $h$ give the two intersection points (or the one tangent point when $h=0$), and the three early-return cases are exactly the case table’s non-2-point conditions (concentric, separate too far, or one strictly inside the other), each checked with the equivalent squared-distance comparison. $■$

Tested: circleLine and circleCircle’s returned points checked to lie on both input curves (distance to each centre matches its radius within $\epsilon$) and matched against a fine brute-force sweep along the line / around one circle for the number and approximate location of intersections, across all cases in both tables (0, 1, 2 intersections, tangent, concentric, nested).

The radical line and radical centre

The radical axis of two circles is the locus of points with equal power to both:
$\mathrm{pow}(p,C)=|p-c{|}^2-r^2.$
Setting the two powers equal gives a line (the $x^2+y^2$ terms cancel):
$2(c_2-c_1)\cdot p=|c_2{|}^2-|c_1{|}^2-r_2^2+r_1^2.$
For three circles the three radical axes meet at the radical centre — the point from which tangent lengths to all three are equal. This is the clean way to solve “find the point equidistant in tangent length” problems, and it reduces circle problems to line intersections.

Proof: the radical axis is a line, and the radical centre exists

$\mathrm{pow}(p,C_1)=\mathrm{pow}(p,C_2)⟺|p-c_1{|}^2-r_1^2=|p-c_2{|}^2-r_2^2$. Expanding $|p-c_i{|}^2=|p{|}^2-2p\cdot c_i+|c_i{|}^2$, the $|p{|}^2$ terms on both sides cancel, leaving $-2p\cdot c_1+|c_1{|}^2-r_1^2=-2p\cdot c_2+|c_2{|}^2-r_2^2$, i.e. $2(c_2-c_1)\cdot p=|c_2{|}^2-|c_1{|}^2-r_2^2+r_1^2$ — linear in $p$, hence a line (or empty/everything only in the degenerate case $c_1=c_2$). For three circles, the three pairwise radical axes (of $(1,2)$, $(2,3)$, $(1,3)$) satisfy: a point on both the $(1,2)$ and $(2,3)$ axes has $\mathrm{pow}(\cdot ,C_1)=\mathrm{pow}(\cdot ,C_2)$ and $\mathrm{pow}(\cdot ,C_2)=\mathrm{pow}(\cdot ,C_3)$, hence also $\mathrm{pow}(\cdot ,C_1)=\mathrm{pow}(\cdot ,C_3)$ — automatically on the $(1,3)$ axis too. So the three lines are concurrent (or all parallel, in the degenerate case of collinear centres) at a single radical centre, where the tangent length $\sqrt{\mathrm{pow}}$ to all three circles is equal. $■$

Areas

Lens (intersection) area of two overlapping circles:
$A=r_1^2({\theta }_1-\sin {\theta }_1)/2+r_2^2({\theta }_2-\sin {\theta }_2)/2,$
with ${\theta }_1=2\arccos \frac{d^2+r_1^2-r_2^2}{2d{r}_1}$ and symmetrically for ${\theta }_2$ (swap the roles of $r_1,r_2$).

Proof: the lens area

The lens is the union of two circular segments, one cut from each circle by the radical line (the common chord). The segment from circle 1 has half-angle given by $\cos ({\theta }_1/2)=a/r_1$ where $a$ is the same quantity from the circle-circle construction above (the signed distance along $c_1{c}_2$ to the chord’s foot) — substituting $a=\frac{d^2+r_1^2-r_2^2}{2d}$ gives $\cos ({\theta }_1/2)=\frac{d^2+r_1^2-r_2^2}{2d{r}_1}$, and doubling the half-angle formula (the standard identity $\cos \theta =2{\cos }^2(\theta /2)-1$ relates this to the $\arccos$ form stated) gives ${\theta }_1$ as written. The segment area formula from above applies to each side, and the two segments together exactly tile the lens (they meet precisely at the common chord, with no gap or overlap, since both circles’ boundaries bound the lens on their respective sides of the chord). $■$

Union of $n$ circles: for each circle, walk its boundary and determine which arcs are not covered by any other circle; then apply a Green’s-theorem-style sum over arcs and chords. $O(n^2\log n)$ — see 13-circle-union-and-angular-sweep.

Related constructions

Task	Method
Circle through 3 points	perpendicular bisectors, or the determinant formula
Circle tangent to 2 circles with radius $r$	intersect circles of radii $r_1\pm r$ and $r_2\pm r$
Apollonius circle	the locus with $|PA|/|PB|=k$
Common tangent lines	Tangents
Circle inversion	maps circles and lines to circles and lines
Smallest enclosing circle	Welzl

Precision

Near-tangency

When $d$ is close to $r_1+r_2$, $h^2$ is a tiny difference of large numbers and loses most of its significant digits. Always clamp with max(0.0, h2) before the square root, and decide the case using exact integer comparisons on squared quantities when the input is integral.

Circle Inversion

Inversion in a circle $(o,r)$: maps points, and circles / lines to circles / lines, turning tangency problems into line problems.

PD invertPoint(PD p, PD o, double r) { PD d = p - o; return o + d * (r * r / norm2(d)); }    // |oq| * |op| = r^2, p != o
 
// image of a circle (center c, radius rc): {isLine, c2, r2, a, b}
// isLine: the circle passed through o and the image is the line through a, b; else the image is circle (c2, r2)
tuple<bool, PD, double, PD, PD> invertCircle(PD c, double rc, PD o, double r) {
    PD d = c - o;
    double dist = abs_(d);
    if (fabs(dist - rc) < 1e-9) {                      // circle through o -> line
        PD u = d * (1.0 / dist);
        PD far = invertPoint(o + u * (2 * rc), o, r);  // the antipode of o maps to the closest point of the image line
        PD pr = perp(u);
        return {true, PD{}, 0, far, far + pr};
    }
    PD u = d * (1.0 / dist);
    PD p1 = invertPoint(o + u * (dist - rc), o, r), p2 = invertPoint(o + u * (dist + rc), o, r);
    return {false, (p1 + p2) * 0.5, abs_(p1 - p2) * 0.5, PD{}, PD{}};
}
 
pair<PD, double> invertLine(PD a, PD b, PD o, double r) {        // image of a line not through o: a circle through o
    PD ab = b - a;
    PD foot = a + ab * (dot(o - a, ab) / norm2(ab));              // closest point of the line to o
    PD img = invertPoint(foot, o, r);                             // farthest point of the image circle from o
    return {(o + img) * 0.5, abs_(img - o) * 0.5};
}

Complexity: $O(1)$. Circles through the centre $o$ become lines and vice versa; tangency and angles are preserved. Typical use: circles tangent to two circles through a common point (Apollonius-like problems) become lines tangent to two circles (common tangents), then invert back.

Proof: invertPoint, invertCircle, invertLine

invertPoint. By definition, inversion sends $p$ to the point $q$ on ray $op$ with $|oq|\cdot |op|=r^2$: $q=o+\hat{d}\cdot \frac{r^2}{|d|}$ where $d=p-o$, $\hat{d}=d/|d|$ — simplifying $\hat{d}\cdot \frac{r^2}{|d|}=d\cdot \frac{r^2}{|d{|}^2}$, exactly the code.

invertCircle — the line case. A circle through $o$ has $o$ as one of its own points; every other point $c+rc\cdot \hat{\theta }$ on it inverts to some image point, and since inversion maps circles-and-lines to circles-and-lines, and a “circle through $o$” has no well-defined inverse image AT $o$ (inversion isn’t defined at the center), the image must be the degenerate case: a line. That line is perpendicular to $oc$ (by the general conformal/symmetry property of inversion: the image of a curve symmetric about line $oc$ is itself symmetric about the same line, and a circle through $o$ is symmetric about $oc$; a line symmetric about $oc$ that doesn’t pass through $o$ must be perpendicular to it) and passes through the inverted image of the circle’s farthest point from $o$ (the antipode $o+u\cdot 2rc$, at distance $2rc$ from $o$ along the circle’s diameter through $o$) — this farthest point maps, under inversion, to the closest point of the image line to $o$ (inversion reverses near/far along each ray), which is exactly the foot of the perpendicular from $o$ to the image line — so that single inverted point plus the perpendicular direction perp(u) fully determines the image line, matching the code’s far and far + pr.

invertCircle — the circle case. A circle not through $o$ is still symmetric about line $oc$, so its image (itself a circle, by inversion’s general circle/line-preservation property) is also symmetric about $oc$, hence centred on it. The two points of the original circle that lie exactly on line $oc$ — at distances $dist-rc$ and $dist+rc$ from $o$ — invert to the two points of the image circle that also lie on $oc$, which (being symmetric about the image’s own centre) are exactly the image circle’s own diameter endpoints on that line. So the image centre is their midpoint and the image radius is half their distance, exactly the code’s final return.

invertLine. A line not through $o$ inverts to a circle through $o$ (the reverse of the first case, by the involutive symmetry of inversion — applying it twice returns the original). The point of the line closest to $o$ (the foot of the perpendicular) is on the line of symmetry through $o$ perpendicular to the original line, and inverts to the point of the image circle farthest from $o$ along that same line — i.e. the diametrically opposite point from $o$ on the image circle. So $o$ and that inverted point are the two endpoints of a diameter, giving the image centre as their midpoint and radius as half their distance — exactly the code. $■$

Tested: invertPoint is self-inverse (invertPoint(invertPoint(p,o,r),o,r) == p) and preserves $|op|\cdot |oq|=r^2$; invertCircle and invertLine checked by sampling many points on the original circle/line, inverting each individually with invertPoint, and confirming they all lie on the claimed image circle or line (and that the two routines are mutual inverses: inverting the image of a circle-through-$o$ as a line, then inverting that line back, recovers the original circle).