carto_flow.voronoi_cartogram.geodesic

Geodesic (topology-respecting) Voronoi labeling via multi-source BFS.

Replaces Euclidean nearest-neighbor assignment when geodesic_voronoi=True. The BFS wavefront propagates only through active (land) pixels, so it cannot cross water bodies or other inactive regions — eliminating cross-bay assignments that arise from straight-line distance.

Time complexity: O(n_active_pixels) — comparable to cKDTree labeling.

When the active region has multiple disconnected components (e.g. from elastic boundary deformation creating isolated pockets), each component is seeded dynamically via the unseeded-component fix: the nearest centroid to each component's center-of-mass is used as the seed label.

Functions:

• geodesic_label_active –

  Snap centroids to nearest active pixel, run BFS, return flat labels.

geodesic_label_active

geodesic_label_active(
    points: ndarray,
    gx_active: ndarray,
    gy_active: ndarray,
    active_mask_flat: ndarray,
    grid_nx: int,
    grid_ny: int,
    return_debug: bool = False,
    grid_x_coords: ndarray | None = None,
    grid_y_coords: ndarray | None = None,
) -> np.ndarray | tuple[np.ndarray, dict]

Snap centroids to nearest active pixel, run BFS, return flat labels.

Parameters:

• points ((G, 2) float) –

  Centroid world coordinates.

• gx_active ((m,) float) –

  World coordinates of active pixels (same order as the active mask).

• gy_active ((m,) float) –

  World coordinates of active pixels (same order as the active mask).

• active_mask_flat ((grid_nx * grid_ny,) bool) –

  Flat active-pixel mask for the full grid.

• grid_nx (int) –

  Grid dimensions.

• grid_ny (int) –

  Grid dimensions.

• return_debug (bool, default: False ) –

  When True, also return a diagnostic dict that reports any centroid whose BFS seed was placed in a different connected component of the active grid than the component the centroid is closest to. This detects the "cross-water labeling" failure mode where Euclidean seed snapping puts a seed in a topologically disconnected region.

  The dict contains:

  seed_rows, seed_cols : (n_seeds,) int32 Grid coordinates of the placed seeds. seed_components : (n_seeds,) int32 Connected-component id for each seed. centroid_components : (G,) int32 Component id of the nearest active pixel to each original centroid. misplaced_mask : (G,) bool True for centroids whose seed is in a different component. n_misplaced : int Number of misplaced seeds. comp_2d : (ny, nx) int32 Full component label grid (useful for visualization). unseeded_comp_ids : (k,) int32 Component IDs (1-based, scipy convention) that had no seed before the fix was applied. Non-empty means the fix fired this call. n_unseeded : int Number of unseeded components. unseeded_pixel_mask : (ny, nx) bool Active pixels that belonged to unseeded components (for overlay). seed_centroid_distances : (G,) float Euclidean distance from each centroid to its seed world position. Values >> grid_dx indicate possible within-component misplacements (seed placed on the far side of a bay).

• grid_x_coords ((nx,) and (ny,) float or None, default: None ) –

  World coordinates of the grid columns/rows. When provided, they are used to compute seed_centroid_distances in the debug dict.

• grid_y_coords ((nx,) and (ny,) float or None, default: None ) –

  World coordinates of the grid columns/rows. When provided, they are used to compute seed_centroid_distances in the debug dict.

Returns:

• labels ( (m,) intp ) –

  Centroid index for each active pixel. If return_debug=True, returns (labels, debug_dict) instead.