Skip to content
Projects

Quadtrees

Download notebookView on GitHubRun when the site was built.

The cells of a FlatQuadtree, how deep it splits where the charges crowd, and which cells a Barnes-Hut walk takes as multipoles for one target, drawn with plasma-plots’ plot_quadtree.

Two clusters of charges of both signs on a sparse background. The tree splits every cell holding more than leaf_capacity charges, so it reaches deep inside the clusters and stays shallow around them. plot_quadtree reads the cells straight from the tree: their centres, half widths, depths, children and particle counts.

import numpy as np
import plasma_plots
from plasma_plots.trees import barnes_hut_walk, plot_quadtree, quadtree_cells
from tree_d_3d import FlatQuadtree, Quad, direct_field
plasma_plots.set_backend("plotly")
plasma_plots.set_math("latex")
rng = np.random.default_rng(4)
pos = np.concatenate(
[
rng.normal((-0.45, -0.35), 0.1, (900, 2)),
rng.normal((0.4, 0.35), 0.18, (900, 2)),
rng.uniform(-1.0, 1.0, (300, 2)),
]
).T.clip(-0.999, 0.999)
charge = rng.choice([-1.0, 1.0], pos.shape[1])
tree = FlatQuadtree(pos, charge, Quad(0.0, 0.0, 1.0), leaf_capacity=8)
cells = quadtree_cells(tree)
print(
f"{pos.shape[1]} charges, {int((cells.counts > 0).sum())} cells, depth {cells.depths.max()}"
)
plot_quadtree(tree, points=pos, point_color=charge, title="The tree on 2100 charges")
2100 charges, 755 cells, depth 8
Loading figure…

The leaf capacity sets how far the tree splits. A larger one makes fewer, fuller leaves: a shorter walk with longer direct sums at its end. Coloured by the charges each leaf holds:

with plasma_plots.figure(2, 1, figsize=(6.4, 11.5), gridspec_kw={"hspace": 0.3}) as fig:
for ax, capacity in zip(fig, (8, 32)):
small = FlatQuadtree(pos, charge, Quad(0.0, 0.0, 1.0), leaf_capacity=capacity)
plot_quadtree(small, color="count", ax=ax, title=f"leaf capacity {capacity}")
fig
Loading figure…

For one target the walk starts at the root. A cell of side ss at distance dd counts as a single multipole when s/d<θs/d < \theta; any other cell is opened, down to the leaves, which are summed charge by charge. A small opening angle opens more cells and is more accurate:

target = (0.1, -0.05)
with plasma_plots.figure(2, 1, figsize=(6.4, 11.5), gridspec_kw={"hspace": 0.3}) as fig:
for ax, theta in zip(fig, (0.3, 0.8)):
plot_quadtree(tree, points=pos, target=target, theta=theta, color=None, ax=ax)
fig
Loading figure…

The work of a walk is the multipoles it takes plus the charges in the leaves it sums. Counted with barnes_hut_walk for every charge as a target, against the error of FlatQuadtree.evaluate relative to the direct sum:

exact = direct_field(pos, pos, charge, exclude=np.arange(pos.shape[1]), softening=1e-3)[
1
]
thetas = np.array([0.2, 0.3, 0.45, 0.6, 0.8, 1.0])
error, work = [], []
sample = rng.choice(pos.shape[1], 200, replace=False)
for theta in thetas:
field = tree.evaluate(
pos, exclude=np.arange(pos.shape[1]), theta=theta, softening=1e-3
)[1]
error.append(np.abs(field - exact).max() / np.abs(exact).max())
walks = [barnes_hut_walk(cells, pos[:, i], theta) for i in sample]
work.append(
np.mean([w["accepted"].sum() + cells.counts[w["direct"]].sum() for w in walks])
)
with plasma_plots.figure(2, 1, sharex=True, figsize=(6.4, 8.0)) as fig:
fig[0].semilogy(thetas, error, "o-")
fig[0].set_ylabel("largest field error")
fig[1].plot(thetas, work, "o-", color="C1")
fig[1].axhline(pos.shape[1], color="gray", linestyle="--", label="direct sum")
fig[1].set_ylabel("interactions per target")
fig[1].set_xlabel(r"opening angle $\theta$")
fig[1].legend()
fig
Loading figure…