# How the knn_connection Algorithm Finds Neighboring Bounding Boxes in doc2graph

> Learn how the knn_connection algorithm in doc2graph builds a spatial kNN graph using projection maps, expanding search windows, and Euclidean distance to find neighboring bounding boxes.

- Repository: [Andrea Gemelli/doc2graph](https://github.com/andreagemelli/doc2graph)
- Tags: internals
- Published: 2026-02-24

---

**The `knn_connection` method in [`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py) constructs a spatial k‑nearest‑neighbour graph by building axis‑aligned projection maps, dynamically expanding an aspect‑ratio‑aware search window to gather candidates, intersecting vertical and horizontal projections, and ranking the closest *k* neighbors by Euclidean distance.**

The `knn_connection` algorithm serves as the spatial backbone of the `andreagemelli/doc2graph` repository, transforming raw document bounding boxes into graph edges that represent physical proximity. Unlike naive pairwise distance computations, this implementation leverages projection‑based spatial indexing and adaptive window expansion to efficiently identify neighboring boxes. Understanding how `knn_connection` finds neighboring bounding boxes is essential for optimizing document understanding pipelines that rely on graph neural networks.

## Four-Stage Neighbor Detection Pipeline

The algorithm processes bounding boxes through four distinct computational stages defined in [`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py), each optimized to reduce the search space before performing expensive distance calculations.

### Building Projection Maps for Spatial Indexing

In the initialization phase (lines 30‑42), `knn_connection` constructs two auxiliary data structures that map spatial coordinates to bounding box indices:

- **`vertical_projections`**: A list of length *width* where each index stores the IDs of boxes intersecting that x‑coordinate.
- **`horizontal_projections`**: A list of length *height* where each index stores the IDs of boxes intersecting that y‑coordinate.

These maps are populated in a single pass over all bounding boxes, enabling O(1) lookup of boxes intersecting any given axis line. This projection strategy eliminates the need to compare every box against every other box during the neighbor search phase.

### Dynamic Window‑Based Candidate Collection

For each reference box, the algorithm expands a rectangular search window until it contains at least *k* candidate neighbors (lines 53‑84). The window expansion logic incorporates several adaptive mechanisms:

- **`window_multiplier`**: The window size grows multiplicatively each iteration until sufficient candidates are found or a maximum size threshold is reached.
- **Aspect ratio awareness**: The offset applied in x and y directions scales according to the box’s aspect ratio (wider vs. taller), maintaining a roughly square visual search area regardless of box orientation.
- **Projection queries**: Using the pre‑computed maps, the algorithm retrieves `vertical_bboxs` (boxes intersecting the window’s x‑range) and `horizontal_bboxs` (boxes intersecting the window’s y‑range).

This windowed approach ensures that the algorithm only considers spatially relevant candidates rather than the entire document population.

### Intersecting Vertical and Horizontal Candidates

Once candidate sets are retrieved, the algorithm computes their intersection (lines 94‑100) to produce the raw neighbor set. Only boxes that appear in both the vertical and horizontal projections—meaning they actually overlap the search window in 2D space—are retained. The implementation removes duplicate entries and explicitly excludes the reference box itself from consideration, ensuring that a node never connects to itself.

### Distance‑Based Final Selection

With the filtered candidate set, `knn_connection` computes the precise Euclidean distance between box centers using the `polar` function imported from [`doc2graph/data/utils.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/utils.py) (lines 102‑118). The ranking process follows these steps:

1. Calculate polar distance from the reference box center to each candidate center.
2. Sort candidates by ascending distance.
3. Select the first *k* entries as final neighbors.
4. Append bidirectional edges (`[src, dst]` and `[dst, src]`) to the edge lists, avoiding duplicate connections.

The method ultimately returns two parallel lists—`u` (source node indices) and `v` (target node indices)—that conform to DGL’s graph construction API.

## Practical Implementation Example

The following example demonstrates how to invoke the `knn_connection` algorithm directly using the `GraphBuilder` class:

```python
from doc2graph.data.graph_builder import GraphBuilder

# Initialise the builder (configuration reads `edge_type = "knn"` from YAML)

builder = GraphBuilder()

# Prepare bounding boxes as [xmin, ymin, xmax, ymax] in pixel coordinates

boxes = [
    [30, 120, 210, 180],
    [220, 115, 400, 190],
    [45, 250, 190, 310],
    # … additional boxes …

]

# Execute k‑NN connection with k=5 neighbors

src_nodes, dst_nodes = builder.knn_connection(size=(800, 600), bboxs=boxes, k=5)

print("Source indices:", src_nodes)
print("Destination indices:", dst_nodes)

```

The returned index pairs integrate directly with Deep Graph Library (DGL):

```python
import dgl
import torch

# Construct the graph from edge lists

g = dgl.graph(
    (torch.tensor(src_nodes), torch.tensor(dst_nodes)),
    num_nodes=len(boxes),
    idtype=torch.int32
)
print(g)

```

## Key Source Files and Functions

- **[`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py)**: Contains the `knn_connection` method (lines 30‑118) implementing projection maps, window expansion, and distance ranking.
- **[`doc2graph/data/utils.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/utils.py)**: Defines the `polar` function used for Euclidean distance calculation between bounding box centers.
- **[`doc2graph/utils.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/utils.py)**: Provides the `get_config` helper that reads `edge_type` configuration from YAML files.
- **[`doc2graph/main.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/main.py)**: Entry point that orchestrates graph creation and selects between `fully` connected and `knn` edge generation strategies.

## Summary

- **Projection indexing**: `knn_connection` builds `vertical_projections` and `horizontal_projections` arrays (lines 30‑42) to enable constant‑time spatial lookups.
- **Adaptive search windows**: The algorithm expands aspect‑ratio‑aware windows (lines 53‑84) until capturing at least *k* candidate neighbors.
- **Intersection filtering**: Only boxes appearing in both vertical and horizontal projections are considered valid candidates (lines 94‑100).
- **Exact distance ranking**: Final neighbor selection uses the `polar` distance metric (lines 102‑118) to return the closest *k* boxes as bidirectional DGL‑compatible edge lists.

## Frequently Asked Questions

### What is the purpose of the projection maps in knn_connection?

The projection maps serve as spatial indexes that allow the algorithm to retrieve candidate boxes intersecting specific x or y coordinates in O(1) time. By building `vertical_projections` and `horizontal_projections` arrays during initialization (lines 30‑42), `knn_connection` avoids brute‑force O(n²) comparisons and quickly narrows the search space to boxes within the current window region.

### How does the search window adapt to different bounding box shapes?

The window expansion logic incorporates the box’s aspect ratio to determine x and y offset multipliers (lines 53‑84). Wider boxes receive greater horizontal expansion relative to vertical, while taller boxes receive the opposite, ensuring the search window maintains a visually square proportion regardless of the reference box’s dimensions.

### Why does the algorithm intersect vertical and horizontal projections?

The intersection operation (lines 94‑100) acts as a coarse geometric filter. A box must intersect both the vertical and horizontal ranges of the search window to occupy the 2D spatial region, eliminating boxes that merely align on one axis but lie far outside the actual rectangular window. This step significantly reduces the number of expensive distance calculations required.

### What distance metric does knn_connection use to rank neighbors?

The algorithm uses Euclidean distance between bounding box centers, computed via the `polar` function defined in [`doc2graph/data/utils.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/utils.py). This distance metric (invoked at lines 102‑118) measures the straight‑line spatial separation in the document image plane, ensuring that selected neighbors represent the physically closest elements.