Analyze and Fix Topology¶

Lloyd relaxation optimizes cell areas but pays no attention to topology. Two issues can arise in any dataset:

• Adjacency violations — a pair of regions that share a border in the input ends up in Voronoi cells that do not touch.
• Orientation misalignment — the spatial direction between a pair of Voronoi cell centroids is inverted relative to the geographic direction between those regions.

When the dataset also contains grouped sub-regions (e.g. congressional districts grouped by state), two further issues can appear:

• Satellite cells — a group's Voronoi cells split into two or more disconnected components.
• Compactness — a group's Voronoi cells may not be compact, but rather form strings.

TopologyRepair attempts to address all of these issues. Adjacency and orientation repairs can run on any dataset; group contiguity and compactness repairs require group_by.

See also: Explanation: Contiguity Repair · Inspect and Improve Convergence · Tutorial

In [1]:

import matplotlib.pyplot as plt

import carto_flow.data as examples
import carto_flow.voronoi_cartogram as vor
from carto_flow.geo_utils.simplification import simplify_coverage
from carto_flow.voronoi_cartogram.visualization import plot_topology

us_districts = examples.load_us_census(population=True, level="congressional_district")
us_districts = simplify_coverage(us_districts, tolerance=5000, min_island_size=50000)

import matplotlib.pyplot as plt import carto_flow.data as examples import carto_flow.voronoi_cartogram as vor from carto_flow.geo_utils.simplification import simplify_coverage from carto_flow.voronoi_cartogram.visualization import plot_topology us_districts = examples.load_us_census(population=True, level="congressional_district") us_districts = simplify_coverage(us_districts, tolerance=5000, min_island_size=50000)

Grouped Voronoi Cartogram Without Topology Repair¶

Pass group_by to tell the algorithm which column defines the groups. Without topology repair, some districts may end up detached from other districts in the same state.

In [2]:

result = vor.create_voronoi_cartogram(
    us_districts,
    backend=vor.RasterBackend(resolution=256),
    options=vor.VoronoiOptions(n_iter=30, area_cv_tol=0.1),
    group_by="State Name",
)

result = vor.create_voronoi_cartogram( us_districts, backend=vor.RasterBackend(resolution=256), options=vor.VoronoiOptions(n_iter=30, area_cv_tol=0.1), group_by="State Name", )

Inspect Topology¶

plot_topology() overlays topology issues on the cartogram. Satellite cells are highlighted in red.

In [3]:

analysis = result.analyze_topology("State Name")

fig, axes = plt.subplots(1, 2, figsize=(20, 10), sharex=True, sharey=True)

_ = result.plot(
    "State Name", ax=axes[0], cmap="tab20", show_edges=True, alpha=0.2
)  # , labels='State Abbreviation', label_color='0.5', label_fontsize=7)
_ = plot_topology(analysis, result, ax=axes[0], title="Satellite cells")

p = vor.visualization.plot_compactness(
    result, "State Name", normalize=True, ax=axes[1], show_centroids=False, legend=False
)

plt.tight_layout()

cb = plt.colorbar(p.collections[0], ax=axes, shrink=0.5, label="Normalized inertia (relative to group mean)")

analysis = result.analyze_topology("State Name") fig, axes = plt.subplots(1, 2, figsize=(20, 10), sharex=True, sharey=True) _ = result.plot( "State Name", ax=axes[0], cmap="tab20", show_edges=True, alpha=0.2 ) # , labels='State Abbreviation', label_color='0.5', label_fontsize=7) _ = plot_topology(analysis, result, ax=axes[0], title="Satellite cells") p = vor.visualization.plot_compactness( result, "State Name", normalize=True, ax=axes[1], show_centroids=False, legend=False ) plt.tight_layout() cb = plt.colorbar(p.collections[0], ax=axes, shrink=0.5, label="Normalized inertia (relative to group mean)")

Read Topology Metrics¶

In [4]:

print(analysis)

print(analysis)

TopologyAnalysis:
  group contiguity : 16 satellite component(s)
  adjacency        : (not checked)
  orientation      : (not checked)

Proactive Topology Preservation with Adjacency Springs¶

Instead of repairing topology violations after they occur (see below), you can reduce how many violations arise in the first place using the adjacency_spring and intra_group_spring options in the backend.

Both options add a one-sided tension force between centroids during each Lloyd step: the force activates only when a pair has drifted further apart than expected, pulling them back together. When target weights are provided, the rest length for each edge is derived from the target areas of both cells (∝ √wᵢ + √wⱼ), so larger cells naturally get longer rest lengths. Without weights, a global median rest length is used.

