Add geo ranking

1 files changed, 118 insertions, 0 deletions

diff --git a/indexer/cell_coverer.hpp b/indexer/cell_coverer.hpp
index 3b2057c1e7..3a433572ec 100644
--- a/indexer/cell_coverer.hpp
+++ b/indexer/cell_coverer.hpp
@@ -2,9 +2,14 @@
 
 #include "indexer/cell_id.hpp"
 
+#include "geometry/rect2d.hpp"
+
 #include "base/buffer_vector.hpp"
 
+#include "std/array.hpp"
+#include "std/cstdint.hpp"
 #include "std/queue.hpp"
+#include "std/utility.hpp"
 #include "std/vector.hpp"
 
 // TODO: Move neccessary functions to geometry/covering_utils.hpp and delete this file.
@@ -98,3 +103,116 @@ inline void CoverRect(m2::RectD rect, size_t cellsCount, int maxDepth, vector<Ce
     result.push_back(id);
   }
 }
+
+// Covers rect with cells using spiral order starting from the rect center.
+template <typename Bounds, typename CellId>
+void CoverSpiral(m2::RectD rect, int maxDepth, vector<CellId> & result)
+{
+  using Converter = CellIdConverter<Bounds, CellId>;
+
+  enum class Direction : uint8_t
+  {
+    Right = 0,
+    Down = 1,
+    Left = 2,
+    Up = 3
+  };
+
+  CHECK(result.empty(), ());
+  // Cut rect with world bound coordinates.
+  if (!rect.Intersect(Bounds::FullRect()))
+    return;
+  CHECK(rect.IsValid(), ());
+
+  auto centralCell = Converter::ToCellId(rect.Center().x, rect.Center().y);
+  while (centralCell.Level() > maxDepth && centralCell.Level() > 0)
+    centralCell = centralCell.Parent();
+
+  if (centralCell.Level() > maxDepth)
+    return;
+
+  result.push_back(centralCell);
+
+  // Area around CentralCell will be covered with surrounding cells.
+  //
+  //          * -> * -> * -> *
+  //          ^              |
+  //          |              V
+  //          *    C -> *    *
+  //          ^         |    |
+  //          |         V    V
+  //          * <- * <- *    *
+  //
+  // To get the best ranking quality we should use the smallest cell size but it's not
+  // efficient because it generates too many index requests. To get good quality-performance
+  // tradeoff we cover area with |maxCount| small cells, then increase cell size and cover
+  // area with |maxCount| bigger cells. We increase cell size until |rect| is covered.
+  // We start covering from the center each time and it's ok for ranking because each object
+  // appears in result at most once.
+  // |maxCount| may be adjusted after testing to ensure better quality-performance tradeoff.
+  uint32_t constexpr maxCount = 64;
+
+  auto const nextDirection = [](Direction direction) {
+    return static_cast<Direction>((static_cast<uint8_t>(direction) + 1) % 4);
+  };
+
+  auto const nextCoords = [](pair<int32_t, int32_t> const & xy, Direction direction, uint32_t step) {
+    auto res = xy;
+    switch (direction)
+    {
+    case Direction::Right: res.first += step; break;
+    case Direction::Down: res.second -= step; break;
+    case Direction::Left: res.first -= step; break;
+    case Direction::Up: res.second += step; break;
+    }
+    return res;
+  };
+
+  auto const coordsAreValid = [](pair<int32_t, int32_t> const & xy) {
+    return xy.first >= 0 && xy.second >= 0 && xy.first <= CellId::MAX_COORD &&
+           xy.second <= CellId::MAX_COORD;
+  };
+
+  m2::RectD coveredRect;
+  static_assert(CellId::MAX_COORD == static_cast<int32_t>(CellId::MAX_COORD), "");
+  while (centralCell.Level() > 0 && !coveredRect.IsRectInside(rect))
+  {
+    uint32_t count = 0;
+    auto const centerXY = centralCell.XY();
+    // We support negative coordinates while covering and check coordinates validity before pushing
+    // cell to |result|.
+    pair<int32_t, int32_t> xy{centerXY.first, centerXY.second};
+    auto direction = Direction::Right;
+    int sideLength = 1;
+    // Indicates whether it is the first pass with current |sideLength|. We use spiral cells order and
+    // must increment |sideLength| every second side pass. |sideLength| and |direction| will behave like:
+    // 1 right, 1 down, 2 left, 2 up, 3 right, 3 down, etc.
+    bool evenPass = true;
+    while (count <= maxCount && !coveredRect.IsRectInside(rect))
+    {
+      for (int i = 0; i < sideLength; ++i)
+      {
+        xy = nextCoords(xy, direction, centralCell.Radius() * 2);
+        if (coordsAreValid(xy))
+        {
+          auto const cell = CellId::FromXY(xy.first, xy.second, centralCell.Level());
+          double minCellX, minCellY, maxCellX, maxCellY;
+          Converter::GetCellBounds(cell, minCellX, minCellY, maxCellX, maxCellY);
+          auto const cellRect = m2::RectD(minCellX, minCellY, maxCellX, maxCellY);
+          coveredRect.Add(cellRect);
+
+          if (rect.IsIntersect(cellRect))
+            result.push_back(cell);
+        }
+        ++count;
+      }
+
+      if (!evenPass)
+        ++sideLength;
+
+      direction = nextDirection(direction);
+      evenPass = !evenPass;
+    }
+    centralCell = centralCell.Parent();
+  }
+}