Merge pull request #4445 from ygorshenin/accelerate-locality-finder

[search] Accelerated locality finder.

3 files changed, 181 insertions, 95 deletions

diff --git a/search/locality_finder.cpp b/search/locality_finder.cpp
index 7621b5f462..c890636617 100644
--- a/search/locality_finder.cpp
+++ b/search/locality_finder.cpp
@@ -5,6 +5,7 @@
 #include "search/dummy_rank_table.hpp"
 #include "search/mwm_context.hpp"
 
+#include "indexer/feature_algo.hpp"
 #include "indexer/ftypes_matcher.hpp"
 #include "indexer/index.hpp"
 
@@ -18,6 +19,7 @@ namespace search
 namespace
 {
 double const kMaxCityRadiusMeters = 30000.0;
+double const kMaxVillageRadiusMeters = 2000.0;
 
 struct Filter
 {
@@ -54,22 +56,22 @@ class LocalitiesLoader
 {
 public:
   LocalitiesLoader(MwmContext const & ctx, Filter const & filter, int8_t lang,
-                   m4::Tree<LocalityFinder::Item> & localities,
+                   LocalityFinder::Holder & holder,
                    map<MwmSet::MwmId, unordered_set<uint32_t>> & loadedIds)
     : m_ctx(ctx)
     , m_filter(filter)
     , m_lang(lang)
-    , m_localities(localities)
+    , m_holder(holder)
     , m_loadedIds(loadedIds[m_ctx.GetId()])
   {
   }
 
   void operator()(uint32_t id) const
   {
-    if (m_loadedIds.count(id) != 0)
+    if (!m_filter.IsGood(id))
       return;
 
-    if (!m_filter.IsGood(id))
+    if (m_loadedIds.count(id) != 0)
       return;
 
     FeatureType ft;
@@ -101,8 +103,7 @@ public:
 
     auto const center = ft.GetCenter();
 
-    LocalityFinder::Item item(name, center, population);
-    m_localities.Add(item, m2::RectD(center, center));
+    m_holder.Add(LocalityItem(name, center, population));
     m_loadedIds.insert(id);
   }
 
@@ -111,21 +112,97 @@ private:
   Filter const & m_filter;
   int8_t const m_lang;
 
-  m4::Tree<LocalityFinder::Item> & m_localities;
+  LocalityFinder::Holder & m_holder;
   unordered_set<uint32_t> & m_loadedIds;
 };
 }  // namespace
 
-// LocalityFinder::Item
-// ------------------------------------------------------------------------------------
-LocalityFinder::Item::Item(string const & name, m2::PointD const & center, uint32_t population)
+// LocalityItem ------------------------------------------------------------------------------------
+LocalityItem::LocalityItem(string const & name, m2::PointD const & center, uint32_t population)
   : m_name(name), m_center(center), m_population(population)
 {
 }
 
+string DebugPrint(LocalityItem const & item)
+{
+  stringstream ss;
+  ss << "Name = " << item.m_name << ", Center = " << DebugPrint(item.m_center)
+     << ", Population = " << item.m_population;
+  return ss.str();
+}
+
+// LocalitySelector --------------------------------------------------------------------------------
+LocalitySelector::LocalitySelector(string & name, m2::PointD const & p)
+  : m_name(name)
+  , m_p(p)
+  , m_bestScore(numeric_limits<double>::max())
+{
+}
+
+void LocalitySelector::operator()(LocalityItem const & item)
+{
+  // TODO (@y, @m): replace this naive score by p-values on
+  // multivariate Gaussian.
+  double const distance = MercatorBounds::DistanceOnEarth(item.m_center, m_p);
+
+  double const score =
+      ftypes::GetPopulationByRadius(distance) / static_cast<double>(item.m_population);
+  if (score < m_bestScore)
+  {
+    m_bestScore = score;
+    m_name = item.m_name;
+  }
+}
+
+// LocalityFinder::Holder --------------------------------------------------------------------------
+LocalityFinder::Holder::Holder(double radiusMeters) : m_radiusMeters(radiusMeters) {}
+
+bool LocalityFinder::Holder::IsCovered(m2::RectD const & rect) const
+{
+  bool covered = false;
+  m_coverage.ForEachInRect(rect, [&covered](bool) { covered = true; });
+  return covered;
+}
+
+void LocalityFinder::Holder::SetCovered(m2::PointD const & p)
+{
+  m_coverage.Add(true, m2::RectD(p, p));
+}
+
+void LocalityFinder::Holder::Add(LocalityItem const & item)
+{
+  m_localities.Add(item, m2::RectD(item.m_center, item.m_center));
+}
+
+void LocalityFinder::Holder::ForEachInVicinity(m2::RectD const & rect,
+                                               LocalitySelector & selector) const
+{
+  m_localities.ForEachInRect(rect, selector);
+}
+
+m2::RectD LocalityFinder::Holder::GetRect(m2::PointD const & p) const
+{
+  return MercatorBounds::RectByCenterXYAndSizeInMeters(p, m_radiusMeters);
+}
+
+m2::RectD LocalityFinder::Holder::GetDRect(m2::PointD const & p) const
+{
+  return MercatorBounds::RectByCenterXYAndSizeInMeters(p, 2 * m_radiusMeters);
+}
+
+void LocalityFinder::Holder::Clear()
+{
+  m_coverage.Clear();
+  m_localities.Clear();
+}
+
 // LocalityFinder ----------------------------------------------------------------------------------
 LocalityFinder::LocalityFinder(Index const & index, VillagesCache & villagesCache)
-  : m_index(index), m_villagesCache(villagesCache), m_lang(0)
+  : m_index(index)
+  , m_villagesCache(villagesCache)
+  , m_lang(0)
+  , m_cities(kMaxCityRadiusMeters)
+  , m_villages(kMaxVillageRadiusMeters)
 {
 }
 
@@ -138,30 +215,34 @@ void LocalityFinder::SetLanguage(int8_t lang)
   m_lang = lang;
 }
 