adjacency_spring acts on pairs of centroids that are adjacent in the input geometries, regardless of group membership. It reduces adjacency violations and orientation misalignment across the whole dataset.

intra_group_spring acts only on pairs within the same group (same state, same region, etc.). When set, adjacency_spring is restricted to cross-group adjacent pairs and intra_group_spring handles same-group pairs independently. A higher value (e.g. intra_group_spring=0.5–1.0) keeps districts within the same state spatially cohesive and reduces satellite formation. Use it alongside adjacency_spring for datasets with both grouped sub-regions and cross-group adjacency constraints.

Typical values:

• adjacency_spring=0.05–0.15 — gentle nudge; reduces violations without noticeably slowing area convergence
• adjacency_spring=0.2–0.4 — stronger effect; may slow convergence slightly for highly weighted datasets
• intra_group_spring=0.5–1.0 — keeps sub-regions of each group together; set higher than adjacency_spring

Adjacency spring options can be used by themselves, or in combination with in-the-loop and post-hoc repairs (see below).

In [5]:

# In this example, we combine adjacency_spring and intra_group_spring
# with an elastic boundary with additional boundary adhesion

result_spring = vor.create_voronoi_cartogram(
    us_districts,
    backend=vor.RasterBackend(
        resolution=256,
        adjacency_spring=0.2,
        intra_group_spring=0.75,
        boundary=vor.ElasticBoundary(strength=0.05, adhesion_strength=0.1),
        area_equalizer_rate=0.1,
    ),
    options=vor.VoronoiOptions(n_iter=60, area_cv_tol=0.1),
    group_by="State Name",
)

analysis_spring = result_spring.analyze_topology("State Name")
print(f"  Discontiguous groups : {analysis_spring.n_discontiguous_groups}  (was {analysis.n_discontiguous_groups})")

# In this example, we combine adjacency_spring and intra_group_spring # with an elastic boundary with additional boundary adhesion result_spring = vor.create_voronoi_cartogram( us_districts, backend=vor.RasterBackend( resolution=256, adjacency_spring=0.2, intra_group_spring=0.75, boundary=vor.ElasticBoundary(strength=0.05, adhesion_strength=0.1), area_equalizer_rate=0.1, ), options=vor.VoronoiOptions(n_iter=60, area_cv_tol=0.1), group_by="State Name", ) analysis_spring = result_spring.analyze_topology("State Name") print(f" Discontiguous groups : {analysis_spring.n_discontiguous_groups} (was {analysis.n_discontiguous_groups})")

  Discontiguous groups : 4  (was 16)

Apply Topology Repair¶

repair_topology() runs the slot-permutation pipeline and returns a TopologyRepairReport with both the repaired cartogram and an updated TopologyAnalysis.

In [6]:

report = result.repair_topology("State Name")
result_fixed = report.cartogram

fig, axes = plt.subplots(1, 2, figsize=(20, 10))
for ax, res, _title in zip(
    axes,
    [result, result_fixed],
    ["Before repair", "After repair"],
    strict=False,
):
    res.plot(
        "State Name", ax=ax, cmap="tab20", show_edges=True, alpha=0.2, labels="State Abbreviation", label_fontsize=8
    )
    # ax.set(title=title)

report.plot(axes=axes)

plt.tight_layout();

report = result.repair_topology("State Name") result_fixed = report.cartogram fig, axes = plt.subplots(1, 2, figsize=(20, 10)) for ax, res, _title in zip( axes, [result, result_fixed], ["Before repair", "After repair"], strict=False, ): res.plot( "State Name", ax=ax, cmap="tab20", show_edges=True, alpha=0.2, labels="State Abbreviation", label_fontsize=8 ) # ax.set(title=title) report.plot(axes=axes) plt.tight_layout();

In [7]:

print(report)

print(report)

TopologyRepairReport (stages: group_contiguity, compactness):
  group contiguity : 16 → 0 satellite(s)
  adjacency        : (not checked)
  orientation      : (not checked)
  reassigned       : 95 district(s)

Automated Repair During Iteration¶

Running repair post-hoc is simple but may need additional iterations to recover. Alternatively, pass fix_topology to VoronoiOptions to repair on a schedule during the relaxation loop.

In [8]:

