[geocoder] Add borders class to support region borders in reverse serverside geocoder

7 files changed, 307 insertions, 0 deletions

diff --git a/defines.hpp b/defines.hpp
index 9518918c1e..a7280af864 100644
--- a/defines.hpp
+++ b/defines.hpp
@@ -51,6 +51,7 @@
 
 #define LOCALITY_DATA_FILE_TAG "locdata"
 #define LOCALITY_INDEX_FILE_TAG "locidx"
+#define BORDERS_FILE_TAG "borders"
 
 #define READY_FILE_EXTENSION ".ready"
 #define RESUME_FILE_EXTENSION ".resume"
diff --git a/indexer/CMakeLists.txt b/indexer/CMakeLists.txt
index 099910e5f9..c217ea1e49 100644
--- a/indexer/CMakeLists.txt
+++ b/indexer/CMakeLists.txt
@@ -6,6 +6,8 @@ set(
   SRC
   altitude_loader.cpp
   altitude_loader.hpp
+  borders.cpp
+  borders.hpp
   categories_holder.cpp
   categories_holder.hpp
   categories_holder_loader.cpp
diff --git a/indexer/borders.cpp b/indexer/borders.cpp
new file mode 100644
index 0000000000..0702ae728f
--- /dev/null
+++ b/indexer/borders.cpp
@@ -0,0 +1,109 @@
+#include "indexer/borders.hpp"
+
+#include "coding/file_container.hpp"
+#include "coding/geometry_coding.hpp"
+#include "coding/var_record_reader.hpp"
+
+#include "base/logging.hpp"
+#include "base/macros.hpp"
+
+#include "defines.hpp"
+
+using namespace std;
+
+namespace
+{
+template <class Reader>
+class BordersVector
+{
+public:
+  BordersVector(Reader const & reader) : m_recordReader(reader, 256 /* expectedRecordSize */) {}
+
+  template <class ToDo>
+  void ForEach(ToDo && toDo) const
+  {
+    m_recordReader.ForEachRecord([&](uint32_t pos, char const * data, uint32_t /*size*/) {
+      ArrayByteSource src(data);
+      serial::GeometryCodingParams cp = {};
+      uint64_t id;
+      ReadPrimitiveFromSource(src, id);
+      size_t size;
+      ReadPrimitiveFromSource(src, size);
+      size_t outerSize;
+      ReadPrimitiveFromSource(src, outerSize);
+      vector<m2::PointD> outer(outerSize);
+      // todo:(@t.yan) consider delta coding techniques.
+      for (auto & point : outer)
+        point = serial::LoadPoint(src, cp);
+
+      vector<vector<m2::PointD>> inners(size);
+      for (auto & inner : inners)
+      {
+        size_t innerSize;
+        ReadPrimitiveFromSource(src, innerSize);
+        inner = vector<m2::PointD>(innerSize);
+        for (auto & point : inner)
+          point = serial::LoadPoint(src, cp);
+      }
+      toDo(id, outer, inners);
+    });
+  }
+
+private:
+  friend class BordersVectorReader;
+
+  VarRecordReader<FilesContainerR::TReader, &VarRecordSizeReaderVarint> m_recordReader;
+
+  DISALLOW_COPY(BordersVector);
+};
+
+class BordersVectorReader
+{
+public:
+  explicit BordersVectorReader(string const & filePath)
+    : m_cont(filePath), m_vector(m_cont.GetReader(BORDERS_FILE_TAG))
+  {
+  }
+
+  BordersVector<ModelReaderPtr> const & GetVector() const { return m_vector; }
+
+private:
+  FilesContainerR m_cont;
+  BordersVector<ModelReaderPtr> m_vector;
+
+  DISALLOW_COPY(BordersVectorReader);
+};
+}  // namespace
+
+namespace indexer
+{
+bool Borders::Border::IsPointInside(m2::PointD const & point) const
+{
+  if (!m_outer.Contains(point))
+    return false;
+
+  for (auto const & inner : m_inners)
+  {
+    if (inner.Contains(point))
+      return false;
+  }
+
+  return true;
+}
+
+bool Borders::Deserialize(string const & filename)
+{
+  try
+  {
+    BordersVectorReader reader(filename);
+    auto const & records = reader.GetVector();
+    DeserializeFromVec(records);
+  }
+  catch (Reader::Exception const & e)
+  {
+    LOG(LERROR, ("Error while reading file:", e.Msg()));
+    return false;
+  }
+  return true;
+}
+}  // namespace indexer
diff --git a/indexer/borders.hpp b/indexer/borders.hpp
new file mode 100644
index 0000000000..333c0f39d4
--- /dev/null
+++ b/indexer/borders.hpp
@@ -0,0 +1,62 @@
+#pragma once
+
+#include "geometry/point2d.hpp"
+#include "geometry/region2d.hpp"
+
+#include <cstdint>
+#include <map>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace indexer
+{
+// Stores region borders for countries, states, cities, city districts in reverse geocoder.
+// Used to check exact object region after getting regions short list from regions geo index.
+// Each region may have several outer borders. It may be islands or separated parts like
+// Kaliningrad region which is part of Russia or Alaska which is part of US.
+// Each outer border may have several inner borders e.g. Vatican and San Marino are
+// located inside Italy but are not parts of it.
+class Borders
+{
+public:
+  bool IsPointInside(uint64_t id, m2::PointD const & point) const
+  {
+    auto const range = m_borders.equal_range(id);
+
+    for (auto it = range.first; it != range.second; ++it)
+    {
+      if (it->second.IsPointInside(point))
+        return true;
+    }
+    return false;
+  }
+
+  bool Deserialize(std::string const & filename);
+
+  template <typename BordersVec>
+  void DeserializeFromVec(BordersVec const & vec)
+  {
+    vec.ForEach([this](uint64_t id, std::vector<m2::PointD> const & outer,
+                       std::vector<std::vector<m2::PointD>> const & inners) {
+      auto it = m_borders.insert(std::make_pair(id, Border()));
+      it->second.m_outer = m2::RegionD(outer);
+      for (auto const & inner : inners)
+        it->second.m_inners.push_back(m2::RegionD(inner));
+    });
+  }
+
+private:
+  struct Border
+  {
+    Border() = default;
+
+    bool IsPointInside(m2::PointD const & point) const;
+
+    m2::RegionD m_outer;
+    std::vector<m2::RegionD> m_inners;
+  };
+
+  std::multimap<uint64_t, Border> m_borders;
+};
+}  // namespace indexer
diff --git a/indexer/indexer_tests/CMakeLists.txt b/indexer/indexer_tests/CMakeLists.txt
index c84224d8bb..1bd0d5a765 100644
--- a/indexer/indexer_tests/CMakeLists.txt
+++ b/indexer/indexer_tests/CMakeLists.txt
@@ -2,6 +2,7 @@ project(indexer_tests)
 
 set(
   SRC
+  borders_test.cpp
   bounds.hpp
   categories_test.cpp
   cell_coverer_test.cpp
diff --git a/indexer/indexer_tests/borders_test.cpp b/indexer/indexer_tests/borders_test.cpp
new file mode 100644
index 0000000000..2c6ee2ed10
--- /dev/null
+++ b/indexer/indexer_tests/borders_test.cpp
@@ -0,0 +1,120 @@
+#include "testing/testing.hpp"
+
+#include "indexer/borders.hpp"
+
+#include "geometry/point2d.hpp"
+
+#include <cstdint>
+#include <vector>
+
+using namespace indexer;
+using namespace std;
+
+namespace
+{
+struct BordersVector
+{
+  struct Border
+  {
+    uint64_t m_id;
+    vector<m2::PointD> m_outer;
+    vector<vector<m2::PointD>> m_inners;
+  };
+
+  template <typename ToDo>
+  void ForEach(ToDo && toDo) const
+  {
+    for (auto const & border : m_borders)
+      toDo(border.m_id, border.m_outer, border.m_inners);
+  }
+
+  vector<Border> m_borders;
+};
+
+UNIT_TEST(BordersTest)
+{
+  {
+    BordersVector vec;
+    vec.m_borders.resize(1);
+    vec.m_borders[0].m_id = 0;
+    vec.m_borders[0].m_outer = {m2::PointD{0, 0}, m2::PointD{1, 0}, m2::PointD{1, 1}, m2::PointD{0, 1}};
+
+    indexer::Borders borders;
+    borders.DeserializeFromVec(vec);
+
+    TEST(borders.IsPointInside(0, m2::PointD{0.5, 0.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{-0.5, 0.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{-0.5, -0.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{-0.5, -0.5}), ());
+  }
+  {
+    BordersVector vec;
+    vec.m_borders.resize(2);
+    vec.m_borders[0].m_id = 0;
+    vec.m_borders[0].m_outer = {m2::PointD{0, 0}, m2::PointD{1, 0}, m2::PointD{1, 1}, m2::PointD{0, 1}};
+    vec.m_borders[1].m_id = 0;
+    vec.m_borders[1].m_outer = {m2::PointD{2, 2}, m2::PointD{3, 2}, m2::PointD{3, 3}, m2::PointD{2, 3}};
+
+    indexer::Borders borders;
+    borders.DeserializeFromVec(vec);
+
+    TEST(borders.IsPointInside(0, m2::PointD{0.5, 0.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{0.5, 2.5}), ());
+    TEST(borders.IsPointInside(0, m2::PointD{2.5, 2.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{2.5, 0.5}), ());
+  }
+  {
+    BordersVector vec;
+    vec.m_borders.resize(2);
+    vec.m_borders[0].m_id = 0;
+    vec.m_borders[0].m_outer = {m2::PointD{0, 0}, m2::PointD{1, 0}, m2::PointD{1, 1}, m2::PointD{0, 1}};
+    vec.m_borders[1].m_id = 1;
+    vec.m_borders[1].m_outer = {m2::PointD{2, 2}, m2::PointD{3, 2}, m2::PointD{3, 3}, m2::PointD{2, 3}};
+
+    indexer::Borders borders;
+    borders.DeserializeFromVec(vec);
+
+    TEST(borders.IsPointInside(0, m2::PointD{0.5, 0.5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{2.5, 2.5}), ());
+    TEST(borders.IsPointInside(1, m2::PointD{2.5, 2.5}), ());
+    TEST(!borders.IsPointInside(1, m2::PointD{0.5, 0.5}), ());
+  }
+  {
+    BordersVector vec;
+    vec.m_borders.resize(1);
+    vec.m_borders[0].m_id = 0;
+    vec.m_borders[0].m_outer = {m2::PointD{0, 0}, m2::PointD{10, 0}, m2::PointD{10, 10}, m2::PointD{0, 10}};
+    vec.m_borders[0].m_inners = {{m2::PointD{2, 2}, m2::PointD{8, 2}, m2::PointD{8, 8}, m2::PointD{2, 8}}};
+
+    indexer::Borders borders;
+    borders.DeserializeFromVec(vec);
+
+    TEST(borders.IsPointInside(0, m2::PointD{1, 1}), ());
+    TEST(borders.IsPointInside(0, m2::PointD{9, 9}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{3, 7}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{5, 5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{6, 6}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{7, 3}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{7, 7}), ());
+  }
+  {
+    BordersVector vec;
+    vec.m_borders.resize(1);
+    vec.m_borders[0].m_id = 0;
+    vec.m_borders[0].m_outer = {m2::PointD{0, 0}, m2::PointD{10, 0}, m2::PointD{10, 10}, m2::PointD{0, 10}};
+    vec.m_borders[0].m_inners = {{m2::PointD{2, 2}, m2::PointD{5, 2}, m2::PointD{5, 5}, m2::PointD{2, 5}},
+                                 {m2::PointD{5, 5}, m2::PointD{8, 5}, m2::PointD{8, 8}, m2::PointD{5, 8}}};
+
+    indexer::Borders borders;
+    borders.DeserializeFromVec(vec);
+
+    TEST(borders.IsPointInside(0, m2::PointD{1, 1}), ());
+    TEST(borders.IsPointInside(0, m2::PointD{9, 9}), ());
+    TEST(borders.IsPointInside(0, m2::PointD{3, 7}), ());
+    TEST(borders.IsPointInside(0, m2::PointD{7, 3}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{5, 5}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{6, 6}), ());
+    TEST(!borders.IsPointInside(0, m2::PointD{7, 7}), ());
+  }
+}
+}  // namespace
diff --git a/xcode/indexer/indexer.xcodeproj/project.pbxproj b/xcode/indexer/indexer.xcodeproj/project.pbxproj
index afa22e6632..2ee32db842 100644
--- a/xcode/indexer/indexer.xcodeproj/project.pbxproj
+++ b/xcode/indexer/indexer.xcodeproj/project.pbxproj
@@ -76,6 +76,9 @@
 		40009064201F5CB000963E18 /* locality_index_builder.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 4000905F201F5CAF00963E18 /* locality_index_builder.hpp */; };
 		40009065201F5CB000963E18 /* locality_object.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40009060201F5CB000963E18 /* locality_object.hpp */; };
 		40009066201F5CB000963E18 /* locality_index_builder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 40009061201F5CB000963E18 /* locality_index_builder.cpp */; };
+		406B37F4207FBABB000F3648 /* borders.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 406B37F2207FBABA000F3648 /* borders.cpp */; };
+		406B37F5207FBABB000F3648 /* borders.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 406B37F3207FBABA000F3648 /* borders.hpp */; };
+		406B37F7207FBAC7000F3648 /* borders_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 406B37F6207FBAC7000F3648 /* borders_test.cpp */; };
 		4095DEB22020AC0000C591A3 /* locality_index.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 4095DEB12020AC0000C591A3 /* locality_index.hpp */; };
 		4099F6491FC7142A002A7B05 /* fake_feature_ids.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 4099F6471FC71429002A7B05 /* fake_feature_ids.cpp */; };
 		4099F64A1FC7142A002A7B05 /* fake_feature_ids.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 4099F6481FC7142A002A7B05 /* fake_feature_ids.hpp */; };
