carto_flow.symbol_cartogram.placement¶

Placement algorithms for symbol cartograms.

Classes:

CirclePhysicsSimulator –

Physics-based simulator for resolving circle overlaps.
ExponentialMovingStats –

EMA tracker for mean and std of vector-valued observations.
ScalarEMA –

EMA tracker for a single scalar value.
TopologyPreservingSimulator –

Two-phase force-based simulator with topology preservation.

Functions:

assign_to_grid_hungarian –

Optimal assignment of regions to grid cells using Hungarian algorithm.
fill_internal_holes –

Post-process grid assignments to fill internal holes.
resolve_circle_overlaps –

Resolve circle overlaps via global expansion + local separation.

CirclePhysicsSimulator ¶

CirclePhysicsSimulator(
    positions: NDArray[floating],
    radii: NDArray[floating],
    original_positions: NDArray[floating] | None = None,
    adjacency: NDArray[floating] | None = None,
    spacing: float = 0.05,
    compactness: float = 0.5,
    topology_weight: float = 0.3,
    damping: float = 0.85,
    dt: float = 0.15,
    max_velocity: float = 3.0,
    k_repel: float = 15.0,
    k_attract: float = 2.0,
)

Physics-based simulator for resolving circle overlaps.

Uses a two-phase approach: 1. Separation phase: Strong repulsion only (no attraction) until overlaps resolved 2. Settling phase: Gentle attraction while maintaining separation

Internally normalizes to unit scale for numerical stability.

Parameters:

compactness (float, default: 0.5 ) –

Balance between centroid-attraction and neighbor-attraction (0-1). 0 = symbols attracted only to original centroids 1 = symbols attracted only to neighbors (tight cluster)
damping (float, default: 0.85 ) –

Velocity damping factor (0-1). Default: 0.85
dt (float, default: 0.15 ) –

Integration timestep. Default: 0.15
max_velocity (float, default: 3.0 ) –

Maximum velocity magnitude. Default: 3.0
k_repel (float, default: 15.0 ) –

Repulsion force coefficient. Default: 15.0
k_attract (float, default: 2.0 ) –

Base attraction force coefficient. Default: 2.0

Methods:

run –

Run simulation until convergence or max iterations.
step –

Perform one simulation step.

run ¶

run(
    max_iterations: int = 500,
    tolerance: float = 0.0001,
    show_progress: bool = True,
    save_history: bool = False,
) -> tuple[
    NDArray[np.floating],
    dict[str, Any],
    list[NDArray[np.floating]] | None,
]

Run simulation until convergence or max iterations.

Returns:

positions ( ndarray ) –

Final symbol positions (in original coordinate system).
info ( dict ) –

Simulation statistics.
history ( list or None ) –

Position history if save_history=True (in original coordinates).

step ¶

step(
    apply_attraction: bool = False,
) -> tuple[int, float, float]

Perform one simulation step.

Parameters:

apply_attraction (bool, default: False ) –

Whether to apply attraction toward original positions.

Returns:

n_overlaps ( int ) –

Number of overlapping pairs.
max_velocity ( float ) –

Maximum velocity magnitude.
max_gap_ratio ( float ) –

Maximum gap ratio (how far neighbors are from touching).

ExponentialMovingStats ¶

ExponentialMovingStats(
    n: int,
    dim: int,
    n_eff: int = 20,
    *,
    adaptive: bool = True,
)

EMA tracker for mean and std of vector-valued observations.

Maintains per-element exponential moving averages of mean and variance for vector-valued time series. Used for steady-state detection by tracking displacement vectors over iterations.

Parameters:

n (int) –

Number of elements (e.g., circles).
dim (int) –

Vector dimension (e.g., 2 for 2D displacement).
n_eff (int, default: 20 ) –

Effective window size. Alpha = 2 / (n_eff + 1).
adaptive (bool, default: True ) –

If True, alpha starts at 1/k and decays to the fixed value, providing faster initial convergence.

Methods:

update –

Update with new observation x of shape (n, dim).

Attributes:

mean_magnitude (NDArray[floating]) –

Per-element magnitude of mean vector: ||mu_i||.
std_magnitude (NDArray[floating]) –

