Enclosing radially convex set¶
Given a set of circles in the plane, let us find a star-shaped (radially convex) region that encloses all of them while minimizing a weighted sum of area and perimeter.
The enclosing shape is parameterized by its center \((c_x, c_y)\) and K radii at uniformly-spaced angles \(\theta_k = 2\pi k / K\). The boundary point at angle \(k\) is: $\(p_k = \text{center} + r_k \begin{pmatrix} \cos\theta_k \\ \sin\theta_k \end{pmatrix}\)$
The optimization minimizes a weighted sum of enclosure violation, area, and perimeter.
The enclosure loss penalizes squared violations of \(r_k \geq (\mathbf{c}_i - \mathbf{c}) \cdot \hat{\theta}_k + r_i\), i.e. the star boundary must extend at least as far as each circle's support in every sampled direction.
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import pandas as pd
from IPython.display import SVG
from jax import numpy as jnp
from vizopt.animation import SnapshotCallback, snapshots_to_animated_svg
from vizopt.base import OptimConfig
from vizopt.radially_convex import (
optimize_multiple_radially_convex_sets,
optimize_multiple_radially_convex_sets_with_movable_circles,
)
Basic start¶
# Three input circles: (cx, cy, radius)
circles = [
(0.0, 0.0, 1.0),
(3.0, 0.5, 0.8),
(1.0, 3.5, 2.0),
(6.0, 0.5, 0.5),
]
fig, ax = plt.subplots(figsize=(3, 3))
for cx, cy, r in circles:
ax.add_patch(plt.Circle((cx, cy), r, facecolor='steelblue', alpha=0.4, edgecolor='steelblue', linewidth=1.5))
ax.plot(cx, cy, '.', color='steelblue')
ax.set_aspect('equal')
ax.autoscale_view()
ax.margins(0.3)
ax.set_title('Input circles')
plt.tight_layout()
snapshot_cb = SnapshotCallback(every=50)
results, history, problem = optimize_multiple_radially_convex_sets(
circles,
sets=[list(range(len(circles)))],
k_angles=128,
weight_area=1.0,
weight_perimeter=5.0,
optim_config=OptimConfig(n_iters=5000, learning_rate=0.001),
callback=snapshot_cb,
)
result = results[0]
print('Center:', result['center'])
print('Min radius:', result['radii'].min().round(3), ' Max radius:', result['radii'].max().round(3))
print(f'Captured {len(snapshot_cb.snapshots)} snapshots')
cx, cy = result['center']
radii = result['radii']
angles = result['angles']
# Close the polygon for plotting
bx = np.append(cx + radii * np.cos(angles), cx + radii[0] * np.cos(angles[0]))
by = np.append(cy + radii * np.sin(angles), cy + radii[0] * np.sin(angles[0]))
fig, ax = plt.subplots(figsize=(5, 5))
ax.fill(bx, by, alpha=0.15, color='tomato', label='Enclosing shape')
ax.plot(bx, by, color='tomato', linewidth=2)
ax.plot(cx, cy, '+', color='tomato', markersize=10, markeredgewidth=2, label='Center')
# Draw radii from center to each boundary point
bx_pts = cx + radii * np.cos(angles)
by_pts = cy + radii * np.sin(angles)
ax.plot(
np.stack([np.full_like(angles, cx), bx_pts]),
np.stack([np.full_like(angles, cy), by_pts]),
color='tomato', linewidth=0.4, alpha=0.5,
)
for icx, icy, r in circles:
ax.add_patch(plt.Circle((icx, icy), r, facecolor='steelblue', alpha=0.4, edgecolor='steelblue', linewidth=1.5))
ax.plot(icx, icy, '.', color='steelblue')
ax.set_aspect('equal')
ax.autoscale_view()
ax.margins(0.2)
ax.legend()
ax.set_title('Optimized enclosing shape')
plt.tight_layout()
fig, ax = plt.subplots(figsize=(7, 3))
ax.plot(np.degrees(angles), radii, color='tomato', linewidth=1.5)
ax.set_xlabel('Angle (degrees)')
ax.set_ylabel('Radius')
ax.set_xlim(0, 360)
ax.set_xticks(np.arange(0, 361, 45))
ax.set_title('Optimized radii vs angle')
plt.tight_layout()
pd.DataFrame(history).set_index('iteration').plot(marker='.', figsize=(7, 3))
plt.ylabel('Loss value')
plt.title('Optimization history')
plt.tight_layout()
svg = snapshots_to_animated_svg(problem, snapshot_cb.snapshots, fps=5, size=500, history=history)
SVG(data=svg)
Multi-set¶
# Two clusters of circles — the boundaries must enclose each cluster
# without overlapping the other cluster's circles.
circles = [
# Set 0: left cluster
(0.0, 0.0, 0.6),
(1.2, 0.3, 0.5),
(0.3, 1.4, 0.4),
# Set 1: right cluster
(4.5, 0.0, 0.6),
(5.5, 0.5, 0.5),
(4.2, 1.3, 0.4),
# Set 2: isolated circle (not in any set — obstacle for both)
(2.5, 0.5, 0.3),
# Additional bottom circles
(1.2, -1.3, 0.5),
(5.5, -1.5, 0.5),
]
sets = [
[0, 1, 2], # left cluster
[3, 4, 5], # right cluster
[1, 3, 7, 8], # bottom set, partially intersecting left and right cluster
[3, 4, 5, 8] # right + bottom right
]
# Offsets per set: 0.1 for sets 0–2, 0.2 for set 3. Shape (S, 1) broadcasts to (S, N).
offsets = np.array([[0.1], [0.1], [0.1], [0.2]])
results, history, _ = optimize_multiple_radially_convex_sets(
circles,
sets,
k_angles=128,
weight_area=1.0,
weight_perimeter=2.0,
weight_exclusion=10.0,
weight_smoothness=2.,
offsets=offsets,
optim_config=OptimConfig(n_iters=5000, learning_rate=0.001),
)
colors = ["tomato", "steelblue", "violet", "green", "gray"]
fig, ax = plt.subplots(figsize=(8, 5))
for s, (result, color) in enumerate(zip(results, colors)):
cx, cy = result["center"]
radii = result["radii"]
angles = result["angles"]
bx = np.append(cx + radii * np.cos(angles), cx + radii[0] * np.cos(angles[0]))
by = np.append(cy + radii * np.sin(angles), cy + radii[0] * np.sin(angles[0]))
ax.fill(bx, by, alpha=0.15, color=color)
ax.plot(bx, by, color=color, linewidth=2, label=f"Set {s}")
ax.plot(cx, cy, "+", color=color, markersize=10, markeredgewidth=2)
# Draw radii from center to each boundary point
bx_pts = cx + radii * np.cos(angles)
by_pts = cy + radii * np.sin(angles)
ax.plot(
np.stack([np.full_like(angles, cx), bx_pts]),
np.stack([np.full_like(angles, cy), by_pts]),
color=color,
linewidth=0.4,
alpha=0.5,
)
for i, (cx, cy, r) in enumerate(circles):
if any(i in s for s in sets):
color = colors[next(si for si, s in enumerate(sets) if i in s)]
ax.add_patch(
plt.Circle(
(cx, cy), r, facecolor=color, alpha=0.5, edgecolor=color, linewidth=1.5
)
)
else:
ax.add_patch(
plt.Circle(
(cx, cy),
r,
facecolor="gray",
alpha=0.4,
edgecolor="gray",
linewidth=1.5,
)
)
ax.text(cx, cy + r + 0.1, "obstacle", ha="center", fontsize=8, color="gray")
ax.plot(cx, cy, ".", color="k", markersize=4)
ax.set_aspect("equal")
ax.autoscale_view()
ax.margins(0.2)
ax.legend()
ax.set_title("Multi-set: each boundary encloses its circles, avoids others")
plt.tight_layout()
pd.DataFrame(history).set_index('iteration').plot(marker='.', figsize=(7, 3))
plt.ylabel('Loss value')
plt.title('Multi-set optimization history')
plt.tight_layout()
Allowing circles to move¶
# Same setup as the multi-set example above, but circle positions are optimized too.
circles = [
# Set 0: left cluster
(0.0, 0.0, 0.6),
(1.2, 0.3, 0.5),
(0.3, 1.4, 0.4),
# Set 1: right cluster
(4.5, 0.0, 0.6),
(5.5, 0.5, 0.5),
(4.2, 1.3, 0.4),
# Set 2: isolated circle (obstacle for both)
(2.5, 0.5, 0.3),
# Additional bottom circles
(1.2, -1.3, 0.5),
(5.5, -1.5, 0.5),
]
sets = [
[0, 1, 2], # left cluster
[3, 4, 5], # right cluster
[1, 3, 7, 8], # bottom set, partially intersecting left and right cluster
[3, 4, 5, 8], # right + bottom right
]
offsets = np.array([[0.1], [0.1], [0.1], [0.2]])
results, circles_out, history, _ = optimize_multiple_radially_convex_sets_with_movable_circles(
circles,
sets,
k_angles=128,
weight_area=1.0,
weight_perimeter=2.0,
weight_exclusion=10.0,
weight_smoothness=2.0,
weight_position_anchor=1.0,
weight_circle_collision=100.,
offsets=offsets,
optim_config=OptimConfig(n_iters=10000, learning_rate=0.002),
)
# ── Plot ──────────────────────────────────────────────────────────────────────
colors = ["tomato", "steelblue", "violet", "green", "gray"]
fig, ax = plt.subplots(figsize=(8, 5))
for s, (result, color) in enumerate(zip(results, colors)):
cx, cy = result["center"]
radii = result["radii"]
angles = result["angles"]
bx = np.append(cx + radii * np.cos(angles), cx + radii[0] * np.cos(angles[0]))
by = np.append(cy + radii * np.sin(angles), cy + radii[0] * np.sin(angles[0]))
ax.fill(bx, by, alpha=0.15, color=color)
ax.plot(bx, by, color=color, linewidth=2, label=f"Set {s}")
ax.plot(cx, cy, "+", color=color, markersize=10, markeredgewidth=2)
circles_array = np.array(circles)
for i, ((ox, oy, r), (nx_, ny_, _)) in enumerate(zip(circles_array, circles_out)):
in_any_set = any(i in s for s in sets)
color = colors[next((si for si, s in enumerate(sets) if i in s), None)] if in_any_set else "gray"
# Draw arrow from original to optimized position
if np.hypot(nx_ - ox, ny_ - oy) > 0.01:
ax.annotate("", xy=(nx_, ny_), xytext=(ox, oy),
arrowprops=dict(arrowstyle="->", color="k", lw=1.0))
# Original position (faded)
ax.add_patch(plt.Circle((ox, oy), r, facecolor="none", edgecolor=color,
linewidth=1, linestyle="--", alpha=0.4))
# Optimized position
ax.add_patch(plt.Circle((nx_, ny_), r, facecolor=color, alpha=0.5,
edgecolor=color, linewidth=1.5))
ax.plot(nx_, ny_, ".", color="k", markersize=4)
ax.set_aspect("equal")
ax.autoscale_view()
ax.margins(0.2)
ax.legend()
ax.set_title("Movable circles: dashed = initial, solid = optimized (arrows show movement)")
plt.tight_layout()
British Islands — joint multi-set and circle layout¶
The British Islands have a natural nested set structure:
- Great Britain contains England, Scotland, Wales
- United Kingdom contains Great Britain + Northern Ireland
- British Islands contains United Kingdom + Jersey, Guernsey, Isle of Man
We optimize both the star-shaped boundaries of each set and the positions of the element circles simultaneously.
sets = {}
sets["Great Britain"] = {"Scotland", "England", "Wales"}
sets["United Kingdom"] = sets["Great Britain"] | {"Northern Ireland"}
sets["British Islands"] = {"Jersey", "Guernsey", "Isle of Man"} | sets["United Kingdom"]
sets
#from vizopt.radially_convex import optimize_multiple_radially_convex_sets
# Approximate relative sizes (proportional to land area, for illustration)
british_circle_radii = {
"England": 2.0,
"Scotland": 1.6,
"Wales": 0.7,
"Northern Ireland": 0.6,
"Isle of Man": 0.25,
"Jersey": 0.18,
"Guernsey": 0.15,
}
british_set_members = {
"Great Britain": ["England", "Scotland", "Wales"],
"United Kingdom": ["Great Britain", "Northern Ireland"],
"British Islands": ["United Kingdom", "Isle of Man", "Jersey", "Guernsey"],
}