Restore class Covering.

3 files changed, 419 insertions, 0 deletions

diff --git a/geometry/covering.hpp b/geometry/covering.hpp
new file mode 100644
index 0000000000..44ef105bf2
--- /dev/null
+++ b/geometry/covering.hpp
@@ -0,0 +1,290 @@
+#pragma once
+#include "covering_utils.hpp"
+#include "../geometry/point2d.hpp"
+#include "../base/assert.hpp"
+#include "../base/base.hpp"
+#include "../base/logging.hpp"
+#include "../base/set_operations.hpp"
+#include "../base/stl_add.hpp"
+#include "../std/algorithm.hpp"
+#include "../std/array.hpp"
+#include "../std/functional.hpp"
+#include "../std/iterator.hpp"
+#include "../std/map.hpp"
+#include "../std/queue.hpp"
+#include "../std/utility.hpp"
+#include "../std/vector.hpp"
+
+namespace covering
+{
+
+template <class CellIdT>
+class Covering
+{
+public:
+  typedef CellIdT CellId;
+  typedef typename CellId::LessQueueOrder LessQueueOrder;
+
+  Covering() : m_Size(0) {}
+
+  explicit Covering(CellId cell) : m_Size(1)
+  {
+    m_Covering[cell.Level()].push_back(cell);
+  }
+
+  explicit Covering(vector<CellId> const & v, int64_t minId = 0)
+  {
+    for (size_t i = 0; i < v.size(); ++i)
+      m_Covering[v[i].Level()].push_back(v[i]);
+    Sort();
+    Unique();
+    RemoveDuplicateChildren();
+    RemoveFullSquares(minId);
+    m_Size = CalculateSize();
+  }
+
+  // Cover triangle.
+  Covering(m2::PointD const & a, m2::PointD const & b, m2::PointD const & c,
+           int level = CellId::DEPTH_LEVELS - 1)
+  {
+    // TODO: ASSERT(a != b), ASSERT(b != c), ASSERT(a != c) ?
+    ASSERT(0 <= level && level <= CellId::DEPTH_LEVELS, (level, CellId::Root()));
+    CoverTriangleInfo info;
+    info.m_pCovering = this;
+    info.m_A = a;
+    info.m_B = b;
+    info.m_C = c;
+    info.m_Level = level;
+    CoverTriangleImpl(info, CellId::Root());
+    Sort();
+    RemoveFullSquares();
+    m_Size = CalculateSize();
+  }
+
+  size_t Size() const
+  {
+    ASSERT_EQUAL(m_Size, CalculateSize(), ());
+    return m_Size;
+  }
+
+  void Append(Covering<CellId> const & c)
+  {
+    AppendWithoutNormalize(c);
+    RemoveDuplicateChildren();
+    RemoveFullSquares();
+    m_Size = CalculateSize();
+  }
+
+  void OutputToVector(vector<CellId> & result) const
+  {
+    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
+        result.insert(result.end(), m_Covering[level].begin(), m_Covering[level].end());
+  }
+
+  void OutputToVector(vector<int64_t> & result) const
+  {
+    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
+      for (size_t i = 0; i < m_Covering[level].size(); ++i)
+        result.push_back(m_Covering[level][i].ToInt64());
+  }
+
+  void Simplify(int64_t minId = 0)
+  {
+    int cellsSimplified = 0;
+    int const initialSize = m_Size;
+    for (int level = CellId::DEPTH_LEVELS - 1; level > 1; --level)
+    {
+      if (m_Covering[level].size() >= 2)
+      {
+        int const initialLevelSize = static_cast<int>(m_Covering[level].size());
+        SimplifyLevel(level, minId);
+        cellsSimplified += initialLevelSize - static_cast<int>(m_Covering[level].size());
+        if (cellsSimplified > initialSize / 2)
+          break;
+      }
+    }
+    RemoveDuplicateChildren();
+    RemoveFullSquares(minId);
+    m_Size = CalculateSize();
+  }
+
+private:
+
+  void SimplifyLevel(int level, int64_t minId)
+  {
+    map<CellId, uint32_t, LessQueueOrder> parentCellCounts;
+    typedef typename vector<CellId>::const_iterator ConstIteartor;
+    for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it)
+      if (it->Parent().ToInt64() >= minId)
+        ++parentCellCounts[it->Parent()];
+
+    vector<CellId> parentCells, childCells;
+    for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it)
+    {
+      if (parentCellCounts[it->Parent()] > 1)
+        parentCells.push_back(it->Parent());
+      else
+        childCells.push_back(*it);
+    }
+    ASSERT(IsSorted(parentCells.begin(), parentCells.end(), LessQueueOrder()), (parentCells));
+    ASSERT(IsSorted(childCells.begin(), childCells.end(), LessQueueOrder()), (childCells));
+    m_Covering[level].swap(childCells);
+    parentCells.erase(unique(parentCells.begin(), parentCells.end()), parentCells.end());
+    AppendToVector(m_Covering[level - 1], parentCells);
+  }
+
+  static void AppendToVector(vector<CellId> & a, vector<CellId> const & b)
+  {
+    ASSERT(IsSortedAndUnique(a.begin(), a.end(), LessQueueOrder()), (a));
+    ASSERT(IsSortedAndUnique(b.begin(), b.end(), LessQueueOrder()), (b));
+    vector<CellId> merged;
+    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(merged), LessQueueOrder());
+    a.swap(merged);
+  }
+
+  template <typename CompareT>
+  struct CompareCellsAtLevel
+  {
+    explicit CompareCellsAtLevel(int level) : m_Level(level) {}
+
+    bool operator() (CellId id1, CellId id2) const
+    {
+      return m_Comp(id1.AncestorAtLevel(m_Level), id2.AncestorAtLevel(m_Level));
+    }
+
+    CompareT m_Comp;
+    int m_Level;
+  };
+
+  void AppendWithoutNormalize(Covering const & c)
+  {
+    for (int level = CellId::DEPTH_LEVELS - 1; level >= 0; --level)
+      AppendToVector(m_Covering[level], c.m_Covering[level]);
+  }
+
+  void Sort()
+  {
+    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
+      sort(m_Covering[level].begin(), m_Covering[level].end(), LessQueueOrder());
+  }
+
+  void Unique()
+  {
+    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
+    {
+      vector<CellId> & covering = m_Covering[level];
+      ASSERT(IsSorted(covering.begin(), covering.end(), LessQueueOrder()), (covering));
+      covering.erase(unique(covering.begin(), covering.end()), covering.end());
+    }
+  }
+
+  void RemoveDuplicateChildren()
+  {
+    RemoveDuplicateChildrenImpl();
+#ifdef DEBUG
+    // Assert that all duplicate children were removed.
+    vector<int64_t> v1, v2;
+    OutputToVector(v1);
+    RemoveDuplicateChildrenImpl();
+    OutputToVector(v2);
+    ASSERT_EQUAL(v1, v2, ());
+#endif
+  }
+
+  void RemoveDuplicateChildrenImpl()
+  {
+    for (int parentLevel = 0; parentLevel < static_cast<int>(m_Covering.size()) - 1; ++parentLevel)
+    {
+      if (m_Covering[parentLevel].empty())
+        continue;
+      for (int childLevel = parentLevel + 1; childLevel < static_cast<int>(m_Covering.size());
+           ++childLevel)
+      {
+        vector<CellId> substracted;
+        CompareCellsAtLevel<LessQueueOrder> comparator(parentLevel);
+        ASSERT(IsSorted(m_Covering[childLevel].begin(), m_Covering[childLevel].end(), comparator),
+               (m_Covering[childLevel]));
+        ASSERT(IsSorted(m_Covering[parentLevel].begin(), m_Covering[parentLevel].end(), comparator),
+               (m_Covering[parentLevel]));
+        SetDifferenceUnlimited(m_Covering[childLevel].begin(), m_Covering[childLevel].end(),
+                               m_Covering[parentLevel].begin(), m_Covering[parentLevel].end(),
+                               back_inserter(substracted), comparator);
+        m_Covering[childLevel].swap(substracted);
+      }
+    }
+  }
+
+  void RemoveFullSquares(int64_t minId = 0)
+  {
+    vector<CellId> cellsToAppend;
+    for (int level = m_Covering.size() - 1; level >= 0; --level)
+    {
+      // a -> b + parents
+      vector<CellId> const & a = m_Covering[level];
+      vector<CellId> b;
+      vector<CellId> parents;
+      b.reserve(a.size());
+      for (size_t i = 0; i < a.size(); ++i)
+      {
+        if (i + 3 < a.size())
+        {
+          CellId const parent = a[i].Parent();
+          if (parent == a[i+1].Parent() &&
+              parent == a[i+2].Parent() &&
+              parent == a[i+3].Parent() &&
+              parent.ToInt64() >= minId)
+          {
+            parents.push_back(parent);
+            i += 3;
+            continue;
+          }
+        }
+        b.push_back(a[i]);
+      }
+      m_Covering[level].swap(b);
+      if (level > 0)
+        AppendToVector(m_Covering[level - 1], parents);
+    }
+  }
+
+  size_t CalculateSize() const
+  {
+    size_t size = 0;
+    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
+      size += m_Covering[level].size();
+    return size;
+  }
+
+  struct CoverTriangleInfo
+  {
+    m2::PointD m_A, m_B, m_C;
+    int m_Level;
+    Covering<CellId> * m_pCovering;
+  };
+
+  static void CoverTriangleImpl(CoverTriangleInfo const & info, CellId const cell)
+  {
+    ASSERT_LESS_OR_EQUAL(cell.Level(), info.m_Level, (info.m_A, info.m_B, info.m_C));
+    CellObjectIntersection intersection =
+        IntersectCellWithTriangle(cell, info.m_A, info.m_B, info.m_C);
+
+    if (intersection == CELL_OBJECT_NO_INTERSECTION)
+      return;
+
+    if (cell.Level() == info.m_Level || intersection == CELL_INSIDE_OBJECT)
+    {
+      info.m_pCovering->m_Covering[cell.Level()].push_back(cell);
+      return;
+    }
+
+    for (uint8_t child = 0; child < 4; ++child)
+      CoverTriangleImpl(info, cell.Child(child));
+  }
+
+
+  array<vector<CellId>, CellId::DEPTH_LEVELS> m_Covering; // Covering by level.
+  size_t m_Size;
+};
+
+
+}
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index 27ebf4014e..35986be65f 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -25,6 +25,7 @@ HEADERS += \
   screenbase.hpp \
   cellid.hpp \
   rect_intersect.hpp \
