circlepack#

Implements a fast, dependency-free algorithm for packing circles with prescribed tangencies. Used internally in KnotPy for layout of graph structures.

Functions

acxyz(x, y, z)

Angle at x between y and z using circle geometry.

circle_pack(internal, external)

Compute a circle packing layout given prescribed tangencies.

flower(radius, center, cycle)

Sum of angles at center formed with its neighboring cycle.

invert_around(packing, k[, smallCircles])

Invert packing so that circle k surrounds the others.

invert_packing(packing, center)

Invert all circles in the packing around a given complex point.

normalize_packing(packing[, k, target])

Normalize the packing so that a given circle has radius target.

place(placements, radii, internal, center)

Recursively place neighbors of a given center based on geometry.

test_grid(packing, k, z, r, q, g)

Yield candidate centers and their resulting smallest radius after inversion and normalization.
circle_pack(internal, external)#

Compute a circle packing layout given prescribed tangencies.

Internal circles are surrounded by a cycle of other circles; external circles have fixed radii.

Parameters:

  • internal (dict[str, list[str]]) – Mapping of internal keys to cyclic list of neighbor keys.

  • external (dict[str, float]) – Mapping of external keys to fixed radii.

Returns:

A dictionary mapping each key to a (center, radius) pair.

Raises:

ValueError – If keys are not disjoint or external radii are non-positive.

Return type:

dict[str, tuple[complex, float]]

Example

>>> internal = {'A': ['B', 'C', 'D']}
>>> external = {'B': 1.0, 'C': 1.0, 'D': 1.0}
>>> packing = circle_pack(internal, external)
>>> len(packing)
4
invert_packing(packing, center)#

Invert all circles in the packing around a given complex point.

Parameters:

  • packing (dict[str, tuple[complex, float]]) – Dictionary mapping keys to (center, radius) pairs.

  • center (complex) – Complex point to invert around.

Returns:

A new packing where all circles are inverted.

Return type:

dict[str, tuple[complex, float]]

Example

>>> inverted = invert_packing(packing, 0j)
normalize_packing(packing, k=None, target=1.0)#

Normalize the packing so that a given circle has radius target.

Parameters:

  • packing (dict[str, tuple[complex, float]]) – Mapping from keys to (center, radius).

  • k (str) – Optional key of the circle to normalize. If None, uses the smallest.

  • target (float) – Desired radius for the selected circle.

Returns:

New packing with all circles scaled accordingly.

Return type:

dict[str, tuple[complex, float]]

invert_around(packing, k, smallCircles=None)#

Invert packing so that circle k surrounds the others.

This finds a Möbius transform (via inversion) that places circle k large enough to contain the others, based on a grid search.

Parameters:

  • packing (dict[str, tuple[complex, float]]) – The circle packing to invert.

  • k (str) – Key of the desired outer circle.

  • smallCircles (list[str] | None) – Optional list of keys to consider in optimization.

Returns:

A new packing with optimized inversion.

Return type:

dict[str, tuple[complex, float]]