Apollonius tenth problem: Tangent circle to three other circles: Effectively solved by moebius transformation

Today I played around with circles. My aim is to implement a python package for closest disc packaging. But first things first: Any algorithm in this category has the need to determine the tangent circle to three other circles effectively.

I found an interesting article [1] that tackles this problem utilizing a moibius transformation and thus solves it analytically.

Asume we have three circles C1,..,C3.

The really cool idea of this paper is to shrink (better term maybe substract of) the radii of the circles so that one radius becomes zero: Let's assume it is C1. So we got C1 with a radius of zero.

Then we transform the euclidian plane so that C1 is in the origin of a new complex plane Z. Then we transform Z with a moibius Z->1/Z tranformation opbtaining a new Plane W.

In the W-Plane C1 is pushed to infinity leaving only C2-> W2 and C3 -> W3 as circles. If we now construct tangents T1 and T2 on W2 and W3. T1, T2 are touching W2 and W3 and since they are infinite lines touching infinity (the transformed C1). After an appropriate back moibius transformation W->1/W the former tangents become the Appolonius circles we are looking for.


Colored red the three circles we like to have a tangent circle for an in green and orange the Apollonius tangent circles.

There may be two (seen above), one (below), or zero (below, below) solutions.

In this case no tangent circle can be constructed.


import math
from random import random
import matplotlib.pyplot as plt
from datetime import datetime
fig, ax = plt.subplots(figsize=(6, 6))
ax.set(xlim=(-10, 10), ylim=(-10, 10))
EXACT = 1e-10
class Circ(object):
def __init__(self, x, y, r):
self.x = x
self.y = y
self.r = r
def rand(self, rand_xy, rand_r):
circ = Circ(
random() * rand_xy,
random() * rand_xy,
random() * rand_r
return circ
def shrink(self, amount):
return Circ(self.x, self.y, self.r-amount)
def distance(self, c):
distance = math.sqrt((self.x-c.x)**2 + (self.y-c.y)**2) - self.r -c.r
return distance
def overlap(self, c):
return self.distance(c) < 0
class Tangent(object):
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
def backtransform(self, c1):
a = self.a/self.c
b = self.b/self.c
return Circ(
c1.x -a/2.,
c1.y +b/2,
math.sqrt(a**2 + b**2)/2 - c1.r
def tangets(circ1, circ2):
dx = circ2.x - circ1.x
dy = circ2.y - circ1.y
dr = circ2.r - circ1.r
D = math.sqrt(dx * dx + dy *dy)
X = dx/D
Y = dy/D
R = dr/D
a1 = R * X - Y*math.sqrt(1 - R*R)
b1 = R * Y + X*math.sqrt(1 - R*R)
c1 = circ1.r - (a1*circ1.x + b1*circ1.y)
a2 = R * X + Y*math.sqrt(1 - R*R)
b2 = R * Y - X*math.sqrt(1 - R*R)
c2 = circ1.r - (a2*circ1.x + b2*circ1.y)
return Tangent(a1, b1, c1), Tangent(a2, b2, c2),
def moebius_transform(circ):
D = (circ.x-c1.x)**2 + (circ.y-c1.y)**2 - circ.r**2
xr = (circ.x-c1.x)/D
yr = -(circ.y-c1.y)/D
rr = circ.r/abs(D)
return Circ(xr, yr, rr)
def point(a,b,c,x):
return (-c-a*x) / b
def plot_tangents(tgs):
for tg in tgs:
(0, point(tg.a, tg.b, tg.c,0)),
(10, point(tg.a, tg.b, tg.c,10)),
def plot_circ(circ, **kw):
return plt.Circle((circ.x, circ.y), circ.r, **kw)

c1 = Circ.rand(5,3)
while True:
c2 = Circ.rand(5,3)
if not c2.overlap(c1):
while True:
c3 = Circ.rand(8,4)
if not (c3.overlap(c1) or c3.overlap(c2)):
circles = [c1, c2, c3]

c2_shrunk = c2.shrink(c1.r)
c3_shrunk = c3.shrink(c1.r)
circ1 = plot_circ(c1, color='r', fill=None)
circ2 = plot_circ(c2, color='r', fill=None)
circ3 = plot_circ(c3, color='r', fill=None)
#circ2_shrunk = plot_circ(c2_shrunk, color='r', fill=None, ls='--')
#circ3_shrunk = plot_circ(c3_shrunk, color='b', fill=None, ls='--')
tgs = tangets(moebius_transform(c2_shrunk),
A1 = tgs[0].backtransform(c1)
A2 = tgs[1].backtransform(c1)

good = True
for c in circles:
dist = c.distance(A1)
if dist < -EXACT or dist > EXACT:
good = False
if good:
circ_A1 = plot_circ(A1, color='g', fill=None, ls=':')
good = True
for c in circles:
dist = c.distance(A2)
if dist < -EXACT or dist > EXACT:
good = False
if good:
circ_A2 = plot_circ(A2, color='orange', fill=None, ls=':')
with open(str(datetime.now())+'.png', 'wb') as outfile:

This code is crap and was never meant for anything than the dump. But it shows the prove of concept.

The above algorithm can be modified to also solve the problem of a tangent circle of two circles in an enclosing circle. This is vital for algorithms of disc packaging into a circle.





 [1] https://www.sciencedirect.com/science/article/abs/pii/S0010448505001016