-void LocalityFinder::GetLocality(m2::PointD const & pt, string & name)
+void LocalityFinder::GetLocality(m2::PointD const & p, string & name)
 {
-  m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters);
+  m2::RectD const crect = m_cities.GetRect(p);
+  m2::RectD const vrect = m_villages.GetRect(p);
 
-  bool covered = false;
-  m_coverage.ForEachInRect(rect, [&covered](bool) { covered = true; });
-  if (!covered)
-    LoadVicinity(pt);
+  LoadVicinity(p, !m_cities.IsCovered(crect) /* loadCities */,
+               !m_villages.IsCovered(vrect) /* loadVillages */);
 
-  m_localities.ForEachInRect(rect, LocalitySelector(name, pt));
+  LocalitySelector selector(name, p);
+  m_cities.ForEachInVicinity(crect, selector);
+  m_villages.ForEachInVicinity(vrect, selector);
 }
 
 void LocalityFinder::ClearCache()
 {
   m_ranks.reset();
-  m_coverage.Clear();
-  m_localities.Clear();
+  m_cities.Clear();
+  m_villages.Clear();
   m_loadedIds.clear();
 }
 
-void LocalityFinder::LoadVicinity(m2::PointD const & pt)
+void LocalityFinder::LoadVicinity(m2::PointD const & p, bool loadCities, bool loadVillages)
 {
-  m2::RectD const drect =
-      MercatorBounds::RectByCenterXYAndSizeInMeters(pt, 2 * kMaxCityRadiusMeters);
+  if (!loadCities && !loadVillages)
+    return;
+
+  m2::RectD const crect = m_cities.GetDRect(p);
+  m2::RectD const vrect = m_villages.GetDRect(p);
 
   vector<shared_ptr<MwmInfo>> mwmsInfo;
   m_index.GetMwmsInfo(mwmsInfo);
@@ -179,57 +260,34 @@ void LocalityFinder::LoadVicinity(m2::PointD const & pt)
     {
     case feature::DataHeader::world:
     {
+      if (!loadCities)
+        break;
+
       if (!m_ranks)
         m_ranks = RankTable::Load(value.m_cont);
       if (!m_ranks)
         m_ranks = make_unique<DummyRankTable>();
 
       MwmContext ctx(move(handle));
-      ctx.ForEachIndex(
-          drect, LocalitiesLoader(ctx, CityFilter(*m_ranks), m_lang, m_localities, m_loadedIds));
+      ctx.ForEachIndex(crect,
+                       LocalitiesLoader(ctx, CityFilter(*m_ranks), m_lang, m_cities, m_loadedIds));
       break;
     }
     case feature::DataHeader::country:
-      if (header.GetBounds().IsPointInside(pt))
+      if (loadVillages && header.GetBounds().IsPointInside(p))
       {
         MwmContext ctx(move(handle));
-        ctx.ForEachIndex(drect, LocalitiesLoader(ctx, VillageFilter(ctx, m_villagesCache), m_lang,
-                                                 m_localities, m_loadedIds));
+        ctx.ForEachIndex(vrect, LocalitiesLoader(ctx, VillageFilter(ctx, m_villagesCache), m_lang,
+                                                 m_villages, m_loadedIds));
       }
       break;
     case feature::DataHeader::worldcoasts: break;
     }
   }
 
