SpatialIndex

You can start using this now by inserthing this at the top of your indicator/strategy/library.

import ArunaReborn/SpatialIndex/1 as SI


Overview


SpatialIndex is a high-performance Pine Script library that implements price-bucketed spatial indexing for efficient proximity queries on large datasets. Instead of scanning through hundreds or thousands of items linearly (O(n)), this library provides O(k) bucket lookup where k is typically just a handful of buckets, dramatically improving performance for price-based filtering operations.

This library works with any data type through index-based references, making it universally applicable for support/resistance levels, pivot points, order zones, pattern detection points, Fair Value Gaps, and any other price-based data that needs frequent proximity queries.

Why This Library Exists

The Problem

When building advanced technical indicators that track large numbers of price levels (support/resistance zones, pivot points, order blocks, etc.), you often need to answer questions like:
- *"Which levels are within 5% of the current price?"*
- *"What zones overlap with this price range?"*
- *"Are there any significant levels near my entry point?"*

The naive approach is to loop through every single item and check its price. For 500 levels across multiple timeframes, this means 500 comparisons every bar. On instruments with thousands of historical bars, this quickly becomes a performance bottleneck that can cause scripts to time out or lag.

The Solution

SpatialIndex solves this by organizing items into price buckets—like filing cabinets organized by price range. When you query for items near $50,000, the library only looks in the relevant buckets (e.g., $49,000-$51,000 range), ignoring all other price regions entirely.

Performance Example:
- Linear scan: Check 500 items = 500 comparisons per query
- Spatial index: Check 3-5 buckets with ~10 items each = 30-50 comparisons per query
- Result: 10-16x faster queries

Key Features

Core Capabilities
- ✅ Generic Design: Works with any data type via index references
- ✅ Multiple Index Strategies: Fixed bucket size or ATR-based dynamic sizing
- ✅ Range Support: Index items that span price ranges (zones, gaps, channels)
- ✅ Efficient Queries: O(k) bucket lookup instead of O(n) linear scan
- ✅ Multiple Query Types: Proximity percentage, fixed range, exact price with tolerance
- ✅ Dynamic Updates: Add, remove, update items in O(1) time
- ✅ Batch Operations: Efficient bulk removal and reindexing
- ✅ Query Caching: Optional caching for repeated queries within same bar
- ✅ Statistics & Debugging: Built-in stats and diagnostic functions

### Advanced Features
- ATR-Based Bucketing: Automatically adjusts bucket sizes based on volatility
- Multi-Bucket Spanning: Items that span ranges are indexed in all overlapping buckets
- Reindexing Support: Handles array removals with automatic index shifting
- Cache Management: Configurable query caching with automatic invalidation
- Empty Bucket Cleanup: Automatically removes empty buckets to minimize memory


How It Works

The Bucketing Concept

Think of price space as divided into discrete buckets, like a histogram:

```
Price Range: $98-$100 $100-$102 $102-$104 $104-$106 $106-$108
Bucket Key: 49 50 51 52 53
Items: [1,5,9] [2,7] [3,4] [] [6,8]
```

When you query for items near $103:
1. Calculate which buckets overlap the $101.50-$104.50 range (keys 50, 51, 52)
2. Return items from only those buckets: [2, 3, 4, 7]
3. Never check items in buckets 49 or 53

Bucket Size Selection

Fixed Size Mode:
```pine
var SI.SpatialBucket index = SI.newSpatialBucket(2.0) // $2 per bucket
```
- Good for: Instruments with stable price ranges
- Example: For stocks trading at $100, 2.0 = 2% increments

ATR-Based Mode:
```pine
float atr = ta.atr(14)
var SI.SpatialBucket index = SI.newSpatialBucketATR(1.0, atr) // 1x ATR per bucket
SI.updateATR(index, atr) // Update each bar
```
- Good for: Instruments with varying volatility
- Adapts automatically to market conditions
- 1.0 multiplier = one bucket spans one ATR unit

