Determining whether two circles intersect at all is fairly simple: we calculate whether the distance between their center points is less than or equal to the sum of their two radiuses.(note below)
Let's consider the two circles to be \$A\$ and \$B\$: we'll define their center points as vectors \$c_A\$ and \$c_B\$, and their radii as \$r_A\$ and \$r_B\$. The circles are colliding if:
$$ \tag{0} \lvert c_A - c_B \rvert \le r_A + r_B $$
... where \$\lvert this \rvert\$ represents a vector's magnitude (length).
Here's that equation represented as pseudocode:
class Circle {
center: Vector2
radius: Float
}
function Colliding(a: Circle, b: Circle) returns Boolean {
Vector2 diff = a.center - b.center
Float maxDistance = a.radius + b.radius
return diff.magnitude <= maxDistance
}
Note: We're counting the edges exactly touching—the distance being exactly the sum of the two radiuses—as a collision. If you don't want to count this as a collision then in the above formula and code sample, where they use \$\le\$ or <=, you should instead use \$<\$ or <.
(This section is heavy on mathematics. For code, skip to the next section.)
“Intersection of Two Circles” by Paul Bourke (1997) describes an algorithm for determining the exact intersection points. It provides this diagram:
In this diagram, \$P_0\$ and \$P_1\$ are the center points of the two circles, and \$r_0\$ and \$r_1\$ are their radii.
First we determine the distance (\$d\$) between the circles:
$$ \tag{1} d = \lvert P_1 - P_0 \rvert $$
Then we'll check a couple of potential cases which result in no intersections.
$$ \tag{2} \begin{array}{lll} \text{case 1:} & d > r_0 + r_1 \\ \text{case 2:} & d < \lVert r_0 - r_1 \rVert \; \text{or} \; d = 0 \end{array} $$
- If case 1 is true, the circles are wholly separate and there is no edge intersection.
- If case 2 is true, one circle wholly contains the other, and there is no edge intersection to calculate, or rather the intersection is 100% of the smallest circle. (Note we're subtracting not adding; \$\lVert this \rVert\$ represents absolute value.)
If neither is true, we'll proceed.
In that diagram, there are two triangles we can observe: one is \$P_0 P_2 P_3\$, which has \$r_0\$, \$a\$, and \$h\$ for its edges. The other is \$P_1 P_2 P_3\$ which has edges \$r_1\$, \$b\$, and \$h\$. We need to calculate \$P_2\$, \$a\$, and \$h\$, and then eventually we can work out \$P_3\$ which represents the intersection points we're looking for. We never use \$b\$ so we'll leave that aside.
First we'll calculate \$a\$:
$$ \tag{3} a = \frac{r_0^2 - r_1^2 + d^2}{2d} $$
Then \$h\$: $$ \tag{4} \begin{array}{rl} \text{given} & a^2 + h^2 = r_0^2, \\ \text{then} & h^2 = r_0^2 - a^2 \\ \text{therefore} & h = \sqrt{r_0^2 - a^2} \\ \end{array} $$
Then \$P_2\$:
$$ \tag{5} P_2 = P_0 + \frac {a(P_1 - P_0)}{d} $$
If the circles are exactly as far apart as our combined radiuses, \$P_2\$ is our single (only) collision point:
$$ \tag{6} \begin{array}{ll} \text{case 3:} & d = r_0 + r_1 \end{array} $$
If case 3 is true we just use \$P_2\$; done.
Otherwise we have two collision points, represented in the diagram as \$P_3\$. We'll calculate \$P_3\$ by its coordinates \$(x_3, y_3)\$. In the following, \$x_0\$/\$y_0\$ thru \$x_2\$/\$y_2\$ represent the x- and y-coords of \$P_0\$ thru \$P_2\$.
$$ \tag{7} \begin{align} x_3 &= x_2 \pm \frac{h(y_1 - y_0)}{d} \\ y_3 &= y_2 \mp \frac{h(x_1 - x_0)}{d} \end{align} $$
So, \$P_3\$ is actually two points, right? Let's call them \$\alpha\$ and \$\beta\$ (alpha and beta). We follow equation 7 to calculate them as follows:
$$ \tag{8} \text{for }\alpha\text{:} \\ \begin{align} x_\alpha &= x_2 + \frac{h(y_1 - y_0)}{d} \\ y_\alpha &= y_2 - \frac{h(x_1 - x_0)}{d} \end{align} $$
$$ \tag{9} \text{for }\beta\text{:} \\ \begin{align} x_\beta &= x_2 - \frac{h(y_1 - y_0)}{d} \\ y_\beta &= y_2 + \frac{h(x_1 - x_0)}{d} \end{align} $$
Note: plus and minus, then minus and plus.
Now we have our intersection points, \$\alpha\$ and \$\beta\$.
Here's the above algorithm as code, written in Python 2.7.
from math import sqrt
# Determines whether two circles collide and, if applicable,
# the points at which their borders intersect.
# Based on an algorithm described by Paul Bourke:
# https://web.archive.org/web/20060911063359/http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/
# Arguments:
# P0 (Vector2): the centre point of the first circle
# P1 (Vector2): the centre point of the second circle
# r0 (number): radius of the first circle
# r1 (number): radius of the second circle
# Returns:
# False if the circles do not collide
# True if one circle wholly contains another such that the borders
# do not overlap, or overlap exactly (e.g. two identical circles)
# An array of two vectors containing the intersection points
# if the circle's borders intersect.
def Intersection(P0, P1, r0, r1):
if type(P0) != Vector2 or type(P1) != Vector2:
raise TypeError("P0 and P1 must be vectors")
# equation 1
offset = P1 - P0
d = offset.magnitude()
# equation 2: simple cases
if d > (r0 + r1):
# no collision
return False
elif d == 0 or d < abs(r0 - r1):
# full containment
return True
# equation 3
a = (r0**2 - r1**2 + d**2) / (2 * d)
# equation 4
h = sqrt(r0**2 - a**2)
# equation 5
P2 = P0 + a * (P1 - P0) / d
# equation 6
if (d == r0 + r1):
return [P2]
# equation 8
alpha_x = P2.x + h * (P1.y - P0.y) / d
alpha_y = P2.y - h * (P1.x - P0.x) / d
alpha = Vector2(alpha_x, alpha_y)
# equation 9
beta_x = P2.x - h * (P1.y - P0.y) / d
beta_y = P2.y + h * (P1.x - P0.x) / d
beta = Vector2(beta_x, beta_y)
return [alpha, beta]
# Simple 2D vector class.
# Based on work by @mcleonard on github:
# https://gist.github.com/mcleonard/5351452
class Vector2(object):
def __init__(self, x, y):
"""Create a vector, e.g. v = Vector2(10, 15)"""
self.x = x
self.y = y
def magnitude(self):
"""Returns the magnitude of this vector."""
return sqrt(self.x**2 + self.y**2)
def __add__(self, other):
"""Returns the vector addition of self and other."""
newx = self.x + other.x
newy = self.y + other.y
return Vector2(newx, newy)
def __sub__(self, other):
"""Returns the vector difference of self and other."""
newx = self.x - other.x
newy = self.y - other.y
return Vector2(newx, newy)
def __mul__(self, other):
"""Multiplies each component if other is a scalar"""
if type (other) == type(1) or type(other) == type(1.0):
return Vector2(self.x * other, self.y * other)
else:
raise NotImplementedError
def __rmul__(self, other):
return self.__mul__(other)
def __div__(self, other):
"""Divides each component if other is a scalar"""
if type (other) == type(1) or type(other) == type(1.0):
return Vector2(self.x / other, self.y / other)
else:
raise NotImplementedError
def __str__(self):
"""Returns this vector as a string of the form: (x, y)"""
return "(%(x)d, %(y)d)" % { "x": self.x, "y": self.y }
def format(input):
if isinstance(input, list):
return "\n " + "\n ".join(str(v) for v in input)
else:
return "\n " + str(input)
def run_test(label, expected, actual):
print label
print "Expected:", format(expected)
print "Actual:", format(actual)
print "\n"
def run_all_tests():
run_test("Intersection 1", \
["(0.5, -1.93649)", "(0.5, 1.93649)"], \
Intersection(Vector2(0,0), Vector2(1, 0), 2, 2) \
)
run_test("Intersection 2", \
["(3.39254, -0.749778)", "(-1.99992, 3.02495)"], \
Intersection(Vector2(2, 3), Vector2(5.5, 8), 4, 9) \
)
run_test("Intersection 3", \
["(5.14024, 9.90651)", "(9.93669, 6.70888)"], \
Intersection(Vector2(8, 9), Vector2(4, 3), 3, 7) \
)
run_test("Single-point edge collision", \
["(2, 0)"], \
Intersection(Vector2(0,0), Vector2(4, 0), 2, 2) \
)
run_test("Wholly inside", \
"True", \
Intersection(Vector2(0,0), Vector2(1, 0), 5, 2) \
)
run_test("No collision", \
"False", \
Intersection(Vector2(0,0), Vector2(5, 0), 2, 2) \
)
run_test("The same circle twice", \
"True", \
Intersection(Vector2(0,0), Vector2(0,0), 5, 5) \
)
print "Expected values are approximations.\n"
run_all_tests()
Run this code on trinket.io here.
Some tests are defined at the bottom of the file. You can verify your results in Wolfram Alpha by running a query to determine the intersection of two circles like this:
intersection ((x - h)^2 + (y - k)^2 = r^2), ((x - h)^2 + (y - k)^2 = r^2)
Where for each of the two circles, h = x-coord, k = y-coord, and r = the radius.
Here's the Wolfram results for each of those intersection test cases:
, this will give you a right-handed perpendicular vector.
