5
\$\begingroup\$

I want to find whether 2 circles with radii r1 and r2 intersect, and if so, where they do so. Is there a simple solution?

\$\endgroup\$
  • \$\begingroup\$ Do you really need the actual intersection area or do you just need to know if you're in the intersection area? The latter is easier to solve--if you're closer than the radius to both centers you're in the intersection area. \$\endgroup\$ – Loren Pechtel Jan 8 '11 at 18:57
  • \$\begingroup\$ Related, for 3D: Sphere-Sphere intersection and Circle-Sphere intersection \$\endgroup\$ – doppelgreener Jun 16 '18 at 16:32
14
\$\begingroup\$

Simple collision: detecting whether two circles intersect at all

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 <.

Determining the exact intersection points

(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\$.

Code implementation

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:

\$\endgroup\$
10
\$\begingroup\$

Do you mean if the circles are overlapping? That's easy, just figure out the distance between the two and compare it to the r1 and r2. Or more specifically, calculate the squared distance between the two (it's faster) and compare it to (r1 + r2)^2.

If you mean what the actual intersection points are of the two circles, then I don't know the math for that offhand.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.