Module spatial 

A static R-tree over 2D boxes, with an overflow list for what is added after the build (ADR-0010).

Written to move as is. This module imports nothing from the rest of the crate (nor any dependency): the design lets the heads and the spatial layer be born in energyml-section and move down to the future energyml-cache crate by copying this one file.

What it is

• Static, packed by STR (sort-tile-recursive, Leutenegger et al. 1997): the boxes are sorted by the x of their centre, cut into vertical slices, each slice sorted by y and cut into nodes of FAN_OUT boxes; the nodes are packed the same way, level by level, up to one root. No box is ever moved after the build, so there is no balancing to get wrong.
• An overflow list: Index::insert after the build appends to a flat list scanned on every query; once it outgrows a share of the tree (Index::needs_rebuild) the next insert folds it in and rebuilds.
• Exact by construction: a query returns every item whose box meets the query box (closed boxes: touching counts), and only those - the same answer as a linear scan, in another order. The tests confront the two on random data. What the tree saves is the boxes it never opens, not any precision; a query by a polygon is its bounding box (Rect::of_points), then the caller’s exact test on what comes back.

A box with a non-finite bound is not indexable: Rect::new refuses it (None), so the caller decides what such an item means rather than the tree losing it silently.

Structs

Index

The index: items of type T filed under their box.

Rect

A closed 2D box: min <= max on both axes, both finite.

Constants

FAN_OUT

Boxes per node. Eight keeps a 5 000-item tree four levels deep.

OVERFLOW_FLOOR

The overflow is folded into the tree when it holds more than this many items and more than a quarter of the tree.