Skip to content

carto_flow.voronoi_cartogram.contiguity

Group-contiguity repair for Voronoi cartogram results.

Functions:

make_groups_contiguous 

make_groups_contiguous(
    gdf: GeoDataFrame,
    group_by: str,
    *,
    max_passes: int = 20,
    show_progress: bool = False,
    debug: bool = False,
) -> tuple[gpd.GeoDataFrame, list[tuple[Any, list[int]]]]

Permute rows of gdf so that each group forms a contiguous Voronoi region.

After lloyd relaxation, rows belonging to the same group (e.g. congressional districts within a state) may occupy non-adjacent Voronoi slots. This function permutes the row-to-slot mapping — without moving any cell geometry — so that each group's slots form a connected subgraph of the Voronoi adjacency graph.

The returned GeoDataFrame has the same rows as gdf but reordered: result.iloc[i] is the row that should be placed at slot i (i.e. the geometry at gdf.geometry.iloc[i] is now owned by a potentially different original row).

Algorithm
  1. Build a slot-adjacency graph from gdf.geometry using :func:carto_flow.geo_utils.adjacency.find_adjacent_pairs.
  2. Maintain a permutation slot_of[d] (district → slot) and its inverse dist_at[s] (slot → district).
  3. Repeat up to max_passes times:

a. For each multi-district group, find connected components of its current slots (BFS restricted to that group's slots). b. For each satellite component (all but the largest), BFS through other-group slots to find the shortest path to the main body. Slots that changed hands earlier in the same pass are forbidden, preventing within-pass oscillation. c. Walk the path: swap each intermediate district with the one moving forward along the path. Before each swap, check that the swap would not disconnect the displaced district's group (articulation-point check). If it would, skip this path. d. Stop when all groups are contiguous or no swaps were made in a pass.

Parameters:

  • gdf (GeoDataFrame) –

    GeoDataFrame whose geometry column contains the Voronoi cells (one cell per row). All other columns are carried along unchanged.

  • group_by (str) –

    Column in gdf that identifies which group each row belongs to.

  • max_passes (int, default: 20 ) –

    Maximum number of repair passes (default 20).

  • show_progress (bool, default: False ) –

    If True, print a summary of discontiguous groups before the first pass and a status line after each pass.

  • debug (bool, default: False ) –

    If True, print one line per satellite repair attempt showing the group, satellite slots, and outcome (SWAPPED / REJECTED / NO PATH).

Returns:

  • GeoDataFrame –

    Copy of gdf with only the geometry column permuted. Row i of the result keeps all original attribute values but is assigned the Voronoi cell geometry that was determined to belong to it.

  • list[tuple[Any, list[int]]] –

    One entry per remaining satellite component: (group_id, row_indices) where group_id is the value from the group_by column and row_indices is the sorted list of original gdf row indices belonging to that satellite. The main body of each group is excluded. Empty when fully converged.