Spatial Predicates and R-tree Indexing#

This article covers the low-level geometric machinery used by Docling's rule-based reading order prediction: epsilon-tolerant spatial predicates defined on BoundingBox (in docling-core) and an R-tree spatial index built and queried inside ReadingOrderPredictor (in docling-ibm-models). Understanding both layers — and the mismatch between them — is essential for debugging incorrect reading order or contributing to the ordering algorithm.

Key files:

• docling_core/types/doc/base.py — BoundingBox spatial predicate methods
• docling_ibm_models/reading_order/reading_order_rb.py — PageElement, ReadingOrderPredictor, R-tree construction and queries

Epsilon-Tolerant Spatial Predicates#

All spatial predicates live on BoundingBox in docling_core/types/doc/base.py. The "strict" variants apply a small epsilon tolerance so that elements touching at a boundary are still considered ordered — not merely adjacent.

Key predicate methods:

Coordinate-origin semantics matter. is_strictly_above has different logic for BOTTOMLEFT (higher b = higher on page) vs. TOPLEFT (lower t = higher on page) 1. All comparisons raise ValueError if origins differ. The reading-order predictor normalizes all elements to BOTTOMLEFT before processing 2.

The eps default (1.0e-3) is set as a class-level attribute on PageElement, which extends BoundingBox. Callers can override it per-call, but the reading order predictor always uses the default.

R-tree Spatial Index#

The R-tree (from the rtree package) is constructed inside _init_ud_maps to avoid O(n²) candidate enumeration.

Index construction 3:

spatial_idx = rtree_index.Index()
for i, pelem in enumerate(page_elems):
    spatial_idx.insert(i, (pelem.l, pelem.b, pelem.r, pelem.t))

Coordinates are inserted as raw floats in (l, b, r, t) order — matching BOTTOMLEFT convention.

"Above" candidate query 4:

query_bbox = (pelem_j.l - 0.1, pelem_j.t, pelem_j.r + 0.1, float("inf"))
candidates = list(spatial_idx.intersection(query_bbox))

This asks: which elements have any part above pelem_j.t? The ±0.1 horizontal expansion captures elements that are nearly (but not exactly) x-aligned.

Interruption detection also uses the R-tree: _has_sequence_interruption queries a bounding box spanning the vertical gap between two elements to find any third element that would break their predecessor–successor link.

The Raw vs. Epsilon-Adjusted Inconsistency#

The critical subtlety: the R-tree is indexed and queried with raw coordinates, but the predicate checks that follow apply epsilon offsets.

After the R-tree returns candidates for element j, the code checks 5:

if not (
    pelem_i.is_strictly_above(pelem_j) # uses eps = 1e-3
    and pelem_i.overlaps_horizontally(pelem_j)
):
    continue

This creates two categories of mismatch for near-boundary element pairs:

1. False positives from the R-tree — an element i enters the candidate set (its raw t is above raw pelem_j.t) but fails is_strictly_above after epsilon adjustment. Handled gracefully: the predicate check discards it.

2. False negatives from the R-tree — an element i whose raw b is just below pelem_j.t is not returned by the R-tree, but is_strictly_above would return True with the epsilon bump. This element is silently missed and no predecessor–successor edge is created.

The second case can produce incorrect reading order on pages where layout boxes sit nearly flush — a situation that can arise from floating-point rounding in upstream PDF coordinate extraction or layout model output. There is currently no guard in the code to detect or log these near-miss cases.

Additionally, the R-tree library itself requires b ≤ t for BOTTOMLEFT boxes (i.e., the second coordinate ≤ fourth coordinate). If coordinate normalization is incomplete or epsilon adjustment produces a degenerate box before insertion, the R-tree may raise or silently misindex the entry.

Quick Reference: Where to Look#