Packing¶

Arranging shapes on a page without letting any of them touch — what a collage of neurons needs, and the kind of thing that is easy to write in numpy and slow to run.

Three primitives, meant to be used together:

masks = fastcore.rasterize_segments(coords, edges, scale=40, pad=1)
positions, variant, grid = fastcore.pack_masks(
    masks, page_shape=(1300, 980)
)

rasterize_segments turns line work — a skeleton's node-to-parent edges, a mesh's face edges — into binary masks. pack_masks lays those out so that no two share a pixel. pack_rectangles is the cheaper bounding-box alternative, useful on its own or as a starting point for the mask packing.

Packing shapes, not boxes¶

A bounding box is mostly empty for anything branching, so packing boxes wastes most of the page. Packing the shapes themselves lets one reach into another's empty space — even sit inside a loop of it — as long as no cable actually meets:

ring = np.zeros((9, 9), dtype=bool)
ring[0, :] = ring[-1, :] = ring[:, 0] = ring[:, -1] = True
small = np.ones((3, 3), dtype=bool)

fastcore.pack_masks([[ring], [small]], (9, 9))[0]     # -> [[0, 0], [1, 1]]
fastcore.pack_rectangles([[9, 9], [3, 3]], (9, 9))[0] # -> None, no room

Why this is not a cross correlation¶

The obvious way to test every position of a mask against the page at once is a correlation: fftconvolve(page, mask[::-1, ::-1], mode="valid") gives the number of shared pixels at each of the ~1.3M positions of a 1300x980 page, and the free ones are the zeros. One vectorised call — which is why it is what you write in numpy.

It is also the wrong computation. It produces an exact overlap count at every position, in floating point, when the question is boolean and the answer is wanted at exactly one position: the best one. Measured on 200 synthetic arbors at 100 px per page unit, on a 1300x980 page:

The correlation is about 70% of the layout, and it grows as O(N² res²) — doubling the resolution quadruples it. What replaces it:

• Positions are visited in the order you score them. Both cost models — bottom-up, and a cost surface — define a total order on positions that does not depend on the shape, so the best free position is the first free one in that order. The scan stops there. A correlation cannot stop early; that is the whole difference.
• Collisions are bit operations. A page row is u64 words, a mask row is u64 words, and the test is an AND — 64 pixels per instruction, no allocation, and a page small enough to stay in cache (160 kB packed against 1.3 MB as bytes).
• The densest rows are tried first. A position that collides usually collides on the shape's heaviest row, so most rejections cost one or two words.
• Provably empty space is skipped. Everything above the highest occupied row is free, so a bottom-up scan is bounded by the fill line rather than by the page.
• The search runs on every core, and so do the variants of a shape against each other. Placement itself does not, and cannot: each shape goes down against the page the one before it left behind, which is what the packing means.

Rasterising is the same story on a smaller scale. Interpolating every edge and scattering the result materialises one element per pixel-step of every edge: on a mesh with 300k edges averaging five pixels each that is a 1.5M-element index array, plus the same again for the parameter and both coordinates, to set a few tens of thousands of distinct pixels. Here the walk writes straight into the mask — on every core at once for a shape with enough edges to be worth splitting, so that one outsized mesh in a neuron list does not set the pace for all of it.

Cost surfaces and masks¶

By default shapes go as far down, and then as far left, as they will go, which fills a rectangle neatly. Pass cost to say what a good position is instead — each shape lands where the surface is lowest under its centre:

rows, cols = np.ogrid[0:height, 0:width]
cost = np.hypot(rows - height / 2, cols - width / 2)   # fill from the middle outwards

To confine shapes to a silhouette, mark everything outside it as already taken and hand that in as grid. Combining the two — a grid that blocks the outside and a cost that grows from the middle of the shape — is what fills an arbitrary outline, since bottom-up would pile everything into the bottom of it.

grid also serves the two-pass case: pack one set of shapes, then hand the page back to squeeze a second set into whatever room is left.

Reference¶

    The two in-plane coordinates of each shape, in whatever units. A
    single array is taken as a single shape.

    Index pairs into the matching ``coords``. Vertices that no edge
    names are ignored - but if a shape has no edges at all, every one
    of its vertices is marked, so a bare point cloud still rasterises.

    Pixels per coordinate unit.

    Margin left around the shape, in pixels, and the radius the result
    is dilated by. Two masks that do not overlap then leave ``2 * pad``
    pixels of clear space between the lines themselves.

    Fill the interior afterwards - what a solid shape wants, since what
    it occupies is its silhouette rather than the wireframe of its
    edges. Unlike ``scale`` and ``pad``, which describe the page and so
    are necessarily shared, this describes the shape: pass one flag per
    shape to rasterise a mix of solid and wireframe in one call.

    Quarter turns counter-clockwise to apply before rasterising, taken
    mod 4 - ``1`` is ``(u, v) -> (-v, u)``. All four are offered because
    a caller whose own axes are mirrored needs the other handedness:
    composed with a flipped axis, a counter-clockwise turn *is* the
    clockwise one. Turning here rather than rotating the coordinates
    first saves a copy of them, which for a large mesh is the biggest
    array in play.

    Number of threads to use. `None` (default) uses all cores.

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> coords = np.array([[0., 0.], [4., 4.]])
>>> edges = np.array([[0, 1]])
>>> mask = fastcore.rasterize_segments(coords, edges)
>>> mask.astype(int)
array([[1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1]])

        One entry per item. An entry may be a single mask, or a list of
        the variants to try for that item - i.e. upright and, if
        rotation is allowed, turned a quarter turn. The two forms mix
        freely, so the output of
        :func:`~navis_fastcore.rasterize_segments` can be handed
        straight over. An item with no usable variant counts as one
        that did not fit.

        Page size in pixels.

        A page that is already partly occupied, e.g. one holding an
        earlier set of shapes, or one with everything outside some
        silhouette marked as taken. Defaults to an empty page.

        What counts as the "best" position: each mask goes where this
        is lowest under its centre. Defaults to as far down, and then
        as far left, as the mask will go - which fills a rectangle
        neatly but would pile everything into the bottom of any other
        shape.

        If True, masks that fit nowhere are skipped instead of failing
        the packing.

        Number of threads to use. `None` (default) uses all cores.

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> square = np.ones((4, 4), dtype=bool)
>>> pos, variant, grid = fastcore.pack_masks([square, square], page_shape=(8, 8))
>>> pos
array([[0., 0.],
       [4., 0.]])

            Whether rectangles may be turned a quarter turn.

            If True, rectangles that fit nowhere are skipped instead of
            failing the packing.

            Free space ``(x, y, width, height)`` to pack into, e.g. what
            an earlier call left over. Defaults to the whole page.

>>> import navis_fastcore as fastcore
>>> pos, rotated, free = fastcore.pack_rectangles(
...     [[4, 4], [4, 4]], page_size=(8, 4)
... )
>>> pos
array([[0., 0.],
       [4., 0.]])