Per-element std magnitude: sqrt(sum of component variances).

mean_magnitude `property` ¶

mean_magnitude: NDArray[floating]

Per-element magnitude of mean vector: ||mu_i||.

std_magnitude `property` ¶

std_magnitude: NDArray[floating]

Per-element std magnitude: sqrt(sum of component variances).

update ¶

update(x: NDArray[floating]) -> None

Update with new observation x of shape (n, dim).

ScalarEMA ¶

ScalarEMA(
    n_eff: int = 20,
    *,
    adaptive: bool = True,
    initial_value: float = 0.0,
)

EMA tracker for a single scalar value.

Parameters:

n_eff (int, default: 20 ) –

Effective window size. Alpha = 2 / (n_eff + 1).
adaptive (bool, default: True ) –

If True, alpha starts at 1/k and decays to the fixed value.
initial_value (float, default: 0.0 ) –

Value before the first update. Default: 0.0

Methods:

update –

Update with new scalar observation.

update ¶

update(x: float) -> None

Update with new scalar observation.

TopologyPreservingSimulator ¶

TopologyPreservingSimulator(
    positions: NDArray[floating],
    radii: NDArray[floating],
    original_positions: NDArray[floating] | None = None,
    adjacency: NDArray[floating] | None = None,
    spacing: float = 0.05,
    compactness: float = 0.5,
    topology_weight: float = 0.3,
    overlap_tolerance: float = 0.0001,
    expansion_max_iterations: int = 20,
    max_expansion_factor: float = 2.0,
    topology_gate_distance: float = 2.5,
    neighbor_weight: float = 0.5,
    origin_weight: float = 0.0,
    force_mode: str = "direction",
    contact_tolerance: float = 0.02,
    contact_iterations: int = 3,
    max_step: float = 0.3,
    contact_transfer_ratio: float = 0.5,
    contact_elasticity: float = 0.0,
    size_sensitivity: float = 0.0,
    global_step_fraction: float = 0.5,
    local_step_fraction: float = 0.5,
    overlap_projection_iters: int = 5,
    step_smoothing_window: int = 20,
    convergence_window: int = 50,
    adaptive_ema: bool = True,
)

Two-phase force-based simulator with topology preservation.

Unlike CirclePhysicsSimulator which uses velocity-based physics, this simulator uses:

Overlap Resolution Phase: Global expansion + overlap projection to reach a non-overlapping state
Packing Phase: Force-based refinement with:
Distance-gated angular topology force (preserves neighbor directions)
Neighbor tangency spring (pulls separated neighbors together)
Global centroid attraction force (pulls toward original centroid)
Origin attraction force (pulls each circle toward its original position)
Iterative contact reaction (handles compressive forces at contacts)

The contact reaction constraint allows circles to slide along each other without penetrating, enabling tighter packing while maintaining topology.

Parameters:

positions (NDArray[floating]) –

Initial symbol positions, shape (n, 2).
radii (NDArray[floating]) –

Symbol radii, shape (n,).
original_positions (NDArray[floating] | None, default: None ) –

Original centroid positions for topology reference.
adjacency (NDArray[floating] | None, default: None ) –

Adjacency matrix of shape (n, n). Required for topology forces.
spacing (float, default: 0.05 ) –

Minimum gap as fraction of average radius. Default: 0.05
compactness (float, default: 0.5 ) –

Global compaction strength (0-1). Default: 0.5
topology_weight (float, default: 0.3 ) –

Topology preservation strength (0-1). Default: 0.3
overlap_tolerance (float, default: 0.0001 ) –

Overlap tolerance for overlap resolution convergence, as fraction of average radius. Default: 1e-4
expansion_max_iterations (int, default: 20 ) –

Maximum outer iterations for overlap resolution. Default: 20
max_expansion_factor (float, default: 2.0 ) –

Maximum expansion factor clamp per iteration. Default: 2.0
topology_gate_distance (float, default: 2.5 ) –

Topology force gate distance (in sum of radii). Default: 2.5
neighbor_weight (float, default: 0.5 ) –

Neighbor tangency force coefficient. Default: 0.5
origin_weight (float, default: 0.0 ) –

