Circle Packing¶
A circle packing is a configuration of circles with a prescribed pattern of tangencies: one circle sits at every vertex of a triangulated graph, sized so that circles on adjacent vertices touch along their shared edge. Remarkably, the combinatorics almost pin down the geometry - once the radii on the boundary are fixed, every interior radius is determined uniquely. This rigidity makes circle packings behave like a discrete analogue of conformal (angle-preserving) maps, and a convenient tool for laying out tilings - in particular the mutually-tangent-incircle tilings used in the Intersecting_Cylinders notebook.
pleat solves for the radii with the iterative algorithm of Collins and Stephenson00099-8) as implemented in CirclePack (amongst many more features we do not re-implement here):
pack_euclidean(G, boundary_radii=...)— euclidean packing with prescribed boundary radii.pack_hyperbolic(G, boundary_x_radii=...)— hyperbolic packing in the Poincaré disk (finite boundary x-radii; horocycles not yet supported).
Both require triangulated, simply-connected (disk-topology) input.
For more on the theory of circle packings see Ken Stephenson's books.
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.collections import PatchCollection
from pleat.example_graphs import from_tiles
from pleat.example_tilesets import platonic, curved_platonic
from pleat.circle_packing import pack_euclidean, pack_hyperbolic
def draw_packing(P, ax=None, title=None, unit_circle=False):
"""Render a packed graph: one circle per vertex at ``v['pos']`` with radius ``v['radius']``."""
if ax is None:
_, ax = plt.subplots(figsize=(5, 5))
circles = []
centers = []
for v in P.vertices:
pos = v['pos']
if np.iscomplexobj(pos):
c = (float(pos.real), float(pos.imag))
else:
c = (float(pos[0]), float(pos[1]))
centers.append(c)
circles.append(plt.Circle(c, float(v['radius'])))
coll = PatchCollection(circles, facecolors='none', edgecolors='k', linewidth=0.7)
ax.add_collection(coll)
cs = np.array(centers)
radii = np.array([float(v['radius']) for v in P.vertices])
margin = radii.max() * 1.1
ax.set_xlim(cs[:, 0].min() - margin, cs[:, 0].max() + margin)
ax.set_ylim(cs[:, 1].min() - margin, cs[:, 1].max() + margin)
ax.set_aspect('equal')
ax.set_axis_off()
if unit_circle:
ax.add_artist(plt.Circle((0, 0), 1.0, facecolor='none', edgecolor='#aaa', linestyle='--'))
if title:
ax.set_title(title)
return ax
1. Euclidean packing of a regular triangular patch¶
The {3, 6} Platonic tiling. With uniform boundary radius 1.0, by symmetry every interior radius is also 1.0.
G = from_tiles(platonic(3), rings=3)
P = pack_euclidean(G, boundary_radii=1.0)
draw_packing(P, title='Uniform boundary, regular {3,6} lattice')
plt.show()
2. Euclidean packing with non-uniform boundary¶
The same combinatorics, but with varied boundary radii — pass a callable to let the radius depend on vertex position. Notice how the interior radii adjust so that the circles still close up (angle sum 2π) around every interior vertex.
G = from_tiles(platonic(3), rings=3)
def varied_boundary(v):
# angle around origin of the input position used as a stand-in for vertex id
p = v['pos']
theta = np.arctan2(p[1], p[0])
return 0.5 + 0.4 * np.cos(2 * theta)
P = pack_euclidean(G, boundary_radii=varied_boundary)
draw_packing(P, title='Varied boundary radii (cos 2θ)')
plt.show()
3. Non-regular triangulation via kis¶
Take a pentagonal tiling and apply kis (triangulate every face from its centroid). The resulting graph has mixed vertex degrees, so a uniform-boundary packing produces visibly varied interior radii.
It can also be useful to apply kis only to faces which are not triangular already, see section 5 for an example.
G = from_tiles(curved_platonic(5, 4), rings=2).kis()
P = pack_euclidean(G, boundary_radii=1.0)
draw_packing(P, title='kis(hex), uniform boundary')
plt.show()
4. Hyperbolic packing in the Poincaré disk¶
The same combinatorics, packed hyperbolically with boundary x-radii at 0.5. Positions live in the unit disk.
G = from_tiles(curved_platonic(5, 4), rings=2).kis()
P = pack_hyperbolic(G, boundary_x_radii=0.5)
draw_packing(P, title='Hyperbolic, boundary x-radii = 0.5', unit_circle=True)
plt.show()
Boundary x-radii approaching 1 (the maximal packing)¶
As boundary_x_radii → 1 the boundary circles become horocycles, internally tangent to the unit circle. The x = 1 case is now supported directly.
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
G = from_tiles(curved_platonic(5, 4), rings=2).kis()
for ax, x in zip(axes, (0.5, 0.8, 1.0)):
label = 'maximal (x = 1)' if x == 1.0 else f'boundary x = {x}'
P = pack_hyperbolic(G, boundary_x_radii=x)
draw_packing(P, ax=ax, title=label, unit_circle=True)
plt.show()
5. Prescribing boundary angles instead of radii¶
Use boundary_angles instead of boundary_radii to constrain the angle sum at each boundary vertex, leaving boundary radii as free variables. Passing "from_positions" reads those angles off G's existing positions — useful for matching a packing to an existing flat tiling. The angles must satisfy Gauss-Bonnet (Σ θ = π(F − 2 V_int)), which holds automatically for any flat input.
Specifying both boundary_radii and boundary_angles raises; the two modes are mutually exclusive.
# Build a kis(hex) graph: mixed-degree boundary, interesting per-vertex angles.
from pleat.rendering import multi_show
render_settings = dict(render_vertices=False)
G = from_tiles(curved_platonic(5, 3), rings=1).expand().kis(faces=lambda f: f.order() > 3)
G.convert_to_euclidean()
G.show(**render_settings)
# Pack with angles taken from G's original positions.
P_angles = pack_euclidean(G, boundary_angles='from_positions')
# Compare: pack the same graph with uniform boundary radii.
P_radii = pack_euclidean(G, boundary_radii=1.0)
P_maximal = pack_hyperbolic(G)
P_maximal.convert_to_euclidean()
fig, (a1, a2, a3) = plt.subplots(1, 3, figsize=(15, 5))
draw_packing(P_angles, ax=a1, title="boundary_angles='from_positions'")
draw_packing(P_radii, ax=a2, title='boundary_radii=1.0')
draw_packing(P_maximal, ax=a3, title='maximal hyperbolic')
plt.show()
multi_show(
[P_angles, P_radii, P_maximal],
titles=["boundary_angles='from_positions'", "boundary_radii=1.0", "maximal hyperbolic"],
**render_settings
)
See also¶
Intersecting_Cylinders— curved-folding tessellations built from tilings based on circle packings.