-  m_coverage.Add(true, m2::RectD(pt, pt));
-}
-
-// LocalitySelector --------------------------------------------------------------------------------
-LocalitySelector::LocalitySelector(string & name, m2::PointD const & pt)
-  : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max())
-{
-}
-
-void LocalitySelector::operator()(LocalityFinder::Item const & item)
-{
-  // TODO (@y, @m): replace this naive score by p-values on
-  // multivariate Gaussian.
-  double const distance = MercatorBounds::DistanceOnEarth(item.m_center, m_pt);
-
-  double const score =
-      ftypes::GetPopulationByRadius(distance) / static_cast<double>(item.m_population);
-  if (score < m_bestScore)
-  {
-    m_bestScore = score;
-    m_name = item.m_name;
-  }
-}
-
-string DebugPrint(LocalityFinder::Item const & item)
-{
-  stringstream ss;
-  ss << "Name = " << item.m_name << ", Center = " << DebugPrint(item.m_center)
-     << ", Population = " << item.m_population;
-  return ss.str();
+  if (loadCities)
+    m_cities.SetCovered(p);
+  if (loadVillages)
+    m_villages.SetCovered(p);
 }
 }  // namespace search
diff --git a/search/locality_finder.hpp b/search/locality_finder.hpp
index 913971ac90..eae1ef4a4e 100644
--- a/search/locality_finder.hpp
+++ b/search/locality_finder.hpp
@@ -7,6 +7,8 @@
 #include "geometry/rect2d.hpp"
 #include "geometry/tree4d.hpp"
 
+#include "base/macros.hpp"
+
 #include "std/unique_ptr.hpp"
 #include "std/unordered_set.hpp"
 
@@ -16,50 +18,76 @@ namespace search
 {
 class VillagesCache;
 
+struct LocalityItem
+{
+  LocalityItem(string const & name, m2::PointD const & center, uint32_t population);
+
+  string m_name;
+  m2::PointD m_center;
+  uint32_t m_population;
+};
+
+string DebugPrint(LocalityItem const & item);
+
+class LocalitySelector
+{
+public:
+  LocalitySelector(string & name, m2::PointD const & p);
+
+  void operator()(LocalityItem const & item);
+
+private:
+  string & m_name;
+  m2::PointD m_p;
+  double m_bestScore;
+};
+
 class LocalityFinder
 {
 public:
-  struct Item
+  class Holder
   {
-    Item(string const & name, m2::PointD const & center, uint32_t population);
+   public:
+    Holder(double radiusMeters);
+
+    bool IsCovered(m2::RectD const & rect) const;
+    void SetCovered(m2::PointD const & p);
+
+    void Add(LocalityItem const & item);
+    void ForEachInVicinity(m2::RectD const & rect, LocalitySelector & selector) const;
 
-    string m_name;
-    m2::PointD m_center;
-    uint32_t m_population;
+    m2::RectD GetRect(m2::PointD const & p) const;
+    m2::RectD GetDRect(m2::PointD const & p) const;
+
+    void Clear();
+
+   private:
+
+    double const m_radiusMeters;
+    m4::Tree<bool> m_coverage;
+    m4::Tree<LocalityItem> m_localities;
+
+    DISALLOW_COPY_AND_MOVE(Holder);
   };
 
   LocalityFinder(Index const & index, VillagesCache & villagesCache);
 
   void SetLanguage(int8_t lang);
-  void GetLocality(m2::PointD const & pt, string & name);
+  void GetLocality(m2::PointD const & p, string & name);
   void ClearCache();
 
 private:
-  void LoadVicinity(m2::PointD const & pt);
+  void LoadVicinity(m2::PointD const & p, bool loadCities, bool loadVillages);
 
   Index const & m_index;
   VillagesCache & m_villagesCache;
-  unique_ptr<RankTable> m_ranks;
-
-  m4::Tree<bool> m_coverage;
-  m4::Tree<Item> m_localities;
-  map<MwmSet::MwmId, unordered_set<uint32_t>> m_loadedIds;
-
   int8_t m_lang;
-};
 
-class LocalitySelector
-{
-public:
-  LocalitySelector(string & name, m2::PointD const & pt);
+  Holder m_cities;
+  Holder m_villages;
 
-  void operator()(LocalityFinder::Item const & item);
+  unique_ptr<RankTable> m_ranks;
 
-private:
-  string & m_name;
-  m2::PointD m_pt;
-  double m_bestScore;
+  map<MwmSet::MwmId, unordered_set<uint32_t>> m_loadedIds;
 };
-
-string DebugPrint(LocalityFinder::Item const & item);
 }  // namespace search
