computeLODCrowding
computeLODCrowding(
tree,opts,scratch?):void
Defined in: network/lod.ts:2038
The tree’s crowding (#426): each node’s LODTree.clearZoom — the zoom from which no two of its
members’ glyphs overlap on screen — from the leaves’ positions (cx/cy) and radii (radius). The cut
opens an aggregate once zoomed past it, so an aggregate is drawn only where its members would overlap.
Exact per node, over its own members (a node’s value is the largest pair zoom among them), computed
bottom-up: a node starts from its children’s values — any pair inside one child — and adds the pairs
across its children: a sweep of the children along x, and a dual walk down two children’s subtrees, pruned
by the box distance and each side’s largest radius against the value so far. A node with more than
CROWDING_BUCKET children is swept in buckets of a 2-D index over its children (median splits of
their boxes, built as the node’s pass goes) and its buckets are joined by the walk, which also descends
through that index when an ancestor walks into the node. So the pass prunes on both axes at any width: a
flat module of m members, and a walk between two wide modules whose members interleave, cost about
O(m log m) — swept along one axis alone they cost O(m·√m) and O(m²).
A node whose value reaches its horizon stops there and stores Infinity. The horizon is the zoom at
which the node’s footprint hits opts.expandPx — the footprint rule opens it first, so its exact value
cannot matter past it — or, when later, an ancestor’s: an ancestor starts from its children’s values, and
extents need not grow up the tree (a clump with one far member reaches farther from its centroid than its
parent’s members do from theirs). So each node is exact up to expandPx / (2·e), e the least extent on
its path to the root — at most twice its own horizon, since an ancestor’s extent is at least half a
descendant’s (both bound the descendant’s members, whose box the ancestor’s contains; a nested layout’s
discs nest too). That horizon keeps the pass cheap on dense layouts — a crowded node stops at its first
children, or after one root-to-bucket path of its index, and no ancestor walks into it (the ancestor
inherits its Infinity) — while every node a view could open by overlap is exact. A node whose extent is not finite (a member with a
non-finite position) needs none: the cut never opens a node whose footprint is NaN. Such a member forms no
pair anywhere.
Run it after the position pass and the style pass, whenever either changes (a style change moves the
radii). O(tree size) for the boxes, O(m log m) to index a node of m > CROWDING_BUCKET children
that is not crowded, plus the pairs the sweeps and the walks cannot prune — those inside a bucket’s x window
while the node is not yet crowded, and the members near the borders between siblings. With scratch
(makeLODCrowdingScratch) a pass allocates nothing once warm.
Parameters
Section titled “Parameters”LODCrowdingTree
scratch?
Section titled “scratch?”Returns
Section titled “Returns”void