TiledGrid.h

#pragma once
 
#include "HashGrid.h"
 
#include <algorithm>
#include <array>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <span>
#include <vector>
 
namespace environment::field::aggregation
{
 
[[nodiscard]] double MedianLongerSide(std::span<const Box> boxes);
 
class TiledGrid
{
public:
   static constexpr int kTileSide = 8;
   static constexpr int kTileCells = kTileSide * kTileSide;
 
   struct Item
   {
      std::uint32_t id = 0;
      Box           box;
   };
 
   TiledGrid() = default;
 
   TiledGrid(double xMin, double xMax, double yMin, double yMax, double cellSize);
 
   [[nodiscard]] bool HasExtent() const { return m_nx > 0; }
 
   [[nodiscard]] double CellSize() const { return m_cellSize; }
 
   [[nodiscard]] std::size_t CellCount() const { return static_cast<std::size_t>(m_nx) * static_cast<std::size_t>(m_ny); }
 
   [[nodiscard]] std::size_t TileCount() const { return m_tiles.size(); }
 
   [[nodiscard]] std::size_t SharedTileCount(const TiledGrid& other) const
   {
      std::size_t shared = 0;
      for (std::size_t t = 0; t < std::min(m_tiles.size(), other.m_tiles.size()); ++t) {
         shared += m_tiles[t] != nullptr && m_tiles[t] == other.m_tiles[t] ? 1 : 0;
      }
      return shared;
   }
 
   [[nodiscard]] std::size_t FilledTileCount() const
   {
      return static_cast<std::size_t>(std::count_if(m_tiles.begin(), m_tiles.end(), [](const auto& tile) { return tile != nullptr; }));
   }
 
   [[nodiscard]] std::size_t OverflowCount() const { return m_overflow ? m_overflow->size() : 0; }
 
   [[nodiscard]] bool Inside(const Box& box) const
   {
      return box.xMin >= m_extent.xMin && box.xMax <= m_extent.xMax && box.yMin >= m_extent.yMin && box.yMax <= m_extent.yMax;
   }
 
   [[nodiscard]] TiledGrid With(std::span<const Item> removed, std::span<const Item> added) const;
 
   [[nodiscard]] TiledGrid Cleared() const;
 
   template<class Visitor>
   void ForEachCandidate(const Box& query, Visitor&& visit) const
   {
      if (m_nx > 0) {
         const int ix0 = CellX(query.xMin);
         const int ix1 = CellX(query.xMax);
         const int iy0 = CellY(query.yMin);
         const int iy1 = CellY(query.yMax);
         for (int iy = iy0; iy <= iy1; ++iy) {
            for (int ix = ix0; ix <= ix1; ++ix) {
               const Tile* tile = m_tiles[TileIndex(ix, iy)].get();
               if (tile == nullptr) {
                  continue;
               }
               const std::size_t local = LocalCell(ix, iy);
               for (std::uint32_t k = tile->start[local]; k < tile->start[local + 1]; ++k) {
                  const Entry& e = tile->entries[k];
                  // Report the box in the first cell that the box and the query share.
                  if (std::max(e.ix0, ix0) != ix || std::max(e.iy0, iy0) != iy) {
                     continue;
                  }
                  if (Overlaps(e.box, query)) {
                     visit(e.id);
                  }
               }
            }
         }
      }
      if (m_overflow) {
         for (const Entry& e : *m_overflow) {
            if (Overlaps(e.box, query)) {
               visit(e.id);
            }
         }
      }
   }
 
   void Candidates(const Box& query, std::vector<std::uint32_t>& out) const;
 
private:
   struct Entry
   {
      std::uint32_t id  = 0;
      std::int32_t  ix0 = 0; 
      std::int32_t  iy0 = 0; 
      Box           box;
   };
 
   struct Tile
   {
      std::array<std::uint32_t, kTileCells + 1> start {};
      std::vector<Entry>                        entries;
   };
 
   struct Placed
   {
      std::size_t   tile  = 0;
      std::uint32_t local = 0;
      Entry         entry;
   };
 
   [[nodiscard]] int CellX(double x) const { return CellIndex(x, m_originX, m_nx); }
   [[nodiscard]] int CellY(double y) const { return CellIndex(y, m_originY, m_ny); }
   [[nodiscard]] int CellIndex(double v, double origin, int count) const
   {
      const double cell = std::floor((v - origin) * m_inverseCell);
      return static_cast<int>(std::clamp(cell, 0.0, static_cast<double>(count - 1)));
   }
   [[nodiscard]] std::size_t TileIndex(int ix, int iy) const
   {
      return static_cast<std::size_t>(iy / kTileSide) * static_cast<std::size_t>(m_tilesX) + static_cast<std::size_t>(ix / kTileSide);
   }
   [[nodiscard]] static std::size_t LocalCell(int ix, int iy)
   {
      return static_cast<std::size_t>(iy % kTileSide) * static_cast<std::size_t>(kTileSide) + static_cast<std::size_t>(ix % kTileSide);
   }
 
   void Place(const Item& item, std::vector<Placed>& out) const;
 
   double                                    m_cellSize    = 1.0;
   double                                    m_inverseCell = 1.0;
   double                                    m_originX     = 0.0;
   double                                    m_originY     = 0.0;
   int                                       m_nx          = 0;
   int                                       m_ny          = 0;
   int                                       m_tilesX      = 0;
   Box                                       m_extent;
   std::vector<std::shared_ptr<const Tile>>  m_tiles;    
   std::shared_ptr<const std::vector<Entry>> m_overflow; 
};
 
} // namespace environment::field::aggregation