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

• If bucket overflow occurs, falls back to linear scan (logged)
• If z-order gaps are large, memory is proportional to max z not widget count (mitigated by z-rank normalization on rebuild)

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.