Origin attraction force strength. Pulls each circle toward its original position. Set to 0 to disable. Default: 0.0 - 0: No origin attraction (current behavior) - 0.1-0.5: Gentle pull toward original positions - > 1.0: Strong pull, may interfere with topology preservation
force_mode (str, default: 'direction' ) –

How attraction force magnitude is computed. Applies to both the global centroid attraction force and the origin attraction force. Default: "direction" - "direction": Constant magnitude with drop-off near target - "linear": Force proportional to distance (spring) - "normalized": Force proportional to distance / radius
contact_tolerance (float, default: 0.02 ) –

Contact detection tolerance (fraction of sum of radii). Default: 0.02
contact_iterations (int, default: 3 ) –

Number of contact reaction passes per packing step. Default: 3
max_step (float, default: 0.3 ) –

Maximum step size (fraction of avg radius). Default: 0.3
contact_transfer_ratio (float, default: 0.5 ) –

Balance between cancel (0) and transfer (1) of compressive forces at contact points. Default: 0.5
contact_elasticity (float, default: 0.0 ) –

Controls net compression vs bounce behavior (-1 to 1). Default: 0.0
size_sensitivity (float, default: 0.0 ) –

Controls how step size scales with circle radius. Default: 0.0
overlap_projection_iters (int, default: 5 ) –

Overlap projection iterations per packing step. Default: 5
step_smoothing_window (int, default: 20 ) –

EMA window for step smoothing. Default: 20
convergence_window (int, default: 50 ) –

EMA window for displacement convergence tracking. Default: 50
adaptive_ema (bool, default: True ) –

Whether EMA uses adaptive warmup (alpha starts at 1/k). Default: True

Notes

The topology force uses distance gating: it only acts when circles are within topology_gate_distance * (r_i + r_j) distance. This prevents distant circles from exerting topology forces, focusing preservation on local relationships.

Methods:

packing_step –

Perform one packing refinement iteration.
run –

Run both stages: overlap resolution then circle packing.
run_circle_packing –

Run circle packing (Stage 2) until convergence or max iterations.
run_overlap_resolution –

Overlap Resolution Phase: Reach non-overlapping state via balanced global + local separation.

packing_step ¶

packing_step() -> tuple[float, float]

Perform one packing refinement iteration.

Returns:

drift ( float ) –

Mean relative magnitude of smoothed displacement vectors. Trends to zero at steady state (symmetric jitter cancels).
jitter ( float ) –

Mean relative std of displacement vectors. Measures oscillation amplitude around equilibrium.

run ¶

run(
    max_iterations: int = 500,
    tolerance: float = 0.025,
    show_progress: bool = True,
    save_history: bool = False,
) -> tuple[
    NDArray[np.floating],
    dict[str, Any],
    list[NDArray[np.floating]] | None,
]

Run both stages: overlap resolution then circle packing.

Equivalent to calling :meth:run_overlap_resolution followed by :meth:run_circle_packing. Can be called multiple times; EMA state is reset at the start of each packing phase.

Parameters:

max_iterations (int, default: 500 ) –

Maximum number of packing iterations. Default: 500
tolerance (float, default: 0.025 ) –

Convergence threshold for mean step size. Default: 1e-4
show_progress (bool, default: True ) –

Whether to display progress bar. Default: True
save_history (bool, default: False ) –

Whether to save position history. Default: False

Returns:

positions ( NDArray[floating] ) –

Final symbol positions in original coordinate system.
info ( dict ) –

Simulation statistics including: - "iterations": Total iterations (stage1 + stage2) - "converged": Whether convergence criteria met - "final_overlaps": Remaining overlap count - "stage1_iterations": Overlap resolution iteration count - "stage2_iterations": Packing iteration count - "final_drift": Final smoothed drift metric - "final_jitter": Final jitter metric - "drift_history": Per-iteration drift values - "jitter_history": Per-iteration jitter values
history ( list[NDArray[floating]] | None ) –

Position history if save_history=True, else None.

run_circle_packing ¶

run_circle_packing(
    max_iterations: int = 500,
    tolerance: float = 0.025,
    show_progress: bool = True,
    save_history: bool = False,
) -> tuple[
    NDArray[np.floating],
    dict[str, Any],
    list[NDArray[np.floating]] | None,
]

