Skip to content
Projects

plasma_plots.trees

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() 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

>>> 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)

Classes

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

Functions

NameDescription
animate_quadtreeAnimate a quadtree that follows moving particles: the cells and particles of every frame.
barnes_hut_walkThe cells a Barnes-Hut walk for one target takes as multipoles, opens or sums directly.
build_quadtreeBuild a quadtree of points: split every cell holding more than leaf_capacity.
plot_quadtreePlot the cells of a quadtree, its particles and the Barnes-Hut walk for a target.
quadtree_cellsThe cells of a quadtree, from a tree object or from arrays.

QuadtreeCellsclassdataclass#

class QuadtreeCells(centers: np.ndarray, half_widths: np.ndarray, depths: np.ndarray, children: np.ndarray, counts: np.ndarray | None = None)

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

Attributes

NameTypeDescription
centersnumpy.ndarray(n, 2) cell centres.
half_widthsnumpy.ndarray(n,) half side lengths.
depthsnumpy.ndarray(n,) depths, 0 for the root.
childrennumpy.ndarray(n, 4) indices of the children, -1 where there is none.
countsnumpy.ndarray or None(n,) particles in each cell, if known.
leavesnumpy.ndarrayMask of the cells without children.

centersattributeinstance attribute#

centers: np.ndarray

childrenattributeinstance attribute#

children: np.ndarray

countsattributeclass attributeinstance attribute#

counts: np.ndarray | None = None

depthsattributeinstance attribute#

depths: np.ndarray

half_widthsattributeinstance attribute#

half_widths: np.ndarray

leavesproperty#

leaves: np.ndarray

Mask of the cells without children.

animate_quadtreefunction#

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() 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

NameTypeDefaultDescription
treessequenceNoneOne tree per frame: a QuadtreeCells or a tree with tree-d-3d’s attribute names (see quadtree_cells()). Default: built from points for every frame (build_quadtree() with leaf_capacity and bounds).
pointssequence of arrayNoneOne (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_colorarray or sequence of arrayNoneValues 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.
timessequence of floatNoneThe time (or other sweep value) of each frame, for the titles and the slider of the Plotly version. Default: the frame numbers.
sweepstr't'The name of the sweep, e.g. "t" or "step". Default: "t".
color'depth'"depth"Color the outlines by depth, with a color bar, or draw them in one gray. Default: "depth".
leaves_onlyboolFalseDraw only the leaves. Default: False.
max_depthintNoneDraw no cells deeper than this. Default: all.
leaf_capacityint8The most points a leaf of a tree built from points holds. Default: 8.
bounds(float, float, float)NoneThe 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)NoneThe axes limits (x_min, x_max, y_min, y_max), fixed over the animation. Default: the smallest square holding every frame’s root cell.
cmapstr or matplotlib.colors.ColormapNoneThe colormap of the outlines. Default: "viridis" without its darkest fifth.
point_cmapstr or matplotlib.colors.ColormapNoneThe colormap of point_color. Default: "coolwarm".
linewidthfloat0.8The width of the outlines in points. Default: 0.8.
sfloat6The size of the particle dots. Default: 6.
intervalint100The delay between frames, in milliseconds. Default: 100.
max_framesintNoneKeep at most this many frames, evenly spaced (the first and last included), e.g. to keep a Plotly animation small. Default: all.
titlestrNoneA 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')"matplotlib"Draw with this backend; default: the one of plasma_plots.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.

Examples

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

barnes_hut_walkfunction#

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

NameTypeDefaultDescription
cellsQuadtreeCells or treerequiredThe cells (see quadtree_cells()).
target(float, float)requiredThe point where the field is evaluated.
thetafloat0.5The 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

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

build_quadtreefunction#

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

NameTypeDefaultDescription
pointsarrayrequired(2, N) or (N, 2) positions (a (2, 2) array is read as (2, N)).
leaf_capacityint8The most points a leaf holds. Default: 8.
bounds(float, float, float)NoneThe root cell as (x_centre, y_centre, half_width). Default: the smallest square around the points.
max_depthint24The 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

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

plot_quadtreefunction#

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

NameTypeDefaultDescription
treeobjectNoneA QuadtreeCells, a tree with tree-d-3d’s attribute names (see quadtree_cells()), or None to build one from points (build_quadtree() with its defaults).
pointsarrayNone(2, N) or (N, 2) particle positions, drawn as dots. Default: none.
color('depth', 'count')"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_colorarrayNone(N,) values to color the particles by, e.g. their charge, on a diverging map symmetric about zero. Default: one color.
leaves_onlyboolFalseDraw only the leaves, the cells that hold particles. Default: False.
max_depthintNoneDraw no cells deeper than this. Default: all.
target(float, float)NoneA point to show a Barnes-Hut walk for (barnes_hut_walk()): the cells taken as multipoles and the leaves summed directly are outlined boldly. Default: none.
thetafloat0.5The opening angle of the walk. Default: 0.5.
axmatplotlib.axes.AxesNoneThe axes to draw into. Default: a new figure.
cmapstr or matplotlib.colors.ColormapNoneThe colormap of the outlines. Default: "viridis".
linewidthfloat0.8The width of the outlines in points. Default: 0.8.
sfloat6The size of the particle dots. Default: 6.
titlestrNoneThe title. Default: the number of cells, or the walk’s counts with a target.
backend('matplotlib', 'plotly', 'tikz')"matplotlib"Draw with this backend; default: the one of plasma_plots.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.

Examples

>>> 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")

quadtree_cellsfunction#

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

NameTypeDefaultDescription
treeobjectNoneA 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.
centersarrayNoneThe arrays of QuadtreeCells, without a tree. children is needed for leaves and walks; without it every cell counts as a leaf.
half_widthsarrayNoneThe arrays of QuadtreeCells, without a tree. children is needed for leaves and walks; without it every cell counts as a leaf.
depthsarrayNoneThe arrays of QuadtreeCells, without a tree. children is needed for leaves and walks; without it every cell counts as a leaf.
childrenarrayNoneThe arrays of QuadtreeCells, without a tree. children is needed for leaves and walks; without it every cell counts as a leaf.
countsarrayNoneThe arrays of 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

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