template<typename T> asge::spatial::QuadTree

Allocates a node from the arena, or returns nullptr if the arena is full.

Returns an empty block from the free list or the arena, or nullptr if the arena is full.

Pushes the block on the free list for later reuse.

Appends the element to the node's last block, chaining a new one if full.

False if the arena is full.

Returns 0..3 if the input rect fits one quadrant, -1 otherwise.

Recursively inserts an element into the tree.

False only if the arena has no room for it.

Splits the leaf into 4 children and moves the elements that fit a quadrant down.

Elements that straddle a split line, or whose child could not get a block, stay in the node. If the arena cannot hold 4 children the node is left as a leaf.

Visits the elements of the subtree for which inElemPred holds, using an explicit fixed-size stack.

A child is entered only if inNodePred holds for its bounds, so the node predicate must be true whenever the element predicate is true for something inside the node. Nodes are visited in the same order as a recursive walk (parent, then children 0..3). Returns false once the visitor asked to stop.

Branch-and-bound step of Nearest: updates the best element found so far in the subtree.

Reports the overlapping pairs found in the subtree of inNode.

ioScratch[inAncBegin, inAncEnd) holds the ancestor elements that overlap inNode and is the end of the buffer on entry; children append their own filtered list after it and truncate back once visited. Returns false once the visitor asked to stop.

Reserves an arena of inArenaBytes for nodes and element blocks, and caps the tree at inMaxElements.

Drops every element and node, then starts a new empty tree covering [0,inW]x[0,inH].

Errors with invalid_argument unless both sizes are finite and positive, and with no_buffer_space if the arena cannot even hold the root. After an error the tree is empty and uninitialised, so Insert fails until a Reset succeeds.

Like Reset(inW, inH), but the new tree covers inBounds, which may start away from the origin.

Inserts an element with the given bounds.

Errors if Reset() was never called, the bounds are not fully inside the root, the element budget is exhausted, or the arena has no room left for the element. A failed insert leaves the tree valid and unchanged in content.

Number of elements currently stored.

Calls inVisitor(value) for every element overlapping inRect.

The visitor returns true to continue or false to stop the traversal early. Overlap is strict (AabbOverlap), so rects that only touch are not reported.

Calls inVisitor(value) for every element whose rect strictly contains inPoint.

Same visitor protocol as the Rect overload; a point exactly on an element's edge is not inside it.

Calls inVisitor(value) for every element whose rect is closer to the circle's center than its radius.

Same visitor protocol as the Rect overload; an element that only touches the circle is not reported.

Returns the value of the element whose rect is closest to inPoint.

The distance is 0 for a point inside or on an element. When several elements are equally close, which one is returned is unspecified. Empty if the tree is empty or uninitialised.

Number of nodes created since the last Reset, root included.

Depth of the deepest node created since the last Reset (the root is 0).

True if an arena allocation failed since the last Reset.

It means the tree degraded: some leaf could not split, or an Insert was refused for lack of memory. Compare ArenaUsed() with ArenaCapacity() to size the arena.

Arena bytes consumed so far by nodes and element blocks.

Total arena size in bytes.

Calls inVisitor(a, b) once for every unordered pair of overlapping elements.

Never pairs an element with itself and never reports a pair twice; the order of the pairs and of the two values within a pair is unspecified. The visitor returns true to continue or false to stop early. Allocates one scratch buffer per call.