Two circles

circles.md

If the circles have the same center, they intersect at no point if they have different radius, or at all points if they have the same radius.

Leaving that case aside, we can assume without loss of generality that one circle is centered at (0, 0) and has radius 1, while the other one is centered at (x, 0) with x > 0 and has radius R with R ≥ 1. We're left with three cases.

• If R is outside the closed interval x-1..x+1, the circles don't intersect.

• If R is on either endpoint of that interval, x-1 | x+1, the circles intersect at exactly one point, either (+1, 0) or (-1, 0), respectively.

• Finally, if R is strictly inside the interval x-1..x+1, the two intersection points are of the form (cos ±α, sin ±α), where α satisfies (Pythagoras) R² == (x - cos α)² + sin²α == x² - 2 x cos α + cos²α + sin²α == x² - 2 x cos α + 1. Thus α = acos (x² - R² + 1)/(2 x).

---

Of course, the phrase "without loss of generality" hides a lot of generality. ☺ Assume the two circles are actually of sizes R₁ and R₂, and centered at (x₁, y₁) and (x₂, y₂), respectively. We'll still assume that R₁ ≤ R₂; if not, then they'd best swap roles.

We want the first circle to be at (0, 0), so we'll translate everything so that it is. The second circle then ends up at (x₂ - x₁, y₂ - y₁).

Rotating around the origin by an angle -β = atan2 y₂ - y₁, x₂ - x₁ puts the second circle at (√((x₂ - x₁)² + (y₂ - y₁)²), 0), giving it the y coordinate we want.

Finally, we want to scale everything by 1/R₁ so that the first circle gets a normalized radius. The second circle then ends up at (√((x₂ - x₁)² + (y₂ - y₁)²)/R₁, 0) with a radius of R₂/R₁.

In other words:

d = √((x₂ - x₁)² + (y₂ - y₁)²)
x = d/R₁
R = R₂/R₁

Thus, the actual intersection points result from taking (cos ±α, sin ±α) through the reverse transformations:

                (cos ±α, sin ±α)
scale by R₁:    (R₁ cos ±α, R₁ sin ±α)
rotate by β:    (R₁ cos(β ± α), R₁ sin(β ± α))
translate back: (x₁ + R₁ cos(β ± α), y₁ + R₁ sin(β ± α))

Looking at the form of this last coordinate pair, we see that we are describing points on the first circle, oriented roughly in the angle β (towards the second circle), but spread apart by the angle α (which depends on the sizes of and distances between the two circles). We have recovered full generality.

---

This Perl 6 program implements the above algorithm.

sub postfix:<²>($n) { $n * $n }

sub crosses([$x1, $y1], $R1, [$x2, $y2], $R2) {
    my $xd = $x2 - $x1;
    my $yd = $y2 - $y1;
    my $d = sqrt $xd² + $yd²;

    die "Circles are identical"
        if $d == 0 && $R1 == $R2;

    return crosses([$x2, $y2], $R2, [$x1, $y1], $R1)
        if $R1 > $R2;

    my $β = atan2 $y2 - $y1, $x2 - $x1;
    my $x = $d / $R1;
    my $R = $R2 / $R1;

    sub transform-back([$x, $y]) {
        [round($x1 + $R1 * $x, 1e-3),
         round($y1 + $R1 * $y, 1e-3)];
    }

    sub angle($α) {
        transform-back [cos($β + $α), sin($β + $α)];
    }

    if $R !~~ $x-1..$x+1 {
        return;
    }
    elsif $R == $x-1 {
        return angle(0);
    }
    elsif $R == $x+1 {
        return angle(pi);
    }
    else {  # $R ~~ $x-1 ^..^ $x+1
        my $α = acos ($x² - $R² + 1)/(2 * $x);
        return angle($α), angle(-$α);
    }
}

use Test;

is crosses([0, 0], 1, [5, 0], 1), (), "two circles that don't touch";
is crosses([0, 0], 1, [2, 0], 1), ([1, 0]), "two circles that touch in one point";
is crosses([0, 0], 1, [2, 0], 3), ([-1, 0]), "two circles that touch in the opposite point";
is crosses([0, 0], 5, [8, 0], 5), ([4, 3], [4, -3]), "two circles that touch in two points";
is crosses([0, 0], 5, [0, 8], 5), ([-3, 4], [3, 4]), "rotations are taken into account, too";
is crosses([20, 30], 5, [28, 30], 5), ([24, 33], [24, 27]), "translations are taking into account, too";
is crosses([0, 0], 1, [0, 0], 5), (), "degenerate case I: two circles inside one another";
dies_ok { crosses([0, 0], 1, [0, 0], 1) }, "degenerate case II: two identical circles";
is crosses([0, 1], 5, [1, 0], 1), (), "larger circle before smaller";

done;