include/pops/mesh/index/box_hash.hpp Source FileΒΆ

adc_cpp: include/pops/mesh/index/box_hash.hpp Source File
adc_cpp 0.3.0
Model-free C++23 core for coupled hyperbolic-elliptic systems on adaptive (AMR) meshes, with MPI and GPU (Kokkos) backends
box_hash.hpp
Go to the documentation of this file.
1
10
11#pragma once
12
13#include <pops/mesh/index/box2d.hpp>
14#include <pops/mesh/layout/box_array.hpp>
15
16#include <algorithm>
17#include <cstdint>
18#include <unordered_map>
19#include <vector>
20
21namespace pops {
22
26class BoxHash {
27 public:
30 BoxHash(const BoxArray& ba, int bin) : bin_(bin > 0 ? bin : 1) {
31 for (int i = 0; i < ba.size(); ++i) {
32 const Box2D& b = ba[i];
33 for (int by = fdiv(b.lo[1]); by <= fdiv(b.hi[1]); ++by)
34 for (int bx = fdiv(b.lo[0]); bx <= fdiv(b.hi[0]); ++bx)
35 bins_[key(bx, by)].push_back(i);
36 }
37 }
38
41 std::vector<int> query(const Box2D& q) const {
42 std::vector<int> out;
43 if (q.empty())
44 return out;
45 for (int by = fdiv(q.lo[1]); by <= fdiv(q.hi[1]); ++by)
46 for (int bx = fdiv(q.lo[0]); bx <= fdiv(q.hi[0]); ++bx) {
47 auto it = bins_.find(key(bx, by));
48 if (it != bins_.end())
49 out.insert(out.end(), it->second.begin(), it->second.end());
50 }
51 std::sort(out.begin(), out.end());
52 out.erase(std::unique(out.begin(), out.end()), out.end());
53 return out;
54 }
55
56 private:
57 // bin index = integer division by bin_ rounded down (toward -inf) (handles negative coords).
58 // Thin adapter over floor_div (box2d.hpp): bin_ > 0 (forced by the constructor) -> result
59 // bit-identical to the old x >= 0 ? x / bin_: -((-x + bin_ - 1) / bin_).
60 int fdiv(int x) const { return floor_div(x, bin_); }
61 static std::int64_t key(int bx, int by) {
62 return (static_cast<std::int64_t>(bx) << 32) |
63 (static_cast<std::int64_t>(static_cast<std::uint32_t>(by)) & INT64_C(0xffffffff));
64 }
65
66 int bin_;
67 std::unordered_map<std::int64_t, std::vector<int>> bins_;
68};
69
72inline int suggest_bin(const BoxArray& ba) {
73 int m = 1;
74 for (int i = 0; i < ba.size(); ++i)
75 m = std::max({m, ba[i].nx(), ba[i].ny()});
76 return m;
77}
78
79} // namespace pops
box2d.hpp
Box2D: the integer index space of a 2D cell-centered Cartesian grid.
box_array.hpp
BoxArray: the set of boxes tiling a level (disjoint, covering).
pops::BoxArray
Ordered list of boxes tiling a level.
Definition box_array.hpp:22
pops::BoxArray::size
int size() const
Number of boxes in the tiling.
Definition box_array.hpp:42
pops::BoxHash
Spatial index of a BoxArray's boxes via a bin grid.
Definition box_hash.hpp:26
pops::BoxHash::BoxHash
BoxHash(const BoxArray &ba, int bin)
Builds the index: bin = side of a bin (cells); bin <= 0 forces bin = 1.
Definition box_hash.hpp:30
pops::BoxHash::query
std::vector< int > query(const Box2D &q) const
Indices (SORTED, without duplicates) of the boxes that may intersect q: guaranteed SUPERSET (no inter...
Definition box_hash.hpp:41
pops
Definition amr_hierarchy.hpp:29
pops::floor_div
POPS_HD constexpr int floor_div(int a, int b)
Integer division of a by b rounded down (handles a < 0 AND b < 0). POPS_HD constexpr (kernels).
Definition box2d.hpp:28
pops::suggest_bin
int suggest_bin(const BoxArray &ba)
Recommended bin size for a BoxArray: the largest box extent (at least 1), so that neighboring boxes f...
Definition box_hash.hpp:72
pops::Box2D
2D integer index space, cell-centered.
Definition box2d.hpp:37
pops::Box2D::empty
bool empty() const
true if the box contains no cell (hi < lo in one direction).
Definition box2d.hpp:58
pops::Box2D::hi
int hi[2]
Definition box2d.hpp:39
pops::Box2D::lo
int lo[2]
Definition box2d.hpp:38
Generated by doxygen 1.9.8