STRtree vs R-tree for Label Collision Detection

For label collision detection, use Shapely’s STRtree when the placed-label set is bulk-loaded once and never changes — it has the fastest build and the tightest query nodes but is immutable, with no incremental insert. Use an rtree/libspatialindex index when placement commits labels one at a time and the obstacle set must grow (or shrink) during the pass, because it supports in-place insert and delete without a full rebuild. The decision is not about raw query speed — both answer a bounding-box query in O(log N) — it is about how the index is mutated as your greedy placer runs.

Core Algorithm and Workflow

A collision-detection index answers one question repeatedly: does this candidate label box intersect any already-placed box? Both structures group bounding boxes into a balanced tree of minimum bounding rectangles (MBRs), so a query descends only the branches whose MBRs overlap the candidate. The difference is entirely in the write path.

STRtree uses Sort-Tile-Recursive packing: it sorts every box up front, tiles them into leaf nodes, and builds the tree bottom-up in one pass. That produces minimal node overlap and the fastest construction — but the packing assumes the full set is known, so the tree is frozen the moment it is built. A dynamic R-tree instead inserts boxes one at a time, splitting and rebalancing nodes on the fly, which costs more per box but leaves the structure open to mutation.

Static STRtree bulk-load versus dynamic R-tree incremental insert Two index structures compared. On the left, a Shapely STRtree is built in a single Sort-Tile-Recursive bulk load from a fixed set of boxes and marked immutable. On the right, a dynamic rtree/libspatialindex index accepts insert and delete operations one box at a time as labels are committed. Shapely STRtree bulk-load once, immutable all boxes known up front STR pack root MBR leaf leaf frozen — no insert/delete rtree / libspatialindex incremental insert & delete root MBR leaf leaf commit label → insert(id, bbox) reject label → delete(id, bbox) tree stays live across the pass

That single structural difference drives the whole comparison:

  1. Build cost. STRtree wins decisively for a one-shot build — Sort-Tile-Recursive packing is a single sorted sweep. An rtree index built by per-item insert is slower because each insert may split nodes; its stream-loading constructor narrows the gap when all boxes are known.
  2. Query speed. Roughly comparable. Both descend overlapping MBRs in O(log N). STRtree’s tighter packing gives it a modest edge on selective queries; the difference is usually swamped by how you mutate the index.
  3. Incremental mutation. The deciding factor. Greedy placement commits one label at a time, so the obstacle set grows mid-pass. rtree absorbs each commit with an in-place insert; STRtree forces a full rebuild per commit, turning a placement pass into O(N²).
  4. Memory. STRtree holds the packed nodes plus your Python geometry array. rtree/libspatialindex keeps its own C++ structure (optionally memory-mapped to disk for out-of-core sets), so it scales past RAM but carries per-object overhead.

The placement itself — priority ordering, candidate generation, fallback scaling — is unchanged from Label Collision Avoidance Algorithms; only the index backing the “does this box collide?” check differs.

Production-Ready Python Implementation

The script below wraps both indexes behind one query(bbox) interface, then benchmarks build and query cost separately so you can measure the trade-off on your own data. It uses shapely==2.0.4 and rtree==1.3.0 (which bundles libspatialindex).

import time
import random
from dataclasses import dataclass

from shapely.geometry import box
from shapely.strtree import STRtree
from rtree import index as rtree_index


@dataclass
class Placement:
    """A committed label bounding box and its stable id."""
    id: int
    bbox: object  # shapely Polygon from shapely.geometry.box


class StaticIndex:
    """
    Bulk-loaded Shapely STRtree. Immutable after build: adding a box
    requires discarding and rebuilding the whole tree.
    """

    def __init__(self, placements: list[Placement]):
        self._boxes = [p.bbox for p in placements]
        self._ids = [p.id for p in placements]
        self._tree = STRtree(self._boxes) if self._boxes else None

    def query(self, candidate) -> list[int]:
        if self._tree is None:
            return []
        # Shapely 2.x returns integer positions into self._boxes.
        positions = self._tree.query(candidate, predicate="intersects")
        return [self._ids[i] for i in positions]

    def add(self, placement: Placement) -> None:
        # No in-place insert exists; rebuild from scratch. O(N) per commit.
        self._boxes.append(placement.bbox)
        self._ids.append(placement.id)
        self._tree = STRtree(self._boxes)