Optimal Bucket Size:
The library includes a helper function to calculate optimal size:
```pine
float optimalSize = SI.calculateOptimalBucketSize(close, 5.0) // For 5% proximity queries
```
This ensures queries span approximately 3 buckets for optimal performance.

Index-Based Architecture

The library doesn't store your actual data—it only stores indices that point to your external arrays:

```pine
// Your data
var array<float> levels = array.new<float>()
var array<string> types = array.new<string>()
var array<int> ages = array.new<int>()

// Your index
var SI.SpatialBucket index = SI.newSpatialBucket(2.0)

// Add a level
array.push(levels, 50000.0)
array.push(types, "support")
array.push(ages, 0)
SI.add(index, array.size(levels) - 1, 50000.0) // Store index 0

// Query near current price
SI.QueryResult result = SI.queryProximity(index, close, 5.0)
for idx in result.indices
float level = array.get(levels, idx)
string type = array.get(types, idx)
// Work with your actual data
```

This design means:
- ✅ Works with any data structure you define
- ✅ No data duplication
- ✅ Minimal memory footprint
- ✅ Full control over your data

---

Usage Guide

Basic Setup

```pine
// Import library
import username/SpatialIndex/1 as SI

// Create index
var SI.SpatialBucket index = SI.newSpatialBucket(2.0)

// Your data arrays
var array<float> supportLevels = array.new<float>()
var array<int> touchCounts = array.new<int>()
```

Adding Items

Single Price Point:
```pine
// Add a support level at $50,000
array.push(supportLevels, 50000.0)
array.push(touchCounts, 1)
int levelIdx = array.size(supportLevels) - 1
SI.add(index, levelIdx, 50000.0)
```

Price Range (Zones/Gaps):
```pine
// Add a resistance zone from $51,000 to $52,000
array.push(zoneBottoms, 51000.0)
array.push(zoneTops, 52000.0)
int zoneIdx = array.size(zoneBottoms) - 1
SI.addRange(index, zoneIdx, 51000.0, 52000.0) // Indexed in all overlapping buckets
```

Querying Items

Proximity Query (Percentage):
```pine
// Find all levels within 5% of current price
SI.QueryResult result = SI.queryProximity(index, close, 5.0)

if array.size(result.indices) > 0
for idx in result.indices
float level = array.get(supportLevels, idx)
// Process nearby level
```

Fixed Range Query:
```pine
// Find all items between $49,000 and $51,000
SI.QueryResult result = SI.queryRange(index, 49000.0, 51000.0)
```

Exact Price with Tolerance:
```pine
// Find items at exactly $50,000 +/- $100
SI.QueryResult result = SI.queryAt(index, 50000.0, 100.0)
```

Removing Items

Safe Removal Pattern:
```pine
SI.QueryResult result = SI.queryProximity(index, close, 5.0)

if array.size(result.indices) > 0
// IMPORTANT: Sort descending to safely remove from arrays
array<int> sorted = SI.sortIndicesDescending(result)

for idx in sorted
// Remove from index
SI.remove(index, idx)

// Remove from your data arrays
array.remove(supportLevels, idx)
array.remove(touchCounts, idx)

// Reindex to maintain consistency
SI.reindexAfterRemoval(index, idx)
```

Batch Removal (More Efficient):
```pine
// Collect indices to remove
array<int> toRemove = array.new<int>()
for i = 0 to array.size(supportLevels) - 1
if array.get(touchCounts, i) > 10 // Remove old levels
array.push(toRemove, i)

// Remove in descending order from data arrays
array<int> sorted = array.copy(toRemove)
array.sort(sorted, order.descending)
for idx in sorted
SI.remove(index, idx)
array.remove(supportLevels, idx)
array.remove(touchCounts, idx)

// Batch reindex (much faster than individual reindexing)
SI.reindexAfterBatchRemoval(index, toRemove)
```

Updating Items

