# plasma_plots.trees

*module*

Quadtrees: the cells of a tree code, a Barnes-Hut walk and the particles they hold.

A tree code (Barnes-Hut, the fast multipole method) sorts particles into a hierarchy of nested
squares. [`plot_quadtree()`][plasma_plots.trees.plot_quadtree] draws that hierarchy: every cell's outline colored by its depth
(or by the particles of each leaf), the particles, and for a target point the cells a
Barnes-Hut walk at opening angle ``theta`` takes as multipoles and the leaves it sums directly.

The cells are plain arrays ([`QuadtreeCells`][QuadtreeCells]): centres, half widths, depths and children.
[`quadtree_cells()`][quadtree_cells] reads them from a tree object with the attribute names of
tree-d-3d's ``FlatQuadtree`` (``node_center``, ``node_half``, ``node_depth``, ``node_child``,
``node_start``, ``node_end``), and [`build_quadtree()`][build_quadtree] builds a tree from points, so the plots
need no tree code at all. [`barnes_hut_walk()`][barnes_hut_walk] classifies the cells for one target.

**Examples**

```pycon
>>> cells = build_quadtree(points, leaf_capacity=8)
>>> plot_quadtree(cells, points=points)
>>> plot_quadtree(tree, points=tree.pos, target=(0.3, -0.2), theta=0.5)
>>> plot_quadtree(cells, color="count", leaves_only=True)
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L1-L1)

## plasma_plots.trees.QuadtreeCells

*class* · *dataclass*

```python
class QuadtreeCells
```

The cells of a quadtree as arrays, one row per cell, the root first.

**Attributes**

- `centers` (`numpy.ndarray`) — ``(n, 2)`` cell centres.
- `half_widths` (`numpy.ndarray`) — ``(n,)`` half side lengths.
- `depths` (`numpy.ndarray`) — ``(n,)`` depths, 0 for the root.
- `children` (`numpy.ndarray`) — ``(n, 4)`` indices of the children, -1 where there is none.
- `counts` (`numpy.ndarray or None`) — ``(n,)`` particles in each cell, if known.
- `leaves` (`numpy.ndarray`) — Mask of the cells without children.

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L32-L64)

### plasma_plots.trees.QuadtreeCells.centers

*attribute* · *instance attribute*

```python
centers: np.ndarray
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L52-L52)

### plasma_plots.trees.QuadtreeCells.children

*attribute* · *instance attribute*

```python
children: np.ndarray
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L55-L55)

### plasma_plots.trees.QuadtreeCells.counts

*attribute* · *class attribute* · *instance attribute*

```python
counts: np.ndarray | None = None
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L56-L56)

### plasma_plots.trees.QuadtreeCells.depths

*attribute* · *instance attribute*

```python
depths: np.ndarray
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L54-L54)

### plasma_plots.trees.QuadtreeCells.half_widths

*attribute* · *instance attribute*

```python
half_widths: np.ndarray
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L53-L53)

### plasma_plots.trees.QuadtreeCells.leaves

*property*

```python
leaves: np.ndarray
```

Mask of the cells without children.

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L59-L61)

## plasma_plots.trees.animate_quadtree

*function*

```python
def animate_quadtree(trees=None, *, points=None, point_color=None, times=None, sweep: str = 't', color: str | None = 'depth', leaves_only: bool = False, max_depth: int | None = None, leaf_capacity: int = 8, bounds=None, extent=None, cmap=None, point_cmap=None, linewidth: float = 0.8, s: float = 6, interval: int = 100, max_frames: int | None = None, title: str | None = None, backend=None)
```

Animate a quadtree that follows moving particles: the cells and particles of every frame.

Each frame draws the cells of its tree as [`plot_quadtree()`][plasma_plots.trees.plot_quadtree] does, colored by depth on one
scale for the whole animation, with the particles on top, so the refinement can be watched
following the particles as they cluster, spread or form filaments.

**Parameters**