result_auto = vor.create_voronoi_cartogram(
    us_districts,
    backend=vor.RasterBackend(resolution=256),
    options=vor.VoronoiOptions(
        n_iter=30,
        area_cv_tol=0.1,
        fix_topology=vor.TopologyRepair(
            every=15,  # run repair every 10 iterations
            max_passes=5,  # up to 3 permutation passes per repair call
            group_contiguity=True,
            adjacency=False,
            orientation=False,
        ),
    ),
    group_by="State Name",
)

result_auto = vor.create_voronoi_cartogram( us_districts, backend=vor.RasterBackend(resolution=256), options=vor.VoronoiOptions( n_iter=30, area_cv_tol=0.1, fix_topology=vor.TopologyRepair( every=15, # run repair every 10 iterations max_passes=5, # up to 3 permutation passes per repair call group_contiguity=True, adjacency=False, orientation=False, ), ), group_by="State Name", )

In [9]:

print("Topology analysis for in-the-loop repairs.\n")
print(result_auto.analyze_topology("State Name"))

print("\nResult after additional final repair.\n")
report_auto = result_auto.repair_topology("State Name")
print(report_auto)

print("Topology analysis for in-the-loop repairs.\n") print(result_auto.analyze_topology("State Name")) print("\nResult after additional final repair.\n") report_auto = result_auto.repair_topology("State Name") print(report_auto)

Topology analysis for in-the-loop repairs.

TopologyAnalysis:
  group contiguity : OK
  adjacency        : (not checked)
  orientation      : (not checked)

Result after additional final repair.

TopologyRepairReport (stages: group_contiguity, compactness):
  group contiguity : OK
  adjacency        : (not checked)
  orientation      : (not checked)
  reassigned       : 6 district(s)

Topology Repair Without Grouping¶

Adjacency and orientation repair work on any dataset — no group_by is required. Here we use US States (a flat dataset with no sub-region grouping). analyze_topology() without group_by skips the satellite-cell check and reports only adjacency violations and orientation misalignment.

Note: Post-hoc repair_topology() permutes existing cell geometries without rerunning Voronoi. When weights are non-uniform, a swap permanently assigns a district to a cell sized for a different district, breaking the proportional area relationship. For weighted cartograms, prefer in-loop topology repair via VoronoiOptions(fix_topology=...). The example below uses an unweighted cartogram for this reason.

In [10]:

us_states = examples.load_us_census(population=True)
result_states = vor.create_voronoi_cartogram(
    us_states,
    backend=vor.RasterBackend(resolution=300),
    options=vor.VoronoiOptions(n_iter=30, area_cv_tol=0.1),
)

us_states = examples.load_us_census(population=True) result_states = vor.create_voronoi_cartogram( us_states, backend=vor.RasterBackend(resolution=300), options=vor.VoronoiOptions(n_iter=30, area_cv_tol=0.1), )

In [11]:

analysis_states = result_states.analyze_topology()  # no group_by → checks adjacency and orientation

fig, ax = plt.subplots(figsize=(10, 6))
result_states.plot(ax=ax, show_edges=True, labels="State Abbreviation", alpha=0.5)
plot_topology(analysis_states, result_states, ax=ax, title="Before repair — adjacency and orientation issues")
ax.axis("off")
plt.tight_layout()

print(analysis_states)

analysis_states = result_states.analyze_topology() # no group_by → checks adjacency and orientation fig, ax = plt.subplots(figsize=(10, 6)) result_states.plot(ax=ax, show_edges=True, labels="State Abbreviation", alpha=0.5) plot_topology(analysis_states, result_states, ax=ax, title="Before repair — adjacency and orientation issues") ax.axis("off") plt.tight_layout() print(analysis_states)

TopologyAnalysis:
  group contiguity : OK
  adjacency        : 36 / 109 pairs violated  (67.0% satisfied)
  orientation      : 5 misaligned pair(s)  mean cosine=0.754

In [12]:

report_states = result_states.repair_topology()
report_states

report_states = result_states.repair_topology() report_states

Out[12]:

TopologyRepairReport (stages: adjacency, orientation):
  group contiguity : OK
  adjacency        : 36 → 26 violated pair(s)
  orientation      : 5 → 1 misaligned pair(s)
  reassigned       : 17 district(s)

In [13]:

report_states.plot(title="US States — adjacency and orientation repair")
plt.tight_layout()

report_states.plot(title="US States — adjacency and orientation repair") plt.tight_layout()

See Also¶

• Explanation: Contiguity Repair — slot-permutation algorithm, articulation-point guard, generator relocation
• Inspect and Improve Convergence — plot_displacement details
• Reference: Result — TopologyAnalysis, TopologyRepairReport
• Reference: Backends — adjacency_spring

In [ ]: