Tetrad covered general intersection in his post. Here I'll cover an algorithm that returns the specific points of intersection based on the formulae in this concise article. I'm matching my variable names to those in the article, so keep this diagram in mind - and probably in view too!
The language is Python. You can verify your results in Wolfram Alpha by running a query to determine the intersection of two circles like this:
intersection ((x - 0)^2 + (y - 0)^2 = 2^2), ((x - 1)^2 + (y - 0)^2 = 2^2)
or in the general case
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 = the x-coordinate of the centre of the circle, k = the y-coordinate, and r is the radius.
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:
# P0 (complex): the centre point of the first circle
# P1 (complex): the centre point of the second circle
# r0 (numeric): radius of the first circle
# r1 (numeric): radius of the second circle
# 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 complex numbers containing the intersection points
# if the circle's borders intersect.
def IntersectPoints(P0, P1, r0, r1):
if type(P0) != complex or type(P1) != complex:
raise TypeError("P0 and P1 must be complex types")
# d = distance
d = sqrt((P1.real - P0.real)**2 + (P1.imag - P0.imag)**2)
# n**2 in Python means "n to the power of 2"
# note: d = a + b
if d > (r0 + r1):
elif d < abs(r0 - r1):
elif d == 0:
a = (r0**2 - r1**2 + d**2) / (2 * d)
b = d - a
h = sqrt(r0**2 - a**2)
P2 = P0 + a * (P1 - P0) / d
i1x = P2.real + h * (P1.imag - P0.imag) / d
i1y = P2.imag - h * (P1.real - P0.real) / d
i2x = P2.real - h * (P1.imag - P0.imag) / d
i2y = P2.imag + h * (P1.real - P0.real) / d
i1 = complex(i1x, i1y)
i2 = complex(i2x, i2y)
return [i1, i2]
return "(" + str(c.real) + ", " + str(c.imag) + ")"
return CompToStr(p) + " , " + CompToStr(p)
ip = IntersectPoints
i = ip(complex(0,0), complex(1, 0), 2, 2)
s = ip(complex(0,0), complex(4, 0), 2, 2)
print "Intersection:", PairToStr(i)
print "Wholly inside:", ip(complex(0,0), complex(1, 0), 5, 2)
print "Single-point edge collision:", PairToStr(s)
print "No collision:", ip(complex(0,0), complex(5, 0), 2, 2)
Note that this algorithm uses the readily-available complex class for Python which can mimic a 2D Vector's
y via the
complex.imag attributes respectively. Mathematically speaking a complex is a 2D vector on the complex plane, which is why this works, so programmatically only the syntax is different. It's not optimal but I don't think Python natively has a proper geometric vector class.
Whether this was useful to you or not it was still fun. ;)