- `trees` (`sequence`) (default: `None`) — One tree per frame: a [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells] or a tree with tree-d-3d's attribute names (see [`quadtree_cells()`][plasma_plots.trees.quadtree_cells]). Default: built from ``points`` for every frame ([`build_quadtree()`][plasma_plots.trees.build_quadtree] with ``leaf_capacity`` and ``bounds``).
- `points` (`sequence of array`) (default: `None`) — One ``(2, N)`` or ``(N, 2)`` array of positions per frame (the number of particles may change), or one array with a leading frame axis. Needed without ``trees``. Default: no particles.
- `point_color` (`array or sequence of array`) (default: `None`) — Values to color the particles by on a diverging map symmetric about zero: one ``(N,)`` array for every frame (e.g. the charges), or one per frame. Default: one color.
- `times` (`sequence of float`) (default: `None`) — The time (or other sweep value) of each frame, for the titles and the slider of the Plotly version. Default: the frame numbers.
- `sweep` (`str`) (default: `'t'`) — The name of the sweep, e.g. ``"t"`` or ``"step"``. Default: ``"t"``.
- `color` (`'depth'`) (default: `"depth"`) — Color the outlines by depth, with a color bar, or draw them in one gray. Default: ``"depth"``.
- `leaves_only` (`bool`) (default: `False`) — Draw only the leaves. Default: ``False``.
- `max_depth` (`int`) (default: `None`) — Draw no cells deeper than this. Default: all.
- `leaf_capacity` (`int`) (default: `8`) — The most points a leaf of a tree built from ``points`` holds. Default: 8.
- `bounds` (`(float, float, float)`) (default: `None`) — The root cell ``(x_centre, y_centre, half_width)`` of trees built from ``points``. Default: the smallest square around each frame's points.
- `extent` (`(float, float, float, float)`) (default: `None`) — The axes limits ``(x_min, x_max, y_min, y_max)``, fixed over the animation. Default: the smallest square holding every frame's root cell.
- `cmap` (`str or matplotlib.colors.Colormap`) (default: `None`) — The colormap of the outlines. Default: ``"viridis"`` without its darkest fifth.
- `point_cmap` (`str or matplotlib.colors.Colormap`) (default: `None`) — The colormap of ``point_color``. Default: ``"coolwarm"``.
- `linewidth` (`float`) (default: `0.8`) — The width of the outlines in points. Default: 0.8.
- `s` (`float`) (default: `6`) — The size of the particle dots. Default: 6.
- `interval` (`int`) (default: `100`) — The delay between frames, in milliseconds. Default: 100.
- `max_frames` (`int`) (default: `None`) — Keep at most this many frames, evenly spaced (the first and last included), e.g. to keep a Plotly animation small. Default: all.
- `title` (`str`) (default: `None`) — A format string for each frame's title, with the fields ``sweep``, ``time``, ``cells``, ``leaves`` and ``depth``. Default: ``"{sweep} = {time}: {leaves} leaves, depth {depth}"``.
- `backend` (`('matplotlib', 'plotly', 'tikz')`) (default: `"matplotlib"`) — Draw with this backend; default: the one of [`plasma_plots.set_backend()`][plasma_plots.plotly_backend.set_backend]. With Plotly the result is a figure with one frame per time, a slider and Play/Pause buttons.

**Returns**

- (`matplotlib.animation.FuncAnimation or PlotResult`) — The animation (retain it, e.g. in a variable, or it stops), or with Plotly the converted figure.

**Raises**

- `ValueError` — If ``color`` is unknown, neither trees nor points are given, or the frame counts differ.

> **See Also**
>
> [`plot_quadtree()`][plasma_plots.trees.plot_quadtree] : One tree.
> [`build_quadtree()`][plasma_plots.trees.build_quadtree] : A quadtree of points.

**Examples**

