BoxHash: spatial hash for fast lookup of boxes intersecting a query. More...

#include <pops/mesh/index/box2d.hpp>
#include <pops/mesh/layout/box_array.hpp>
#include <algorithm>
#include <cstdint>
#include <unordered_map>
#include <vector>

Include dependency graph for box_hash.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	pops::BoxHash
	Spatial index of a BoxArray's boxes via a bin grid. More...

Namespaces
namespace	pops

Functions
int	pops::suggest_bin (const BoxArray &ba)
	Recommended bin size for a BoxArray: the largest box extent (at least 1), so that neighboring boxes fall into adjacent bins (memory / selectivity trade-off).

Detailed Description

BoxHash: spatial hash for fast lookup of boxes intersecting a query.

A uniform bin grid (classic spatial-hash technique) maps each bin to the list of boxes that touch it: finding the boxes whose region may intersect a query box becomes ~O(1) per query (the halo-pair search drops from O(N) to ~O(n), n << N). Built ONCE per mesh, reusable as long as it does not change. Non-omission INVARIANT: if a box intersects the query, they share a cell hence a bin -> query() returns a sorted SUPERSET without duplicates, the caller tests the exact intersection.

include/pops/mesh/index/box_hash.hpp File Reference¶

Classes

Namespaces

Functions

Detailed Description