wenmin-wu/tabular-strtree-spatial-index-collision

STRtree Spatial Index Collision Detection

Overview

Checking all pairs of polygons for overlap is O(n^2). Shapely's STRtree builds an R-tree spatial index, so query(polygon) returns only nearby candidates whose bounding boxes intersect. This reduces collision detection to O(n log n) in practice, enabling real-time overlap validation for packing, placement, and geospatial problems with hundreds of polygons.

Quick Start

from shapely.strtree import STRtree
from shapely.geometry import Polygon

def has_any_overlap(polygons):
    if len(polygons) <= 1:
        return False
    tree = STRtree(polygons)
    for i, poly in enumerate(polygons):
        candidates = tree.query(poly)
        for idx in candidates:
            if idx == i:
                continue
            if poly.intersects(polygons[idx]) and not poly.touches(polygons[idx]):
                return True
    return False

def find_overlapping_pairs(polygons):
    tree = STRtree(polygons)
    pairs = []
    for i, poly in enumerate(polygons):
        for idx in tree.query(poly):
            if idx > i and poly.intersects(polygons[idx]) \
               and not poly.touches(polygons[idx]):
                pairs.append((i, idx))
    return pairs

Workflow

1. Build STRtree from all polygons (one-time O(n log n) cost)
2. For each polygon, query returns indices of candidates with overlapping bounding boxes
3. Run exact intersects only on candidates (not all n polygons)
4. Distinguish intersects (overlap) from touches (shared boundary only)
5. Rebuild tree after modifying polygon positions

Key Decisions

• STRtree vs grid: STRtree handles irregular shapes; grid is faster for uniform-size objects
• touches vs intersects: shared edges/vertices are not overlaps — always filter with not touches
• Rebuild cost: tree must be rebuilt after moves; batch moves before rebuilding
• Precision: scale coordinates to integers or use Decimal to avoid float artifacts

References

• Santa 2025 - Getting Started