```pycon
>>> # builds the trees
>>> animate_quadtree(points=history, times=t, leaf_capacity=16)
>>> animate_quadtree(
...     trees, points=[tree.pos for tree in trees], backend="plotly"
... )
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L525-L770)

## plasma_plots.trees.barnes_hut_walk

*function*

```python
def barnes_hut_walk(cells, target, theta: float = 0.5) -> dict[str, np.ndarray]
```

The cells a Barnes-Hut walk for one target takes as multipoles, opens or sums directly.

From the root down, a cell of side ``s`` at distance ``d`` from the target (to its centre)
is accepted when ``s / d < theta`` and it does not hold the target; otherwise a leaf is
summed directly and any other cell is opened.

**Parameters**

- `cells` (`QuadtreeCells or tree`) — The cells (see [`quadtree_cells()`][plasma_plots.trees.quadtree_cells]).
- `target` (`(float, float)`) — The point where the field is evaluated.
- `theta` (`float`) (default: `0.5`) — The opening angle. Default: 0.5.

**Returns**

- (`dict of str to numpy.ndarray`) — Masks over the cells: ``"accepted"`` (multipoles), ``"direct"`` (leaves summed particle by particle) and ``"opened"``.

**Raises**

- `ValueError` — If ``theta`` is negative.

**Examples**

```pycon
>>> walk = barnes_hut_walk(cells, (0.2, 0.1), theta=0.5)
>>> int(walk["accepted"].sum()), int(walk["direct"].sum())
(28, 6)
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L230-L287)

## plasma_plots.trees.build_quadtree

*function*

```python
def build_quadtree(points, *, leaf_capacity: int = 8, bounds=None, max_depth: int = 24) -> QuadtreeCells
```

Build a quadtree of points: split every cell holding more than ``leaf_capacity``.

**Parameters**

- `points` (`array`) — ``(2, N)`` or ``(N, 2)`` positions (a ``(2, 2)`` array is read as ``(2, N)``).
- `leaf_capacity` (`int`) (default: `8`) — The most points a leaf holds. Default: 8.
- `bounds` (`(float, float, float)`) (default: `None`) — The root cell as ``(x_centre, y_centre, half_width)``. Default: the smallest square around the points.
- `max_depth` (`int`) (default: `24`) — The deepest level, which stops the splitting of coincident points. Default: 24.

**Returns**

- (`QuadtreeCells`) — The cells, with the number of points in each.

**Raises**

- `ValueError` — If ``leaf_capacity`` is not positive or there are no points.

**Examples**

