Circle packing

Circle Packing¶

Pack circles of given radii to minimize overlap and overall bounding box size, without any nesting or graph structure. Circle packing is one of the simplest examples of optimization for visualization.

%config InlineBackend.figure_formats = ['svg']

import pathlib

import numpy as np
from IPython.display import SVG
from matplotlib import patches as mpatches
from matplotlib import pyplot as plt

from vizopt.animation import snapshots_to_animated_svg
from vizopt.base import OptimConfig
from vizopt.templates import circle_packing

fig_folder = pathlib.Path("output") / "figs"
fig_folder.mkdir(parents=True, exist_ok=True)

rng = np.random.default_rng(0)
n_circles = 30
radii = rng.uniform(0.01, 1, size=30).tolist()
initial_node_xys = np.random.rand(n_circles, 2).astype(np.float32) * 5

def plot_circles(positions, radii):
    fig, ax = plt.subplots(figsize=(5, 5))
    colors = plt.cm.tab20.colors
    for i, (xy, r) in enumerate(zip(positions, radii)):
        ax.add_patch(mpatches.Circle(xy, radius=r, color=colors[i % len(colors)], alpha=0.6, ec="black", linewidth=0.5))

    margin = max(radii)
    ax.set_xlim(min(p[0] for p in positions) - margin, max(p[0] for p in positions) + margin)
    ax.set_ylim(min(p[1] for p in positions) - margin, max(p[1] for p in positions) + margin)
    ax.set_aspect("equal")
    ax.set_title(f"Circle packing: {len(radii)} circles")
    plt.axis("off")
    plt.tight_layout()

plot_circles(initial_node_xys, radii)

output

positions = circle_packing.optimize_circle_packing(
    radii=radii,
    weight_total_size=10.,
    collision_offset=0.1,
    optim_config=OptimConfig(n_iters=5000, learning_rate=0.01),
)

The optimizer compresses x and y independently (the total size penalty treats each axis separately), so circles are pushed into a compact rectangular arrangement rather than a circular cluster.

plot_circles(positions, radii)

output

Animation¶

from IPython.display import HTML
from vizopt.animation import SnapshotCallback, animate
from vizopt.templates.circle_packing import build_circle_packing_problem

problem = build_circle_packing_problem(
    radii=radii,
    weight_total_size=10.0,
    collision_offset=0.0,
    initial_node_xys=initial_node_xys,
)

cb = SnapshotCallback(every=50)
_, history = problem.optimize(OptimConfig(n_iters=1000, learning_rate=0.03), callback=cb)

svg_str = snapshots_to_animated_svg(
    problem, cb.snapshots, fps=5, history=history, log_scale=True, loss_curve_height=200
)

SVG(data=svg_str)

output