packing

tissue_simulator.packing

Sphere packing algorithm for cell placement.

SpatialHashGrid

SpatialHashGrid(cell_size: float)

Uniform hash grid over cell centers for short-range neighbor queries.

Space is divided into cubic buckets of side cell_size. A query returns every index stored within reach buckets of the query point, which is a superset of all stored points closer than reach * cell_size.

Source code in tissue_simulator/packing.py

def __init__(self, cell_size: float):
    if not cell_size > 0:
        raise ValueError(f"cell_size must be positive, got {cell_size!r}")
    self.cell_size = float(cell_size)
    self._buckets: Dict[Tuple[int, int, int], List[int]] = defaultdict(list)

key

key(point) -> Tuple[int, int, int]

Bucket key of a 3D point.

Source code in tissue_simulator/packing.py

def key(self, point) -> Tuple[int, int, int]:
    """Bucket key of a 3D point."""
    s = self.cell_size
    return (math.floor(point[0] / s), math.floor(point[1] / s),
            math.floor(point[2] / s))

insert

insert(index: int, point) -> None

Store index at point.

Source code in tissue_simulator/packing.py

def insert(self, index: int, point) -> None:
    """Store ``index`` at ``point``."""
    self._buckets[self.key(point)].append(index)

remove

remove(index: int, point) -> None

Remove index previously inserted at point.

Source code in tissue_simulator/packing.py

def remove(self, index: int, point) -> None:
    """Remove ``index`` previously inserted at ``point``."""
    self._buckets[self.key(point)].remove(index)

move

move(index: int, old_point, new_point) -> None

Re-bucket index after its point moved.

Source code in tissue_simulator/packing.py

def move(self, index: int, old_point, new_point) -> None:
    """Re-bucket ``index`` after its point moved."""
    old_key, new_key = self.key(old_point), self.key(new_point)
    if old_key != new_key:
        self._buckets[old_key].remove(index)
        self._buckets[new_key].append(index)

neighbors

neighbors(point, reach: int = 1) -> Iterator[int]

Yield indices stored within reach buckets of point.

Source code in tissue_simulator/packing.py

def neighbors(self, point, reach: int = 1) -> Iterator[int]:
    """Yield indices stored within ``reach`` buckets of ``point``."""
    kx, ky, kz = self.key(point)
    buckets = self._buckets
    for i in range(kx - reach, kx + reach + 1):
        for j in range(ky - reach, ky + reach + 1):
            for k in range(kz - reach, kz + reach + 1):
                bucket = buckets.get((i, j, k))
                if bucket:
                    yield from bucket

SpherePacker

SpherePacker(bounds: Tuple[float, float, float], cell_radii_config: Dict[str, Tuple[float, float]], min_spacing: float = 0.5, allow_boundary_cells: bool = True, seed: Optional[int] = None)

Random sphere packing algorithm for placing cells in tissue.

Initialize sphere packer.

Parameters:

Name	Type	Description	Default
bounds	Tuple[float, float, float]	(height, width, thickness) of tissue	required
cell_radii_config	Dict[str, Tuple[float, float]]	Dict mapping cell types to (min, max) radii	required
min_spacing	float	Minimum spacing between cell surfaces	0.5
allow_boundary_cells	bool	Allow cells extending beyond bounds	True
seed	Optional[int]	Optional integer seed for the instance RNG. When provided, the packing process is deterministic; when None the RNG is seeded from system entropy (previous default behavior).	None

Source code in tissue_simulator/packing.py

def __init__(self, bounds: Tuple[float, float, float],
             cell_radii_config: Dict[str, Tuple[float, float]],
             min_spacing: float = 0.5,
             allow_boundary_cells: bool = True,
             seed: Optional[int] = None):
    """
    Initialize sphere packer.

    Args:
        bounds: (height, width, thickness) of tissue
        cell_radii_config: Dict mapping cell types to (min, max) radii
        min_spacing: Minimum spacing between cell surfaces
        allow_boundary_cells: Allow cells extending beyond bounds
        seed: Optional integer seed for the instance RNG. When provided,
            the packing process is deterministic; when None the RNG is
            seeded from system entropy (previous default behavior).
    """
    self.bounds = bounds
    self.cell_radii_config = cell_radii_config
    self.min_spacing = min_spacing
    self.allow_boundary_cells = allow_boundary_cells
    self.seed = seed
    self._rng = np.random.default_rng(seed)

pack

pack(max_attempts: int = 1000) -> List[Cell]

Pack cells into tissue using random placement.

Parameters:

Name	Type	Description	Default
max_attempts	int	Maximum placement attempts before stopping	1000

