meshspatialgrid.h

Go to the documentation of this file.

 
#ifndef OPENSWMMVIS_LAYERS_MESHSPATIALGRID_H
#define OPENSWMMVIS_LAYERS_MESHSPATIALGRID_H
 
#include <QRectF>
#include <QVector>
#include <QtGlobal>
 
#include <algorithm>
#include <cmath>
#include <vector>
 
struct MeshSpatialGrid
{
    // ── Grid geometry (read-only after rebuild) ───────────────────────
    QRectF extent;
    double cellW = 0.0;
    double cellH = 0.0;
    int    cols  = 0;
    int    rows  = 0;
 
    // ── CSR cell-occupancy storage ────────────────────────────────────
    // cellOffsets has size (cols * rows) + 1 when populated; the trailing
    // sentinel equals cellIndices.size(), so range [offsets[k],
    // offsets[k+1]) inside cellIndices is always a valid (possibly empty)
    // slice for cell k.
    QVector<int> cellOffsets;
    QVector<int> cellIndices;
 
    // ── query() scratch state ─────────────────────────────────────────
    // Sized once in rebuild() and reused for every query. Bumping `epoch`
    // is an O(1) reset of the visited set. On wrap (every ~4B queries)
    // a single fill restores invariants. See query() for details.
    int                          avgPerCell = 0;
    mutable std::vector<quint32> seen;
    mutable quint32              epoch = 0;
 
    void clear()
    {
        extent = {};
        cellW = cellH = 0.0;
        cols  = rows  = 0;
        cellOffsets.clear();
        cellIndices.clear();
        seen.clear();
        epoch      = 0;
        avgPerCell = 0;
    }
 
    [[nodiscard]] bool isEmpty() const { return cellOffsets.isEmpty(); }
 
    void rebuild(const QVector<QRectF> &bboxes);
 
    [[nodiscard]] QVector<int> query(const QRectF &rect) const;
 
    inline void candidatesAtPoint(double x, double y,
                                  const int *&begin, const int *&end) const
    {
        begin = end = nullptr;
        if (cellOffsets.isEmpty() || !std::isfinite(x) || !std::isfinite(y))
            return;
        const int cx = std::clamp(int(std::floor((x - extent.left()) / cellW)), 0, cols - 1);
        const int cy = std::clamp(int(std::floor((y - extent.top())  / cellH)), 0, rows - 1);
        const int  k = cy * cols + cx;
        const int *d = cellIndices.constData();
        begin = d + cellOffsets[k];
        end   = d + cellOffsets[k + 1];
    }
};
 
#endif // OPENSWMMVIS_LAYERS_MESHSPATIALGRID_H