# How pdf-inspector Uses Union-Find to Detect Rectangle-Based Tables in PDFs > Discover how pdf-inspector leverages the union-find algorithm to efficiently detect rectangle-based tables in PDFs by clustering overlapping elements using a disjoint-set structure. - Repository: [Firecrawl/pdf-inspector](https://github.com/firecrawl/pdf-inspector) - Tags: internals - Published: 2026-09-02 --- **The union-find algorithm in pdf-inspector detects rectangle-based tables by clustering spatially overlapping PDF rectangles (`re` operators) into connected components using a disjoint-set structure with grid-based bucketing and AABB overlap tests.** The **pdf-inspector** crate from Firecrawl extracts structured tables from PDF documents by treating each page-level rectangle as a potential table cell boundary. To group these rectangles into meaningful clusters, the library implements a high-performance **union-find (disjoint-set)** algorithm that scales linearly even on pages with thousands of vector graphics. This article breaks down the complete detection pipeline as implemented in the source code. ## Rectangle Preprocessing and Filtering Before clustering begins, raw PDF rectangles undergo normalization in the `detect_tables_from_rects` function. This phase corrects negative widths and heights, discards tiny decorative elements, and removes oversized page-background rectangles that would otherwise dominate the clustering. The preprocessing occurs approximately at lines 30–55 in [`src/tables/detect_rects.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/src/tables/detect_rects.rs). Clean, normalized rectangles are then passed into the core union-find pipeline. ## Union-Find Structure Initialization Each rectangle receives an integer index and becomes an independent set in the **UnionFind** structure defined at lines 14–28 of [`detect_rects.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/detect_rects.rs): ```rust // Simplified conceptual view of the UnionFind struct pub struct UnionFind { parent: Vec, rank: Vec, size: Vec, // Tracks component size for capping } ``` The constructor `UnionFind::new(n)` initializes **n** singleton sets. Path compression and union-by-rank keep subsequent `find` and `union` operations nearly O(1). ## Spatial Grid Bucketing for Linear-Time Proximity To avoid O(n²) pairwise comparisons, pdf-inspector maps rectangles to a uniform spatial grid with **64 pt cells** (`CLUSTER_GRID_CELL`). The helper `grid_span` (lines 85–95) computes the inclusive cell range for each rectangle: ```rust // Returns (min_cell, max_cell) or None for "large" rectangles fn grid_span(rect: &PdfRect, cell_size: f64) -> Option<(i32, i32)>; ``` Rectangles spanning too many grid cells are flagged as *large* and handled separately. This bucketing ensures that overlap tests occur only between rectangles occupying the same or adjacent cells. ## In-Cell Pairwise Union with Bounded Work For each occupied grid cell, `union_bucket_pairs` (lines 97–126) iterates through rectangle indices and tests AABB overlap via `rects_overlap` (lines 63–79): ```rust fn rects_overlap(a: &PdfRect, b: &PdfRect, tolerance: f64) -> bool { a.min_x < b.max_x + tolerance && a.max_x > b.min_x - tolerance && a.min_y < b.max_y + tolerance && a.max_y > b.min_y - tolerance } ``` Key safeguards in this phase: - **Pair limit**: `MAX_CLUSTER_PAIRS_PER_CELL` caps comparisons per cell - **Component capping**: If `uf.size[root] >= MAX_CLUSTER_RECTS` (2000), further unions are rejected (lines 107–110) These limits prevent vector drawings or page-spanning shapes from creating massive, non-table clusters. ## Handling Large Rectangles with B-Tree Indexing Large rectangles that escape the coarse grid are processed through `union_rect_against_bands` (lines 128–162). The algorithm maintains three B-tree maps: - `large_x`: indexed by x-coordinate - `large_y`: indexed by y-coordinate - `large_coarse_y`: indexed by y at reduced resolution This structure enables O(N log N) overlap detection against large shapes. Large rectangles are also compared pairwise against each other through the same B-tree mechanism (lines 164–210). ## Extracting Table Clusters from Components After all union operations complete, `cluster_rects` (lines 334–447) groups rectangles by their union-find root: ```rust // Final clustering phase let mut clusters: HashMap> = HashMap::new(); for (i, rect) in rects.iter().enumerate() { let root = uf.find(i); clusters.entry(root).or_default().push(i); } // Filter by minimum size and return as Vec> clusters.into_values() .filter(|c| c.len() >= min_size) // default min_size = 6 .collect() ``` Only components with at least **6 rectangles** survive this filter, yielding candidate table clusters for downstream processing. ## Downstream Table Detection Strategies The rectangle clusters feed into specialized detectors that attempt grid reconstruction: - `detect_direct_rect_table`: builds tables from explicit rectangle grids - `detect_row_stripe_table`: handles row-striped visual patterns - Heuristic fallbacks for incomplete or irregular structures These higher-level functions reside in [`src/tables/mod.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/src/tables/mod.rs) and select the best interpretation of each cluster based on geometric regularity. ## Practical Usage Example ```rust use pdf_inspector::{extractor, detect_tables_from_rects}; // 1. Extract raw elements from PDF page let items = extractor::extract_text_items(&pdf)?; let rects = extractor::extract_rects(&pdf)?; // 2. Run union-find based table detection let (tables, hints) = detect_tables_from_rects(&items, &rects, page_number); // 3. Access structured table data for table in tables { println!("Detected {} × {} table", table.columns.len(), table.rows.len()); for cell in &table.cells { println!(" Cell content: {:?}", cell.content); } } ``` The CLI provides the same functionality: ```bash pdf2md --json document.pdf ``` ## Summary - **Union-find with path compression** provides near-constant-time component merging for overlapping rectangles - **64 pt spatial grid** reduces overlap tests from O(n²) to O(n) by localizing comparisons - **Component size capping** at 2000 rectangles prevents vector graphics from dominating computation - **B-tree indexed large rectangles** maintain O(N log N) performance for page-spanning shapes - **Minimum cluster size filtering** eliminates spurious small groups before grid detection ## Frequently Asked Questions ### What makes union-find suitable for PDF table detection compared to other clustering algorithms? Union-find excels at **incremental, greedy merging** of spatially connected components without requiring pre-specified cluster counts. The disjoint-set structure naturally handles transitive overlap (A touches B, B touches C, therefore A and C belong together) and supports efficient connectivity queries through path-compressed `find` operations. Alternative approaches like DBSCAN or hierarchical clustering would incur higher overhead for the dense, overlapping rectangles typical in PDF tables. ### Why does pdf-inspector use a 64 pt grid cell size specifically? The **64 pt value** balances spatial locality against bucket population. At typical PDF resolutions, 64 pt (~22 mm) spans roughly 2–3 table cells, ensuring that adjacent rectangles in real tables land in the same or neighboring cells without creating excessive per-cell pair counts. The constant `CLUSTER_GRID_CELL` could be tuned for documents with unusually large or small table structures. ### How does the algorithm distinguish between table rectangles and decorative vector graphics? Three mechanisms filter non-table shapes: **preprocessing removes oversized page backgrounds**, **component capping at 2000 rectangles** isolates massive decorative drawings, and **minimum size filtering (≥6 rectangles)** eliminates isolated decorative elements. Surviving clusters must demonstrate geometric regularity in downstream detectors to be recognized as valid tables. ### What causes the O(N log N) complexity for large rectangles instead of O(N²)? Large rectangles bypass the uniform grid and instead use **B-tree maps (`large_x`, `large_y`, `large_coarse_y`)** for range-query-based overlap detection. Each insertion and lookup costs O(log N), and each large rectangle is compared only against spatially proximate candidates retrieved through these ordered indexes. This avoids the quadratic pairwise comparison that would occur if all large rectangles were tested against each other directly.