+  covering.hpp \
   covering_utils.hpp \
   packer.hpp \
   pointu_to_uint64.hpp \
diff --git a/geometry/geometry_tests/covering_test.cpp b/geometry/geometry_tests/covering_test.cpp
index e67fc6acfb..a419b4354c 100644
--- a/geometry/geometry_tests/covering_test.cpp
+++ b/geometry/geometry_tests/covering_test.cpp
@@ -1,4 +1,132 @@
 #include "../../testing/testing.hpp"
+#include "../cellid.hpp"
+#include "../covering.hpp"
 #include "../covering_utils.hpp"
+#include "../point2d.hpp"
+#include "../../base/stl_add.hpp"
+
 
 // TODO: Add covering unit tests here.
+
+
+typedef m2::CellId<5> CellId;
+
+UNIT_TEST(CoverTriangle_Simple)
+{
+  vector<CellId> v;
+  covering::Covering<CellId> c(m2::PointD(3*2, 3*2), m2::PointD(4*2, 12*2), m2::PointD(14*2, 3*2));
+  c.OutputToVector(v);
+  vector<CellId> e;
+  e.push_back(CellId("03"));
+  e.push_back(CellId("003"));
+  e.push_back(CellId("012"));
+  e.push_back(CellId("013"));
+  e.push_back(CellId("102"));
+  e.push_back(CellId("103"));
+  e.push_back(CellId("112"));
+  e.push_back(CellId("120"));
+  e.push_back(CellId("121"));
+  e.push_back(CellId("122"));
+  e.push_back(CellId("210"));
+  e.push_back(CellId("211"));
+  e.push_back(CellId("212"));
+  e.push_back(CellId("0211"));
+  e.push_back(CellId("0213"));
+  e.push_back(CellId("0231"));
+  e.push_back(CellId("0233"));
+  e.push_back(CellId("1130"));
+  e.push_back(CellId("1132"));
+  e.push_back(CellId("1230"));
+  e.push_back(CellId("1300"));
+  e.push_back(CellId("2011"));
+  e.push_back(CellId("2013"));
+  e.push_back(CellId("2031"));
+  e.push_back(CellId("2033"));
+  e.push_back(CellId("2130"));
+  e.push_back(CellId("2211"));
+  e.push_back(CellId("2300"));
+  e.push_back(CellId("3000"));
+  TEST_EQUAL(v, e, ());
+}
+
+UNIT_TEST(CoverTriangle_TriangleInsideCell)
+{
+  vector<CellId> v;
+  covering::Covering<CellId> c(m2::PointD(0.1, 0.1), m2::PointD(0.2, 0.2), m2::PointD(0.2, 0.4));
+  c.OutputToVector(v);
+  vector<CellId> e;
+  e.push_back(CellId("0000"));
+  TEST_EQUAL(v, e, ());
+}
+
+UNIT_TEST(Covering_Append_Simple)
+{
+  vector<CellId> v1, v2, v3;
+
+  v1.push_back(CellId("012"));
+  v2.push_back(CellId("0123"));
+  v3.push_back(CellId("012"));
+
+  v1.push_back(CellId("023"));
+  v2.push_back(CellId("023"));
+  v3.push_back(CellId("023"));
+
+  v1.push_back(CellId("130"));
+  v1.push_back(CellId("131"));
+  v2.push_back(CellId("133"));
+  v1.push_back(CellId("1320"));
+  v1.push_back(CellId("1321"));
+  v2.push_back(CellId("1322"));
+  v2.push_back(CellId("1323"));
+  v3.push_back(CellId("13"));
+
+  covering::Covering<CellId> c1(v1);
+  c1.Append(covering::Covering<CellId>(v2));
+  vector<CellId> v4;
+  c1.OutputToVector(v4);
+  sort(v4.begin(), v4.end(), CellId::LessStackOrder());
+  TEST_EQUAL(v3, v4, ());
+}
+
+UNIT_TEST(IntersectCellWithTriangle_EmptyTriangle)
+{
+  m2::PointU pt(27, 31);
+  TEST_EQUAL(covering::CELL_OBJECT_NO_INTERSECTION,
+             covering::IntersectCellWithTriangle(CellId("0"), pt, pt, pt), ());
+  TEST_EQUAL(covering::CELL_OBJECT_NO_INTERSECTION,
+             covering::IntersectCellWithTriangle(CellId("1"), pt, pt, pt), ());
+  TEST_EQUAL(covering::CELL_OBJECT_NO_INTERSECTION,
+             covering::IntersectCellWithTriangle(CellId("2"), pt, pt, pt), ());
+  TEST_EQUAL(covering::OBJECT_INSIDE_CELL,
+             covering::IntersectCellWithTriangle(CellId("3"), pt, pt, pt), ());
+}
+
+UNIT_TEST(Covering_EmptyTriangle)
+{
+  m2::PointU pt(27, 31);
+  CellId const expectedCellId = CellId::FromXY(pt.x, pt.y);
+  TEST_GREATER(expectedCellId.ToInt64(), 5, ());
+  covering::Covering<CellId> covering(pt, pt, pt);
+  vector<CellId> ids;
+  covering.OutputToVector(ids);
+  TEST_EQUAL(ids, vector<CellId>(1, expectedCellId), ());
+}
+
+UNIT_TEST(Covering_Simplify_Smoke)
+{
+  vector<CellId> v;
+  v.push_back(CellId("03"));
+  v.push_back(CellId("020"));
+  v.push_back(CellId("021"));
+  v.push_back(CellId("022"));
+  v.push_back(CellId("0012"));
+  covering::Covering<CellId> covering(v);
+  v.clear();
+  covering.Simplify();
+  covering.OutputToVector(v);
+  vector<CellId> e;
+  e.push_back(CellId("02"));
+  e.push_back(CellId("03"));
+  e.push_back(CellId("0012"));
+  TEST_EQUAL(v, e, ());
+}