```pine
// Update a level's price (e.g., after refinement)
float newPrice = 50100.0
SI.update(index, levelIdx, newPrice)
array.set(supportLevels, levelIdx, newPrice)

// Update a zone's range
SI.updateRange(index, zoneIdx, 51000.0, 52500.0)
array.set(zoneBottoms, zoneIdx, 51000.0)
array.set(zoneTops, zoneIdx, 52500.0)
```

Query Caching

For repeated queries within the same bar:

```pine
// Create cache (persistent)
var SI.CachedQuery cache = SI.newCachedQuery()

// Cached query (returns cached result if parameters match)
SI.QueryResult result = SI.queryProximityCached(
index,
cache,
close,
5.0, // proximity%
1 // cache duration in bars
)

// Invalidate cache when index changes significantly
if bigChangeDetected
SI.invalidateCache(cache)
```

---

Practical Examples

Example 1: Support/Resistance Finder

```pine
//version=6
indicator("S/R with Spatial Index", overlay=true)
import username/SpatialIndex/1 as SI

// Data storage
var array<float> levels = array.new<float>()
var array<string> types = array.new<string>() // "support" or "resistance"
var array<int> touches = array.new<int>()
var array<int> ages = array.new<int>()

// Spatial index
var SI.SpatialBucket index = SI.newSpatialBucket(close * 0.02) // 2% buckets

// Detect pivots
bool isPivotHigh = ta.pivothigh(high, 5, 5)
bool isPivotLow = ta.pivotlow(low, 5, 5)

// Add new levels
if isPivotHigh
array.push(levels, high[5])
array.push(types, "resistance")
array.push(touches, 1)
array.push(ages, 0)
SI.add(index, array.size(levels) - 1, high[5])

if isPivotLow
array.push(levels, low[5])
array.push(types, "support")
array.push(touches, 1)
array.push(ages, 0)
SI.add(index, array.size(levels) - 1, low[5])

// Find nearby levels (fast!)
SI.QueryResult nearby = SI.queryProximity(index, close, 3.0) // Within 3%

// Process nearby levels
for idx in nearby.indices
float level = array.get(levels, idx)
string type = array.get(types, idx)

// Check for touch
if type == "support" and low <= level and low[1] > level
array.set(touches, idx, array.get(touches, idx) + 1)
else if type == "resistance" and high >= level and high[1] < level
array.set(touches, idx, array.get(touches, idx) + 1)

// Age and cleanup old levels
for i = array.size(ages) - 1 to 0
array.set(ages, i, array.get(ages, i) + 1)

// Remove levels older than 500 bars or with 5+ touches
if array.get(ages, i) > 500 or array.get(touches, i) >= 5
SI.remove(index, i)
array.remove(levels, i)
array.remove(types, i)
array.remove(touches, i)
array.remove(ages, i)
SI.reindexAfterRemoval(index, i)

// Visualization
for idx in nearby.indices
line.new(bar_index, array.get(levels, idx), bar_index + 10, array.get(levels, idx),
color=array.get(types, idx) == "support" ? color.green : color.red)
```

Example 2: Multi-Timeframe Zone Detector

```pine
//version=6
indicator("MTF Zones", overlay=true)
import username/SpatialIndex/1 as SI

// Store zones from multiple timeframes
var array<float> zoneBottoms = array.new<float>()
var array<float> zoneTops = array.new<float>()
var array<string> zoneTimeframes = array.new<string>()

// ATR-based spatial index for adaptive bucketing
var SI.SpatialBucket index = SI.newSpatialBucketATR(1.0, ta.atr(14))
SI.updateATR(index, ta.atr(14)) // Update bucket size with volatility

// Request higher timeframe data
[htf_high, htf_low] = request.security(syminfo.tickerid, "240", [high, low])

// Detect HTF zones
if not na(htf_high) and not na(htf_low)
float zoneTop = htf_high
float zoneBottom = htf_low * 0.995 // 0.5% zone thickness

// Check if zone already exists nearby
SI.QueryResult existing = SI.queryRange(index, zoneBottom, zoneTop)

if array.size(existing.indices) == 0 // No overlapping zones
// Add new zone
array.push(zoneBottoms, zoneBottom)
array.push(zoneTops, zoneTop)
array.push(zoneTimeframes, "4H")
int idx = array.size(zoneBottoms) - 1
SI.addRange(index, idx, zoneBottom, zoneTop)

// Query zones near current price
SI.QueryResult nearbyZones = SI.queryProximity(index, close, 2.0) // Within 2%

// Highlight nearby zones
for idx in nearbyZones.indices
box.new(bar_index - 50, array.get(zoneBottoms, idx),
bar_index, array.get(zoneTops, idx),
bgcolor=color.new(color.blue, 90))
```

