Module spatial_hit_index 

Spatial hit-test index with z-order support and dirty-rect caching.

Provides O(1) average-case hit-test queries for thousands of widgets by using uniform grid bucketing with z-order tracking.

Design

Uses a hybrid approach:

• Uniform grid: Screen divided into cells (default 8x8 pixels each)
• Bucket lists: Each grid cell stores widget IDs that overlap it
• Z-order tracking: Widgets have explicit z-order; topmost wins on overlap
• Dirty-rect cache: Last hover result cached; invalidated on dirty regions

Invariants

1. Hit-test always returns topmost widget (highest z) at query point
2. Ties broken by registration order (later = on top)
3. Dirty regions force recomputation of affected buckets only
4. No allocations on steady-state hit-test queries

Failure Modes

• Buckets are unbounded Vecs: pathological overlap degrades queries to a per-bucket linear scan but never loses entries (there is no separate fallback path).
• HitId::default() (id 0) is reserved as the removed-entry sentinel; SpatialHitIndex::register rejects it.
• Re-registering an existing id replaces the previous entry.

Structs

CacheStats

Diagnostic statistics for cache performance.

HitEntry

A registered widget’s hit information.

SpatialHitConfig

Configuration for the spatial hit index.

SpatialHitIndex

Spatial index for efficient hit-testing with z-order support.