carto_flow.flow_cartogram.displacement¶

Displacement computation utilities for flow-based cartography.

This module provides functions for applying displacement fields to geometric objects, including polygon displacement with bilinear interpolation and displacement field upsampling. These utilities are essential for the iterative deformation process in flow-based cartogram algorithms.

Functions:

displace_coords –

Basic coordinate displacement with bilinear interpolation.
displace_coords_numba –

Optimized Numba-compiled version for uniform grids.
apply_displacement_to_polygons_vectorized –

Vectorized polygon displacement.
upsample_displacement –

Upsample displacement fields to higher resolution.

Examples:

>>> from carto_flow.flow_cartogram.displacement import displace_coords
>>> from carto_flow.flow_cartogram.grid import Grid
>>> import numpy as np
>>> grid = Grid.from_bounds((0, 0, 100, 80), size=100)
>>> coords = np.array([[10, 20], [30, 40], [50, 60]])
>>> displaced_coords = displace_coords(coords, grid, vx, vy, dt=0.1)

apply_displacement_to_polygons_vectorized ¶

apply_displacement_to_polygons_vectorized(
    polygons: list[Polygon | MultiPolygon],
    vx: ndarray,
    vy: ndarray,
    grid: Grid,
    dt: float,
) -> list[Polygon | MultiPolygon]

Apply vectorized displacement to polygon geometries using velocity field interpolation.

This function efficiently displaces multiple polygon geometries by interpolating velocity values from a regular grid and applying the displacement over a time step. The algorithm handles both individual polygons and multi-polygons while preserving their topological structure.

The displacement process: 1. Flattening: Convert all polygons to individual Polygon objects 2. Coordinate extraction: Collect all vertex coordinates into single array 3. Grid indexing: Find grid cell indices for each coordinate using binary search 4. Bilinear interpolation: Interpolate velocity values at exact coordinate locations 5. Displacement application: Apply velocity * dt to each coordinate 6. Reconstruction: Rebuild polygons maintaining MultiPolygon structure

Parameters:

polygons (List[Union[Polygon, MultiPolygon]]) –

List of shapely polygon geometries to displace. Can contain both individual Polygon and MultiPolygon objects.
vx (ndarray) –

X-component of velocity field with shape (ny, nx) matching grid dimensions. Represents horizontal flow velocities at grid cell centers.
vy (ndarray) –

Y-component of velocity field with shape (ny, nx) matching grid dimensions. Represents vertical flow velocities at grid cell centers.
grid (Grid) –

Grid information containing coordinate arrays and spatial discretization. Must provide x_coords, y_coords arrays for interpolation.
dt (float) –

Time step for displacement integration. Controls the magnitude of displacement applied to polygon vertices.

Returns:

displaced_polygons ( List[Union[Polygon, MultiPolygon]] ) –

List of displaced polygon geometries with same structure as input. Individual Polygons remain as Polygons, MultiPolygons are reconstructed from their constituent displaced Polygon components.

Notes

Performance characteristics: - Vectorized operations: O(n) complexity for n polygon vertices - Binary search indexing: O(log n) per coordinate for grid lookup - Bilinear interpolation: Smooth velocity field approximation - Memory efficient: Processes all coordinates in single vectorized operations

Boundary handling: - Clips grid indices to valid range to handle edge cases - Preserves polygon topology and MultiPolygon structure - Maintains coordinate ordering for proper polygon reconstruction

Use cases: - Flow-based cartography for dynamic shape deformation - Physics-based animation of polygon boundaries - Time integration of velocity fields on geometric objects

Examples:

>>> from shapely.geometry import Polygon
>>> import numpy as np
>>> from carto_flow.displacement import apply_displacement_to_polygons_vectorized
>>> from carto_flow.grid import Grid
>>>
>>> # Create sample polygons
>>> poly1 = Polygon([(0, 0), (1, 0), (1, 1), (0, 1)])
>>> poly2 = Polygon([(2, 0), (3, 0), (3, 1), (2, 1)])
>>> polygons = [poly1, poly2]
>>>
>>> # Set up velocity field (rightward flow)
>>> bounds = (0, 0, 4, 2)
>>> grid = Grid.from_bounds(bounds, size=20)
>>> vx = np.ones((grid.sy, grid.sx)) * 0.1  # Rightward velocity
>>> vy = np.zeros((grid.sy, grid.sx))       # No vertical velocity
>>>
>>> # Apply displacement
>>> dt = 1.0
>>> displaced = apply_displacement_to_polygons_vectorized(
...     polygons, vx, vy, grid, dt
... )
>>>
>>> # Polygons have moved right by 0.1 units
>>> print(f"Original: {polygons[0]}")
>>> print(f"Displaced: {displaced[0]}")

displace_coords ¶

displace_coords(
    coords: ndarray,
    grid: Grid,
    vx: ndarray,
    vy: ndarray,
    dt: float,
) -> np.ndarray

Displace coordinates using bilinear interpolation of velocity field.

Parameters:

coords (ndarray) –

Array of shape (n, 2) containing [x, y] coordinates to displace
grid (Grid) –

Grid information containing coordinate arrays and spatial discretization
vx (ndarray) –

Velocity field components with shape (ny, nx) matching grid dimensions
vy (ndarray) –

Velocity field components with shape (ny, nx) matching grid dimensions
dt (float) –

Time step for displacement integration

Returns:

coords ( ndarray ) –

Displaced coordinates with same shape as input

displace_coords_numba ¶

displace_coords_numba(
    coords: ndarray,
    x_coords: ndarray,
    y_coords: ndarray,
    vx: ndarray,
    vy: ndarray,
    dt: float,
    dx: float,
    dy: float,
) -> np.ndarray

Numba-optimized version with parallel execution for uniform grids dx, dy: constant grid spacing

upsample_displacement ¶

upsample_displacement(
    u_field: ndarray,
    v_field: ndarray,
    new_shape: tuple[int, int],
    order: int = 3,
    sigma_smooth: float = 0.6,
) -> tuple[np.ndarray, np.ndarray]

Upsample a displacement field (u, v) to a higher-resolution grid.

The displacement fields are defined on a regular grid, representing the displacement of each grid cell center in x and y directions. When moving to a higher resolution, we upsample smoothly using spline interpolation and optional Gaussian smoothing to avoid high-frequency artifacts.

Parameters:

u_field (ndarray) –

2D displacement arrays (shape: [ny, nx]).
v_field (ndarray) –

2D displacement arrays (shape: [ny, nx]).
new_shape (tuple[int, int]) –

Target shape (ny_new, nx_new).
order (int, default: 3 ) –

Spline interpolation order (0=nearest, 1=linear, 3=cubic).
sigma_smooth (float, default: 0.6 ) –

Standard deviation for optional Gaussian smoothing applied after interpolation (in pixels). Set to 0 to disable.

Returns:

(u_up, v_up) : tuple[np.ndarray, np.ndarray] –

Upsampled displacement fields matching the target resolution.