### Example 3: Performance Comparison

```pine
//version=6
indicator("Spatial Index Performance Test")
import username/SpatialIndex/1 as SI

// Generate 500 random levels
var array<float> levels = array.new<float>()
var SI.SpatialBucket index = SI.newSpatialBucket(close * 0.02)

if bar_index == 0
for i = 0 to 499
float randomLevel = close * (0.9 + math.random() * 0.2) // +/- 10%
array.push(levels, randomLevel)
SI.add(index, i, randomLevel)

// Method 1: Linear scan (naive approach)
int linearCount = 0
float proximityPct = 5.0
float lowBand = close * (1 - proximityPct/100)
float highBand = close * (1 + proximityPct/100)

for i = 0 to array.size(levels) - 1
float level = array.get(levels, i)
if level >= lowBand and level <= highBand
linearCount += 1

// Method 2: Spatial index query
SI.QueryResult result = SI.queryProximity(index, close, proximityPct)
int spatialCount = array.size(result.indices)

// Compare performance
plot(result.queryCount, "Items Examined (Spatial)", color=color.green)
plot(linearCount, "Items Examined (Linear)", color=color.red)
plot(spatialCount, "Results Found", color=color.blue)

// Spatial index typically examines 10-50 items vs 500 for linear scan!
```

API Reference Summary

Initialization
- `newSpatialBucket(bucketSize)` - Fixed bucket size
- `newSpatialBucketATR(atrMultiplier, atrValue)` - ATR-based buckets
- `updateATR(sb, newATR)` - Update ATR for dynamic sizing

Adding Items
- `add(sb, itemIndex, price)` - Add item at single price point
- `addRange(sb, itemIndex, priceBottom, priceTop)` - Add item spanning range

Querying
- `queryProximity(sb, refPrice, proximityPercent)` - Query by percentage
- `queryRange(sb, priceBottom, priceTop)` - Query fixed range
- `queryAt(sb, price, tolerance)` - Query exact price with tolerance
- `queryProximityCached(sb, cache, refPrice, pct, duration)` - Cached query

Removing & Updating
- `remove(sb, itemIndex)` - Remove item
- `update(sb, itemIndex, newPrice)` - Update item price
- `updateRange(sb, itemIndex, newBottom, newTop)` - Update item range
- `reindexAfterRemoval(sb, removedIndex)` - Reindex after single removal
- `reindexAfterBatchRemoval(sb, removedIndices)` - Batch reindex
- `clear(sb)` - Remove all items

Utilities
- `size(sb)` - Get item count
- `isEmpty(sb)` - Check if empty
- `contains(sb, itemIndex)` - Check if item exists
- `getStats(sb)` - Get debug statistics string
- `calculateOptimalBucketSize(price, pct)` - Calculate optimal bucket size
- `sortIndicesDescending(result)` - Sort for safe removal
- `sortIndicesAscending(result)` - Sort ascending


Performance Characteristics

Time Complexity
- Add: O(1) for single point, O(m) for range spanning m buckets
- Remove: O(1) lookup + O(b) bucket cleanup where b = buckets item spans
- Query: O(k) where k = buckets in range (typically 3-5) vs O(n) linear scan
- Update: O(1) removal + O(1) addition = O(1) total

Space Complexity
- Memory per item: ~8 bytes for index reference + map overhead
- Bucket overhead: Proportional to price range coverage
- Typical usage: For 500 items with 50 active buckets ≈ 4-8KB total