Returns:

Type	Description
List[Cell]	List of successfully placed Cell objects

Source code in tissue_simulator/packing.py

def pack(self, max_attempts: int = 1000) -> List[Cell]:
    """
    Pack cells into tissue using random placement.

    Args:
        max_attempts: Maximum placement attempts before stopping

    Returns:
        List of successfully placed Cell objects
    """
    return self._pack(max_attempts)

pack_with_progress

pack_with_progress(max_attempts: int = 1000, callback=None) -> List[Cell]

Pack cells with progress callback for GUI updates.

Parameters:

Name	Type	Description	Default
max_attempts	int	Maximum placement attempts before stopping	1000
callback		Function called with (cells_placed, total_attempts)	None

Returns:

Type	Description
List[Cell]	List of successfully placed Cell objects

Source code in tissue_simulator/packing.py

def pack_with_progress(self, max_attempts: int = 1000,
                      callback=None) -> List[Cell]:
    """
    Pack cells with progress callback for GUI updates.

    Args:
        max_attempts: Maximum placement attempts before stopping
        callback: Function called with (cells_placed, total_attempts)

    Returns:
        List of successfully placed Cell objects
    """
    return self._pack(max_attempts, callback)

PackingReport dataclass

PackingReport(n_target: int, n_placed: int, n_rsa: int, n_inserted: int, n_relaxed: int, relaxation_iterations: int, max_displacement: float, overlap_fraction: float, target_overlap_fraction: float, saturated_bins: int, bin_size: float, bin_targets: ndarray, bin_achieved: ndarray)

Diagnostics of one :class:InhomogeneousPacker run.

Attributes:

Name	Type	Description
n_target	int	Cells requested by the layout.
n_placed	int	Cells placed (always n_target).
n_rsa	int	Cells placed by hard-core random sequential addition.
n_inserted	int	Cells inserted into saturated bins at best clearance.
n_relaxed	int	Cells moved by overlap relaxation.
relaxation_iterations	int	Relaxation sweeps performed.
max_displacement	float	Largest relaxation displacement in µm.
overlap_fraction	float	Fraction of cells whose nearest neighbor is closer than the hard core kappa * (r_i + r_j) after packing.
target_overlap_fraction	float	The same fraction in the source region.
saturated_bins	int	Bins where addition stalled.
bin_size	float	Bin side in µm.
bin_targets	ndarray	Cell quota per bin, shape (rows, cols).
bin_achieved	ndarray	Cells per bin after packing.

bin_correlation property

bin_correlation: float

Pearson correlation of achieved against target cells per bin.

InhomogeneousPacker

InhomogeneousPacker(bounds: Tuple[float, float, float], layout: Layout, allow_boundary_cells: bool = True, seed=None, bin_size: Optional[float] = None, max_failures: int = 100, insertion_candidates: int = 20, max_relax_iterations: int = 100, displacement_cap: Optional[float] = None, placeholder_type: str = 'default')

Pack cells so that local density follows a :class:~tissue_simulator.density.Layout.

1. The window is split into square bins; each bin's quota is proportional to the layout intensity it covers (largest-remainder rounding).
2. One ticket per quota cell is shuffled and filled by random sequential addition inside its bin, with radii from the layout's density-conditioned marks and hard core kappa * (r_i + r_j). A bin that rejects max_failures consecutive candidates is saturated.
3. Tickets left over in saturated bins are inserted at the best-clearance position of insertion_candidates draws, then overlaps in those bins and a one-bin halo are relaxed by soft-sphere pushes. No cell moves more than displacement_cap from where it was placed, and relaxation stops once the overlap fraction reaches the source region's.

The z coordinate is uniform through the thickness; use a thin slab (thickness below one cell diameter) to mirror a 2D source region.

Parameters:

Name	Type	Description	Default
bounds	Tuple[float, float, float]	(height, width, thickness) of the tissue; height and width must match the layout window.	required
layout	Layout	Target maps from :meth:DensityModel.sample_layout.	required
allow_boundary_cells	bool	Allow cells extending beyond the x/y bounds.	True
seed		Integer seed, SeedSequence or Generator for the packer RNG.	None
bin_size	Optional[float]	Quota bin side in µm; defaults to max(bandwidth / 2, 10) rounded to the layout grid.	None
max_failures	int	Consecutive rejections before a bin is saturated.	100
insertion_candidates	int	Positions tried per insertion.	20
max_relax_iterations	int	Cap on relaxation sweeps.	100
displacement_cap	Optional[float]	Largest relaxation move in µm; defaults to half the median radius.	None
placeholder_type	str	Cell type given to placed cells (labels are normally assigned afterwards).	'default'