@@ -305,6 +308,9 @@
 		4000905F201F5CAF00963E18 /* locality_index_builder.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = locality_index_builder.hpp; sourceTree = "<group>"; };
 		40009060201F5CB000963E18 /* locality_object.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = locality_object.hpp; sourceTree = "<group>"; };
 		40009061201F5CB000963E18 /* locality_index_builder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = locality_index_builder.cpp; sourceTree = "<group>"; };
+		406B37F2207FBABA000F3648 /* borders.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = borders.cpp; sourceTree = "<group>"; };
+		406B37F3207FBABA000F3648 /* borders.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = borders.hpp; sourceTree = "<group>"; };
+		406B37F6207FBAC7000F3648 /* borders_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = borders_test.cpp; sourceTree = "<group>"; };
 		4095DEB12020AC0000C591A3 /* locality_index.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = locality_index.hpp; sourceTree = "<group>"; };
 		4099F6471FC71429002A7B05 /* fake_feature_ids.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = fake_feature_ids.cpp; sourceTree = "<group>"; };
 		4099F6481FC7142A002A7B05 /* fake_feature_ids.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = fake_feature_ids.hpp; sourceTree = "<group>"; };
@@ -596,6 +602,7 @@
 		670C60F81AB0657700C38A8C /* indexer_tests */ = {
 			isa = PBXGroup;
 			children = (
+				406B37F6207FBAC7000F3648 /* borders_test.cpp */,
 				39F376C1207D324E0058E8E0 /* scale_index_reading_tests.cpp */,
 				39F376BE207D32410058E8E0 /* cities_boundaries_serdes_tests.cpp */,
 				40C3C090205BF9F400CED188 /* bounds.hpp */,
@@ -666,6 +673,8 @@
 		6753409C1A3F53CB00A0A8C3 /* indexer */ = {
 			isa = PBXGroup;
 			children = (
+				406B37F2207FBABA000F3648 /* borders.cpp */,
+				406B37F3207FBABA000F3648 /* borders.hpp */,
 				4095DEB12020AC0000C591A3 /* locality_index.hpp */,
 				4000905D201F5CAF00963E18 /* cell_value_pair.hpp */,
 				40009061201F5CB000963E18 /* locality_index_builder.cpp */,
@@ -845,6 +854,7 @@
 				347F337F1C454242009758CC /* trie_builder.hpp in Headers */,
 				34664CF71D49FEC1003D7096 /* centers_table.hpp in Headers */,
 				6753414C1A3F540F00A0A8C3 /* tree_structure.hpp in Headers */,
+				406B37F5207FBABB000F3648 /* borders.hpp in Headers */,
 				F6DF5F311CD0FD9A00A87154 /* categories_index.hpp in Headers */,
 				347F337D1C454242009758CC /* succinct_trie_builder.hpp in Headers */,
 				675341381A3F540F00A0A8C3 /* mwm_set.hpp in Headers */,
@@ -1085,6 +1095,7 @@
 				6753411A1A3F540F00A0A8C3 /* feature_impl.cpp in Sources */,
 				56C74C1C1C749E4700B71B9F /* categories_holder_loader.cpp in Sources */,
 				3D74EF241F8F559D0081202C /* ugc_types_test.cpp in Sources */,
+				406B37F4207FBABB000F3648 /* borders.cpp in Sources */,
 				40A1C30A202B321000F71672 /* locality_index_test.cpp in Sources */,
 				6753410D1A3F540F00A0A8C3 /* drawing_rules.cpp in Sources */,
 				675341301A3F540F00A0A8C3 /* index.cpp in Sources */,
@@ -1135,6 +1146,7 @@
 				6758AED11BB4413000C26E27 /* drules_selector_parser.cpp in Sources */,
 				E906DE3B1CF44934004C4F5E /* postcodes_matcher.cpp in Sources */,
 				3D489BF31D4F87740052AA38 /* osm_editor_test.cpp in Sources */,
+				406B37F7207FBAC7000F3648 /* borders_test.cpp in Sources */,
 			);
 			runOnlyForDeploymentPostprocessing = 0;
 		};