Scalability
- ✅ 100 items: ~5-10x faster than linear scan
- ✅ 500 items: ~10-15x faster
- ✅ 1000+ items: ~15-20x faster
- ⚠️ Performance degrades if bucket size is too small (too many buckets)
- ⚠️ Performance degrades if bucket size is too large (too many items per bucket)

Best Practices

Bucket Size Selection
1. Start with 2-5% of asset price for percentage-based queries
2. Use ATR-based mode for volatile assets or multi-symbol scripts
3. Test bucket size using `calculateOptimalBucketSize()` function
4. Monitor with `getStats()` to ensure reasonable bucket count

Memory Management
1. Clear old items regularly to prevent unbounded growth
2. Use age tracking to remove stale data
3. Set maximum item limits based on your needs
4. Batch removals are more efficient than individual removals

Query Optimization
1. Use caching for repeated queries within same bar
2. Invalidate cache when index changes significantly
3. Sort results descending before removal iteration
4. Batch operations when possible (reindexing, removal)

Data Consistency
1. Always reindex after removal to maintain index alignment
2. Remove from arrays in descending order to avoid index shifting issues
3. Use batch reindex for multiple simultaneous removals
4. Keep external arrays and index in sync at all times

Limitations & Caveats

Known Limitations
- Not suitable for exact price matching: Use tolerance with `queryAt()`
- Bucket size affects performance: Too small = many buckets, too large = many items per bucket
- Memory usage: Scales with price range coverage and item count
- Reindexing overhead: Removing items mid-array requires index shifting

When NOT to Use
- ❌ Datasets with < 50 items (linear scan is simpler)
- ❌ Items that change price every bar (constant reindexing overhead)
- ❌ When you need ALL items every time (no benefit over arrays)
- ❌ Exact price level matching without tolerance (use maps instead)

When TO Use
- ✅ Large datasets (100+ items) with occasional queries
- ✅ Proximity-based filtering (% of price, ATR-based ranges)
- ✅ Multi-timeframe level tracking
- ✅ Zone/range overlap detection
- ✅ Price-based spatial filtering

---

Technical Details

Bucketing Algorithm
Items are assigned to buckets using integer division:
```
bucketKey = floor((price - basePrice) / bucketSize)
```

For ATR-based mode:
```
effectiveBucketSize = atrValue × atrMultiplier
bucketKey = floor((price - basePrice) / effectiveBucketSize)
```

Range Indexing
Items spanning price ranges are indexed in all overlapping buckets to ensure accurate range queries. The midpoint bucket is designated as the "primary bucket" for removal operations.

Index Consistency
The library maintains two maps:
1. `buckets`: Maps bucket keys → IntArray wrappers containing item indices
2. `itemToBucket`: Maps item indices → primary bucket key (for O(1) removal)

This dual-mapping ensures both fast queries and fast removal while maintaining consistency.

Implementation Note: Pine Script doesn't allow nested collections (map containing arrays directly), so the library uses an `IntArray` wrapper type to hold arrays within the map structure. This is an internal implementation detail that doesn't affect usage.

---

Version History

Version 1.0
- Initial release

Credits & License

License: Mozilla Public License 2.0 (TradingView default)
Library Type: Open-source educational resource

This library is designed as a public domain utility for the Pine Script community. As per TradingView library rules, this code can be freely reused by other authors. If you use this library in your scripts, please provide appropriate credit as required by House Rules.


Summary

SpatialIndex is a specialized library that solves a specific problem: fast proximity queries on large price-based datasets. If you're building indicators that track hundreds of levels, zones, or price points and need to frequently filter by proximity to current price, this library can provide 10-20x performance improvements over naive linear scanning.

The index-based architecture makes it universally applicable to any data type, and the ATR-based bucketing ensures it adapts to market conditions automatically. Combined with query caching and batch operations, it provides a complete solution for spatial data management in Pine Script.

Use this library when speed matters and your dataset is large.