Run circle packing (Stage 2) until convergence or max iterations.

Resets EMA state so this method can be called multiple times or after :meth:run_overlap_resolution. Uses :meth:packing_step internally.

Parameters:

max_iterations (int, default: 500 ) –

Maximum number of packing iterations. Default: 500
tolerance (float, default: 0.025 ) –

Convergence threshold for mean step size. Default: 1e-4
show_progress (bool, default: True ) –

Whether to display progress bar. Default: True
save_history (bool, default: False ) –

Whether to save position history. Default: False

Returns:

positions ( NDArray[floating] ) –

Final symbol positions in original coordinate system.
info ( dict ) –

Simulation statistics including: - "converged": Whether convergence criteria met - "final_overlaps": Remaining overlap count - "stage2_iterations": Packing iteration count - "final_drift": Final smoothed drift metric - "final_jitter": Final jitter metric - "drift_history": Per-iteration drift values - "jitter_history": Per-iteration jitter values
history ( list[NDArray[floating]] | None ) –

Position history if save_history=True, else None.

run_overlap_resolution ¶

run_overlap_resolution() -> dict[str, Any]

Overlap Resolution Phase: Reach non-overlapping state via balanced global + local separation.

Alternates partial global expansion (using the exact expansion factor) with partial local pairwise separation. The global_step_fraction and local_step_fraction parameters control the relative weight of each.

Can be called independently or as part of :meth:run.

Returns:

info ( dict ) –

{"iterations": int, "final_max_overlap": float}

assign_to_grid_hungarian ¶

assign_to_grid_hungarian(
    centroids: NDArray[floating],
    grid_centers: NDArray[floating],
    adjacency: NDArray[floating] | None = None,
    tile_adjacency: NDArray[bool_] | None = None,
    vertex_adjacency: NDArray[bool_] | None = None,
    *,
    origin_weight: float = 1.0,
    neighbor_weight: float = 0.3,
    topology_weight: float = 0.0,
    compactness: float = 0.0,
) -> NDArray[np.intp]

Optimal assignment of regions to grid cells using Hungarian algorithm.

The cost function combines four terms (all normalized to [0, 1]):

Origin cost: Squared Euclidean distance from each region's centroid to each grid cell. Weight: origin_weight.
Neighbor cost: Squared BFS hop distance for each adjacent pair (shifted by 1 so edge neighbors cost 0, hop 2 costs 1, hop 3 costs 4, etc.). Vertex-adjacent tiles get a reduced penalty of 0.2. Not normalized by max — neighbor_weight directly scales the raw squared-hop cost.
Topology cost: For each adjacent pair, penalizes assignments that reverse the relative direction between neighbors. Weight: topology_weight.
Compactness cost: Penalizes assignments far from the grid center. Weight: compactness.

Parameters:

centroids (np.ndarray of shape (n, 2)) –

Original region centroids.
grid_centers (np.ndarray of shape (m, 2)) –

Grid cell centers (m >= n).
adjacency (np.ndarray of shape (n, n), default: None ) –

Region adjacency matrix. Required for neighbor and topology costs.
tile_adjacency (np.ndarray of shape (m, m), default: None ) –

Tile edge adjacency matrix.
vertex_adjacency (np.ndarray of shape (m, m), default: None ) –

Tile vertex-only adjacency matrix (tiles sharing exactly one vertex but no edge).
origin_weight (float, default: 1.0 ) –

Weight for origin (centroid distance) cost. Default: 1.0.
neighbor_weight (float, default: 0.3 ) –

Weight for neighbor cost. Default: 0.3.
topology_weight (float, default: 0.0 ) –

Weight for neighbor orientation cost. Default: 0.0.
compactness (float, default: 0.0 ) –

Weight for compactness cost. Default: 0.0.

Returns:

np.ndarray of shape (n,) –

Indices into grid_centers for each centroid.

fill_internal_holes ¶

fill_internal_holes(
    assignments: NDArray[intp],
    tile_adjacency: NDArray[bool_],
    centroids: NDArray[floating],
    grid_centers: NDArray[floating],
    original_polygons: list,
    *,
    min_hole_fraction: float = 0.5,
    verbose: bool = False,
) -> NDArray[np.intp]