class DynamicIndex:
    """
    rtree / libspatialindex Index supporting in-place insert and delete.
    The obstacle set can grow and shrink during a placement pass.
    """

    def __init__(self, placements: list[Placement] | None = None):
        placements = placements or []
        if placements:
            # Stream-loading constructor bulk-packs when boxes are known up front.
            gen = ((p.id, p.bbox.bounds, None) for p in placements)
            self._idx = rtree_index.Index(gen)
        else:
            self._idx = rtree_index.Index()

    def query(self, candidate) -> list[int]:
        # intersection() takes (minx, miny, maxx, maxy) and returns stored ids.
        return list(self._idx.intersection(candidate.bounds))

    def add(self, placement: Placement) -> None:
        # In-place insert; no rebuild. Amortised O(log N).
        self._idx.insert(placement.id, placement.bbox.bounds)

    def remove(self, placement: Placement) -> None:
        self._idx.delete(placement.id, placement.bbox.bounds)


def make_boxes(n: int, extent: float = 10_000.0, size: float = 40.0) -> list[Placement]:
    """Synthesise n non-trivial label boxes in a projected-CRS extent (metres)."""
    rng = random.Random(42)
    out = []
    for i in range(n):
        cx = rng.uniform(0, extent)
        cy = rng.uniform(0, extent)
        out.append(Placement(i, box(cx - size / 2, cy - size / 2,
                                    cx + size / 2, cy + size / 2)))
    return out


def benchmark(n: int) -> None:
    placements = make_boxes(n)
    candidates = [p.bbox for p in make_boxes(n)]  # independent query set

    # --- Build phase (bulk load once) ---
    t0 = time.perf_counter()
    static = StaticIndex(placements)
    t_static_build = time.perf_counter() - t0

    t0 = time.perf_counter()
    dynamic = DynamicIndex(placements)
    t_dynamic_build = time.perf_counter() - t0

    # --- Query phase ---
    t0 = time.perf_counter()
    for c in candidates:
        static.query(c)
    t_static_query = time.perf_counter() - t0

    t0 = time.perf_counter()
    for c in candidates:
        dynamic.query(c)
    t_dynamic_query = time.perf_counter() - t0

    # --- Incremental-commit phase (greedy placement simulation) ---
    # STRtree: rebuild per commit. rtree: in-place insert per commit.
    fresh = make_boxes(n)
    t0 = time.perf_counter()
    incr_static = StaticIndex([])
    for p in fresh:
        incr_static.add(p)          # each add() rebuilds the whole tree
    t_static_incr = time.perf_counter() - t0

    t0 = time.perf_counter()
    incr_dynamic = DynamicIndex()
    for p in fresh:
        incr_dynamic.add(p)         # each add() is an in-place insert
    t_dynamic_incr = time.perf_counter() - t0

    print(f"N={n}")
    print(f"  build   STRtree={t_static_build*1e3:8.2f} ms   "
          f"rtree={t_dynamic_build*1e3:8.2f} ms")
    print(f"  query   STRtree={t_static_query*1e3:8.2f} ms   "
          f"rtree={t_dynamic_query*1e3:8.2f} ms")
    print(f"  commit  STRtree={t_static_incr*1e3:8.2f} ms   "
          f"rtree={t_dynamic_incr*1e3:8.2f} ms")


if __name__ == "__main__":
    for n in (1_000, 5_000, 20_000):
        benchmark(n)

Typical shape of the output: STRtree build is the fastest of the two and query times track each other closely, but the incremental-commit column diverges sharply — STRtree’s per-commit rebuild grows quadratically while rtree’s stays near-linear. That single column is the whole argument: if your placer commits labels progressively, the static index’s build advantage is erased many times over by rebuilds.