```pycon
>>> cells = build_quadtree(np.random.default_rng(0).normal(size=(2, 1000)))
>>> int(cells.leaves.sum()) > 1
True
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L153-L227)

## plasma_plots.trees.plot_quadtree

*function*

```python
def plot_quadtree(tree=None, *, points=None, color: str | None = 'depth', point_color=None, leaves_only: bool = False, max_depth: int | None = None, target=None, theta: float = 0.5, ax=None, cmap=None, linewidth: float = 0.8, s: float = 6, title: str | None = None, backend=None)
```

Plot the cells of a quadtree, its particles and the Barnes-Hut walk for a target.

**Parameters**

- `tree` (`object`) (default: `None`) — A [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], a tree with tree-d-3d's attribute names (see [`quadtree_cells()`][plasma_plots.trees.quadtree_cells]), or ``None`` to build one from ``points`` ([`build_quadtree()`][plasma_plots.trees.build_quadtree] with its defaults).
- `points` (`array`) (default: `None`) — ``(2, N)`` or ``(N, 2)`` particle positions, drawn as dots. Default: none.
- `color` (`('depth', 'count')`) (default: `"depth"`) — Color the outlines by depth, or the leaves by the particles they hold (needs counts), with a color bar; ``None`` draws them in one gray. Default: ``"depth"``.
- `point_color` (`array`) (default: `None`) — ``(N,)`` values to color the particles by, e.g. their charge, on a diverging map symmetric about zero. Default: one color.
- `leaves_only` (`bool`) (default: `False`) — Draw only the leaves, the cells that hold particles. Default: ``False``.
- `max_depth` (`int`) (default: `None`) — Draw no cells deeper than this. Default: all.
- `target` (`(float, float)`) (default: `None`) — A point to show a Barnes-Hut walk for ([`barnes_hut_walk()`][plasma_plots.trees.barnes_hut_walk]): the cells taken as multipoles and the leaves summed directly are outlined boldly. Default: none.
- `theta` (`float`) (default: `0.5`) — The opening angle of the walk. Default: 0.5.
- `ax` (`matplotlib.axes.Axes`) (default: `None`) — The axes to draw into. Default: a new figure.
- `cmap` (`str or matplotlib.colors.Colormap`) (default: `None`) — The colormap of the outlines. Default: ``"viridis"``.
- `linewidth` (`float`) (default: `0.8`) — The width of the outlines in points. Default: 0.8.
- `s` (`float`) (default: `6`) — The size of the particle dots. Default: 6.
- `title` (`str`) (default: `None`) — The title. Default: the number of cells, or the walk's counts with a target.
- `backend` (`('matplotlib', 'plotly', 'tikz')`) (default: `"matplotlib"`) — Draw with this backend; default: the one of [`plasma_plots.set_backend()`][plasma_plots.plotly_backend.set_backend].

**Returns**

- (`PlotResult`) — The figure and axes, with the cells in ``data["cells"]`` and, with a target, the walk's masks in ``data["walk"]``.

**Raises**

- `ValueError` — If ``color`` is unknown, ``"count"`` has no counts, or neither a tree nor points are
given.

> **See Also**
>
> [`build_quadtree()`][plasma_plots.trees.build_quadtree] : A quadtree of points.
> [`barnes_hut_walk()`][plasma_plots.trees.barnes_hut_walk] : The classification of the cells for one target.

**Examples**

```pycon
>>> plot_quadtree(points=positions)  # builds the tree
>>> plot_quadtree(tree, points=tree.pos, target=(0.1, 0.4), theta=0.7)
>>> plot_quadtree(tree, color="count", leaves_only=True, backend="plotly")
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L312-L510)

## plasma_plots.trees.quadtree_cells

*function*

```python
def quadtree_cells(tree=None, *, centers=None, half_widths=None, depths=None, children=None, counts=None) -> QuadtreeCells
```

The cells of a quadtree, from a tree object or from arrays.

**Parameters**

- `tree` (`object`) (default: `None`) — A [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], or a tree with the attributes ``node_center`` ``(n, 2)``, ``node_half`` ``(n,)`` and ``node_depth`` ``(n,)``, and optionally ``node_child`` (the first of four consecutive children, -1 for a leaf; or an ``(n, 4)`` array) and ``node_start`` and ``node_end`` (the particle range of each cell), as tree-d-3d's ``FlatQuadtree`` has them. Default: the arrays.
- `centers` (`array`) (default: `None`) — The arrays of [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], without a tree. ``children`` is needed for leaves and walks; without it every cell counts as a leaf.
- `half_widths` (`array`) (default: `None`) — The arrays of [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], without a tree. ``children`` is needed for leaves and walks; without it every cell counts as a leaf.
- `depths` (`array`) (default: `None`) — The arrays of [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], without a tree. ``children`` is needed for leaves and walks; without it every cell counts as a leaf.
- `children` (`array`) (default: `None`) — The arrays of [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], without a tree. ``children`` is needed for leaves and walks; without it every cell counts as a leaf.
- `counts` (`array`) (default: `None`) — The arrays of [`QuadtreeCells`][plasma_plots.trees.QuadtreeCells], without a tree. ``children`` is needed for leaves and walks; without it every cell counts as a leaf.

**Returns**

- (`QuadtreeCells`) — The cells.

**Raises**

- `ValueError` — If neither a tree nor ``centers`` and ``half_widths`` are given, or the shapes differ.

**Examples**

```pycon
>>> cells = quadtree_cells(tree)  # a FlatQuadtree
>>> cells = quadtree_cells(centers=c, half_widths=h, depths=d, children=k)
```

[View source](https://github.com/max-models/plasma-plots/blob/devel/src/plasma_plots/trees.py#L74-L142)