diff --git a/search/search_tests/locality_selector_test.cpp b/search/search_tests/locality_selector_test.cpp
index 53c7659cf4..29cf8d6270 100644
--- a/search/search_tests/locality_selector_test.cpp
+++ b/search/search_tests/locality_selector_test.cpp
@@ -6,7 +6,7 @@ using namespace search;
 
 namespace
 {
-string GetMatchedCity(m2::PointD const & point, vector<LocalityFinder::Item> const & items)
+string GetMatchedCity(m2::PointD const & point, vector<LocalityItem> const & items)
 {
   string name;
   LocalitySelector selector(name, point);
@@ -21,31 +21,31 @@ string GetMatchedCity(m2::PointD const & point, vector<LocalityFinder::Item> con
 // UNIT_TEST(LocalitySelector_Test1)
 // {
 //   auto const name = GetMatchedCity(
-//       m2::PointD(-97.563458662952925238, 26.796728721236661386),
-//       {{"Matamoros", m2::PointD(-97.506656349498797454, 26.797180986068354969), 10000},
+//       m2::PointD(-97.56345, 26.79672),
+//       {{"Matamoros", m2::PointD(-97.50665, 26.79718), 10000},
 
-//        {"Brownsville", m2::PointD(-97.489103971612919963, 26.845589500139880101), 180663}});
+//        {"Brownsville", m2::PointD(-97.48910, 26.84558), 180663}});
 //   TEST_EQUAL(name, "Matamoros", ());
 // }
 
 UNIT_TEST(LocalitySelector_Test2)
 {
-  vector<LocalityFinder::Item> const localities = {
-      {"Moscow", m2::PointD(37.617513849438893203, 67.45398133444564337), 11971516},
-      {"Krasnogorsk", m2::PointD(37.340409438658895169, 67.58036703829372982), 135735},
-      {"Khimki", m2::PointD(37.444994145035053634, 67.700701677882875629), 240463},
-      {"Mytishchi", m2::PointD(37.733943192236807818, 67.736750571340394345), 180663},
-      {"Dolgoprudny", m2::PointD(37.514259518892714595, 67.780738804428438016), 101979}};
+  vector<LocalityItem> const localities = {
+      {"Moscow", m2::PointD(37.61751, 67.45398), 11971516},
+      {"Krasnogorsk", m2::PointD(37.34040, 67.58036), 135735},
+      {"Khimki", m2::PointD(37.44499, 67.70070), 240463},
+      {"Mytishchi", m2::PointD(37.73394, 67.73675), 180663},
+      {"Dolgoprudny", m2::PointD(37.51425, 67.78073), 101979}};
 
   {
     auto const name =
-        GetMatchedCity(m2::PointD(37.538269143836714647, 67.535546478148901883), localities);
+        GetMatchedCity(m2::PointD(37.53826, 67.53554), localities);
     TEST_EQUAL(name, "Moscow", ());
   }
 
   {
     auto const name =
-        GetMatchedCity(m2::PointD(37.469807099326018829, 67.666502652067720192), localities);
+        GetMatchedCity(m2::PointD(37.46980, 67.66650), localities);
     TEST_EQUAL(name, "Khimki", ());
   }
 }