Performance Tuning and Cartographic Best Practices

  • Match the index to the mutation pattern, not the dataset size. A 50,000-box obstacle set that never changes is a textbook STRtree win; a 2,000-box set mutated 2,000 times mid-placement belongs in an rtree. Decide on the write path first.
  • Bulk-load the dynamic index when you can. If you happen to know the full obstacle set up front but still want rtree for later deletes, use its stream-loading constructor, Index((id, bbox, None) for ...), rather than a loop of insert calls — it packs in one pass and avoids repeated node splits.
  • Keep your own id-to-object mapping. Neither index returns Shapely geometries. STRtree.query yields array positions and rtree yields the integer ids you supplied, so hold a parallel list or dict. Reusing the feature’s row index as the rtree id keeps delete(id, bbox) cheap when you retract a rejected label.
  • Query with MBRs, refine with the exact predicate. Both indexes test axis-aligned bounding boxes. For rotated or buffered labels the MBR overstates the footprint, so an index hit is a candidate, not a confirmed overlap — confirm it against the true polygon. That refinement step is exactly where rotated-label bugs hide, covered in Debugging Missed Collisions with Rotated Map Labels.
  • Tier the workload to sidestep the rebuild penalty. If you must use STRtree (for example, to stay dependency-free), group placements into priority tiers, bulk-load one tree per tier, and rebuild once per tier rather than once per label — the same tiering the dense-urban resolver in Solving Label Overlap in Dense Urban Maps with Python applies.

Integration and Next Steps

Because both backends sit behind one query(bbox) method, the collision resolver stays index-agnostic — you can swap StaticIndex for DynamicIndex per dataset without touching placement logic. Two integration notes matter in production:

  • Batch renderers with a fixed obstacle layer. When high-priority labels (motorways, boundaries) are pre-placed and frozen before the pass, load them into a single STRtree and query it read-only while a separate DynamicIndex accumulates the labels you place this run. The static layer never rebuilds; only the live layer mutates.
  • Style-engine hand-off. A resolver that commits and retracts labels interactively — as a rule-based styling pass re-evaluates candidates — needs delete, so it must use the rtree backend. This is the natural fit when collision resolution runs inside the styling stage described in Rule-Based Styling Engines, where a later rule can override an earlier placement and the box has to leave the index.

For out-of-core obstacle sets that exceed RAM, libspatialindex can memory-map its structure to disk via rtree.index.Property(); property.dat-backed storage — a path STRtree cannot take, since it materialises every box in Python memory. Start from the mutation pattern, benchmark build and commit separately on representative N, and let the incremental-commit column make the call.

Frequently Asked Questions

Can I add a box to a Shapely STRtree after it is built?

No. In Shapely 2.x the STRtree is immutable once constructed — there is no insert or delete. To add a placed label you rebuild the tree from the full geometry list, which is O(N) per commit and O(N²) across a greedy pass. If you need incremental mutation, use an rtree/libspatialindex Index, which supports insert(id, bbox) and delete(id, bbox) in place.

Does STRtree.query return geometries or indices?

Shapely 2.x STRtree.query returns integer positions into the array you built the tree from, not geometry objects. Pass predicate='intersects' to filter by exact predicate rather than bare bounding-box overlap. The rtree Index.intersection method instead returns the integer ids you supplied at insert time, so you own the id-to-object mapping. Keep a parallel list or dict keyed by position or id.

Why is my rtree index slower to build than STRtree?

Inserting boxes one at a time triggers repeated node splits and rebalancing, so a per-item build is slower than STRtree’s Sort-Tile-Recursive packing. If you have all boxes up front, use the stream-loading constructor, Index((id, bbox, None) for ...), which bulk-packs and closes most of the gap. Reserve per-item insert for the boxes you genuinely discover during placement.

Back to Programmatic Map Styling and Label Automation