Source code in tissue_simulator/packing.py

def __init__(self, bounds: Tuple[float, float, float], layout: Layout,
             allow_boundary_cells: bool = True,
             seed=None,
             bin_size: Optional[float] = None,
             max_failures: int = 100,
             insertion_candidates: int = 20,
             max_relax_iterations: int = 100,
             displacement_cap: Optional[float] = None,
             placeholder_type: str = "default"):
    """
    Args:
        bounds: (height, width, thickness) of the tissue; height and width
            must match the layout window.
        layout: Target maps from :meth:`DensityModel.sample_layout`.
        allow_boundary_cells: Allow cells extending beyond the x/y bounds.
        seed: Integer seed, SeedSequence or Generator for the packer RNG.
        bin_size: Quota bin side in µm; defaults to
            ``max(bandwidth / 2, 10)`` rounded to the layout grid.
        max_failures: Consecutive rejections before a bin is saturated.
        insertion_candidates: Positions tried per insertion.
        max_relax_iterations: Cap on relaxation sweeps.
        displacement_cap: Largest relaxation move in µm; defaults to half
            the median radius.
        placeholder_type: Cell type given to placed cells (labels are
            normally assigned afterwards).
    """
    height, width, _ = bounds
    if abs(width - layout.width) > 1e-6 or abs(height - layout.height) > 1e-6:
        raise ValueError(
            f"bounds {bounds!r} do not match the layout window "
            f"({layout.height}, {layout.width}).")
    self.bounds = tuple(float(b) for b in bounds)
    self.layout = layout
    self.allow_boundary_cells = allow_boundary_cells
    self.max_failures = int(max_failures)
    self.insertion_candidates = max(1, int(insertion_candidates))
    self.max_relax_iterations = int(max_relax_iterations)
    self.displacement_cap = (0.5 * layout.marks.median_radius
                             if displacement_cap is None else float(displacement_cap))
    self.placeholder_type = placeholder_type
    if bin_size is None:
        bin_size = max(0.5 * (layout.bandwidth or 20.0), 10.0)
    self.bin_pixels = max(1, int(round(bin_size / layout.grid_step)))
    self.bin_size = self.bin_pixels * layout.grid_step
    self._rng = np.random.default_rng(seed)
    self.report: Optional[PackingReport] = None

pack

pack() -> List[Cell]

Place layout.n_target cells and store a :class:PackingReport.

Source code in tissue_simulator/packing.py

def pack(self) -> List[Cell]:
    """Place ``layout.n_target`` cells and store a :class:`PackingReport`."""
    layout = self.layout
    r_max = max(float(r.max()) for r in layout.marks.radii_by_bin)
    self._grid = SpatialHashGrid(max(2.0 * layout.kappa * r_max, 1e-6))
    self._xs, self._ys, self._zs, self._rs = [], [], [], []

    quotas = self._bin_quotas()
    self._rows, self._cols = quotas.shape
    self._pixel_cache = {}
    tickets = np.repeat(np.arange(quotas.size), quotas.ravel())
    self._rng.shuffle(tickets)

    saturated = np.zeros(quotas.size, dtype=bool)
    deficit = []
    for b in tickets:
        if saturated[b] or not self._place_by_addition(b):
            saturated[b] = True
            deficit.append(b)
    n_rsa = len(self._xs)
    for b in deficit:
        self._insert_at_best_clearance(b)
    n_relaxed, iterations, max_displacement = (
        self._relax(set(deficit)) if deficit else (0, 0, 0.0))

    achieved = np.zeros(quotas.size, dtype=int)
    for x, y in zip(self._xs, self._ys):
        achieved[self._bin_of(x, y)] += 1

    self.report = PackingReport(
        n_target=int(layout.n_target), n_placed=len(self._xs), n_rsa=n_rsa,
        n_inserted=len(deficit), n_relaxed=n_relaxed,
        relaxation_iterations=iterations, max_displacement=float(max_displacement),
        overlap_fraction=self._overlap_fraction(),
        target_overlap_fraction=float(layout.target_overlap_fraction),
        saturated_bins=int(saturated.sum()), bin_size=self.bin_size,
        bin_targets=quotas, bin_achieved=achieved.reshape(quotas.shape),
    )

    cells = []
    for x, y, z, r in zip(self._xs, self._ys, self._zs, self._rs):
        cell = Cell(center=(x, y, z), radius=r, cell_type=self.placeholder_type)
        cell.is_boundary = not cell.is_within_bounds(self.bounds)
        cells.append(cell)
    return cells