# How Rect‑Based Table Detection Works in pdf‑inspector: A Deep Dive into PDF Rectangle Operators

> Discover how pdf-inspector performs rect-based table detection by clustering PDF rectangle operators. Learn about its multi-stage pipeline for accurate table reconstruction.

- Repository: [Firecrawl/pdf-inspector](https://github.com/firecrawl/pdf-inspector)
- Tags: deep-dive
- Published: 2026-09-01

---

**pdf‑inspector detects tables by clustering explicit rectangle (`re`) drawing operators from PDF content streams through a multi‑stage pipeline involving spatial indexing, union‑find clustering, and grid‑based table reconstruction.**

The `pdf-inspector` Rust library implements a sophisticated rect‑based table detection system in [`src/tables/detect_rects.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/src/tables/detect_rects.rs). This approach targets PDFs where table cells are explicitly drawn as rectangular borders—a common pattern in generated PDFs from spreadsheets, reports, and data exports. The system processes raw PDF geometry operators, filters noise, clusters related rectangles, and attempts multiple table reconstruction strategies before falling back to heuristic hints.

## Overview of the Detection Pipeline

The entry point `detect_tables_from_rects` orchestrates nine distinct processing stages. Each stage progressively refines rectangle data toward structured table output or diagnostic hints for downstream detectors.

### Stage 1: Normalize and Filter Raw Rectangles

PDF content streams often contain malformed or decorative rectangle operators. The first pass corrects negative widths and heights, removes tiny decorations below a size threshold, and strips obvious page‑spanning backgrounds via `without_page_backgrounds`.

```rust
// From detect_tables_from_rects, lines 36-49
let rects: Vec<_> = rects
    .into_iter()
    .map(|r| r.normalize())  // Fixes negative dimensions
    .filter(|r| r.area() > MIN_RECT_AREA)  // Drop decorations
    .collect();

```

Lines 52‑66 implement additional filtering, while lines 70‑84 handle background removal. This normalization ensures downstream clustering operates on geometrically valid, semantically meaningful rectangles.

### Stage 2: Remove Oversized Background Fills

Large filled rectangles often represent section backgrounds rather than cell borders. The code computes the **median cell width** from all remaining rects, then discards any rectangle exceeding **10× that median**.

```rust
// Lines 77-84: Median-based size filtering
let median_width = compute_median_width(&rects);
let max_allowed_width = median_width * 10.0;
let rects: Vec<_> = rects
    .into_iter()
    .filter(|r| r.width() <= max_allowed_width)
    .collect();

```

This statistical approach adapts to document scale without hardcoded thresholds.

### Stage 3: Deduplicate Sub‑Rectangles

Nested or overlapping rectangles from adjacent drawing commands produce spurious edge detections. The algorithm identifies small rectangles fully contained within slightly larger ones (height ratio < 4) and drops the smaller copy. Lines 95‑126 implement this containment check with tolerance‑aware geometry.

## Spatial Clustering with Union‑Find

The core grouping algorithm uses **disjoint‑set (union‑find) data structures** combined with spatial hashing for near‑linear performance.

### Grid Bucketing for Scalable Overlap Detection

Rather than testing all rectangle pairs (O(n²)), `cluster_rects` assigns rectangles to a uniform **64‑point grid**. Overlap tests occur only within shared grid cells, with a per‑cell pair limit (`MAX_CLUSTER_PAIRS_PER_CELL`) preventing pathological cases.

```rust
// Lines 81-95: Grid coordinate utilities
fn grid_coord(x: f32, cell_size: f32) -> i32 {
    (x / cell_size).floor() as i32
}

fn grid_span(min: f32, max: f32, cell_size: f32) -> RangeInclusive<i32> {
    // Returns inclusive cell indices for a coordinate range
    grid_coord(min, cell_size)..=grid_coord(max, cell_size)
}

```

### Handling Large Rectangles

Rectangles spanning more than 64 grid cells bypass the standard bucketing to avoid memory explosion. These "large" rectangles route through auxiliary maps (`large_x`, `large_y`, `large_coarse_y`) and merge in linear‑time passes (lines 65‑73, 124‑170).

### Union‑Find Implementation

The `UnionFind` struct (lines 14‑55) manages component merging with path compression:

```rust
pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<u8>,
    size: Vec<usize>,
}

impl UnionFind {
    pub fn find(&mut self, x: usize) -> usize {
        // Path compression for amortized O(α(n)) lookup
    }
    
    pub fn union(&mut self, x: usize, y: usize) {
        // Union by rank, with size tracking
    }
}

```

Two rectangles union when `rects_overlap` (lines 63‑79) returns true—an AABB test with tolerance scaling (`tolerance * 4.0`).

### Component Formation

After all unions complete, lines 332‑347 gather root nodes and filter components below `min_size` (default 6 rectangles). This eliminates isolated drawing artifacts from genuine table structures.

## Table Construction Strategies

Each surviving rect cluster feeds into progressive table detectors:

### Direct Rectangle Table Detection

`detect_direct_rect_table` (lines 576‑584) attempts three strategies in order:

1. **Full grid**: Requires consistent row and column alignment across all rectangles
2. **Row stripe**: Horizontal cell bands with varying column counts per row
3. **Stacked boxes**: Independent rectangular regions treated as sub‑tables

### Wide‑Cluster Splitting

When direct detection fails on broad clusters, `split_wide_cluster` (lines 49‑112, invoked at lines 588‑610) finds the largest X‑axis gap and recursively detects tables in each partition:

```rust
// Conceptual flow from lines 588-610
if let Some(split_point) = find_largest_x_gap(&cluster) {
    let (left, right) = split_at_gap(cluster, split_point);
    detect_tables_from_rects_on(left);
    detect_tables_from_rects_on(right);
}

```

### Fallback Merge

If individual clusters yield only narrow tables (≤ 3 columns) or no tables, the algorithm merges **all clusters** and runs a row‑stripe detector on the combined geometry (lines 686‑724). This handles fragmented table borders that survive initial clustering as separate components.

## Hint Generation for Heuristic Detection

Clusters that resist all table construction become `RectHintRegion` outputs (lines 740‑815, 836‑876). These bounding boxes guide the later **heuristic detector**—a separate subsystem analyzing text alignment and spacing rather than explicit graphics.

```rust
// Output types from detect_tables_from_rects
pub struct RectHintRegion {
    pub bbox: Rect,
    pub confidence: f32,
    pub source_cluster_size: usize,
}

```

This cooperation between explicit‑geometry and heuristic detection maximizes recall across diverse PDF generation patterns.

## Public API and Usage

The rustdoc‑friendly interface exposes detection through `pdf_inspector::extractor`:

```rust
use pdf_inspector::extractor::detect_tables_from_rects;

// Items: extracted text positions from the PDF
// Rects: PdfRect objects from `re` operators in content stream
// page: 0-based page index
let (tables, hint_regions) = detect_tables_from_rects(
    &page_text_items,
    &page_rects,
    page_number,
);

```

Return values:

- **`tables`**: Complete `Table` structures with column/row indexing and cell text assignment
- **`hint_regions`**: Localized search regions for downstream heuristic processing

## Integration in the pdf2md Binary

The production `pdf2md` tool orchestrates three detection strategies:

```rust
// From src/extractor/mod.rs conceptual flow
let (rect_tables, hints) = detect_tables_from_rects(&items, &rects, page);
if !rect_tables.is_empty() {
    return rect_tables;  // Prefer explicit geometry
}

let line_tables = detect_tables_from_lines(&items, &lines);
let heuristic_tables = detect_tables_heuristic(&items, hints);

// Merge or select best results...

```

This cascading approach prioritizes high‑precision rect‑based results while maintaining coverage through alternative methods.

## Key Implementation Limits

| Parameter | Default | Purpose |
|-----------|---------|---------|
| `CLUSTER_GRID_CELL` | 64 pt | Spatial hashing resolution |
| `MAX_CLUSTER_PAIRS_PER_CELL` | — | Prevents quadratic blow‑up within cells |
| `MAX_CLUSTER_RECTS` | 2000 | Caps union‑find component size |
| `min_size` | 6 rects | Minimum cluster size for table consideration |

These safeguards ensure robust performance on vector‑heavy PDFs with thousands of drawing operators.

## Summary

- **Rect‑based detection** in pdf‑inspector operates on explicit PDF `re` operators, making it highly precise for bordered tables
- The **nine‑stage pipeline** progressively filters noise, clusters spatially related rectangles, and attempts multiple reconstruction strategies
- **Union‑find with 64‑pt grid bucketing** achieves near‑linear clustering performance while handling pathological inputs through size limits and large‑rect special cases
- Three **table construction strategies** (full grid, row stripe, stacked boxes) accommodate diverse table layouts, with recursive splitting for wide clusters
- **Hint generation** bridges to heuristic detection when explicit geometry proves insufficient
- The public API at `detect_tables_from_rects` returns both completed tables and diagnostic regions, supporting flexible downstream processing

## Frequently Asked Questions

### What types of PDFs work best with rect‑based table detection?

PDFs generated from structured data sources—spreadsheets, database reports, and document generators—typically draw explicit cell borders with `re` operators. Scanned documents, HTML‑to‑PDF conversions with CSS borders, and presentation exports may lack these operators entirely, requiring the heuristic or line‑based detectors instead.

### How does pdf‑inspector handle overlapping or nested tables?

The **deduplication stage** (lines 95‑126) removes contained sub‑rectangles, while the **wide‑cluster splitting** mechanism partitions horizontally separated tables that share vertical overlap. Tables stacked vertically typically separate during grid bucketing due to Y‑axis cell boundaries. The fallback merge (lines 686‑724) can recombine erroneously split fragments when both halves produce weak results.

### Why does the union‑find cluster cap at 2000 rectangles?

`MAX_CLUSTER_RECTS = 2000` prevents runaway memory and CPU consumption on decorative vector graphics or complex illustrations misinterpreted as rectangle operators. According to the source in [`src/tables/detect_rects.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/src/tables/detect_rects.rs), this limit has proven sufficient for production tables while excluding pathological PDFs that would otherwise stall processing.