Post-process grid assignments to fill internal holes.

An internal hole is an unoccupied tile surrounded by occupied tiles that cannot reach the grid boundary through other unoccupied tiles. Geographic gaps (e.g. internal lakes) present in the original geometries are preserved by comparing the number of grid holes to the number of geographic holes.

Parameters:

assignments ((n,) int array) –

Current region-to-tile assignments (indices into grid_centers).
tile_adjacency ((m, m) bool array) –

Edge-based tile adjacency matrix. Used for the flood-fill that classifies exterior vs. internal tiles, for grouping holes into connected components, and for shift chain BFS. Should use strict edge adjacency (shared vertices >= 2) so that vertex-only touches don't leak the flood-fill through gaps.
centroids ((n, 2) array) –

Original region centroids.
grid_centers ((m, 2) array) –

Tile center positions.
original_polygons (list of Polygon) –

Original region geometries, used to detect expected geographic gaps.
min_hole_fraction (float, default: 0.5 ) –

Minimum area of a geographic interior ring, as a fraction of one tile's area, for it to count as a genuine geographic gap. Rings smaller than this are treated as boundary artifacts and ignored.
verbose (bool, default: False ) –

If True, print diagnostic information about the hole-filling process.

Returns:

(n,) int array –

Updated assignments with internal holes filled.

resolve_circle_overlaps ¶

resolve_circle_overlaps(
    positions: NDArray[floating],
    radii: NDArray[floating],
    *,
    spacing: float = 0.05,
    max_iterations: int = 20,
    overlap_tolerance: float = 0.0001,
    global_step_fraction: float = 0.5,
    local_step_fraction: float = 0.5,
    max_expansion_factor: float = 2.0,
    rng: Generator | None = None,
) -> tuple[NDArray[np.floating], dict[str, Any]]

Resolve circle overlaps via global expansion + local separation.

Alternates partial global expansion from the weighted centroid with partial local pairwise separation until all overlaps are resolved.

This is a standalone function extracted from TopologyPreservingSimulator for reuse in simple layout algorithms that only need overlap resolution.

Parameters:

positions ((n, 2) array) –

Circle center positions.
radii ((n,) array) –

Circle radii.
spacing (float, default: 0.05 ) –

Minimum gap as fraction of average radius. Default: 0.05
max_iterations (int, default: 20 ) –

Maximum outer iterations. Default: 20
overlap_tolerance (float, default: 0.0001 ) –

Convergence tolerance as fraction of average radius. Default: 1e-4
global_step_fraction (float, default: 0.5 ) –

Fraction of global expansion to apply per iteration (0-1]. Default: 0.5
local_step_fraction (float, default: 0.5 ) –

Fraction of local separation to apply per iteration (0-1]. Default: 0.5
max_expansion_factor (float, default: 2.0 ) –

Maximum expansion factor clamp per iteration. Must be > 1.0. Default: 2.0
rng (Generator, default: None ) –

Random number generator for coincident circle handling. If None, a default generator with seed 42 is used.

Returns:

positions ( (n, 2) array ) –

Resolved positions with no overlaps (or minimal remaining overlap).
info ( dict ) –

Statistics with keys: - "iterations": Number of iterations performed - "final_max_overlap": Maximum remaining overlap as fraction of avg radius

Examples:

>>> positions = np.array([[0, 0], [0.5, 0], [1, 0]])
>>> radii = np.array([0.4, 0.4, 0.4])
>>> resolved, info = resolve_circle_overlaps(positions, radii, spacing=0.1)
>>> info["iterations"]
3

carto_flow.symbol_cartogram.placement¶

CirclePhysicsSimulator ¶

run ¶

step ¶

ExponentialMovingStats ¶

mean_magnitude property ¶

std_magnitude property ¶

update ¶

ScalarEMA ¶

update ¶

TopologyPreservingSimulator ¶

packing_step ¶

run ¶

run_circle_packing ¶

run_overlap_resolution ¶

assign_to_grid_hungarian ¶

fill_internal_holes ¶

resolve_circle_overlaps ¶

mean_magnitude `property` ¶

std_magnitude `property` ¶