Split coast cells by 4 with many polygon points.

6 files changed, 119 insertions, 107 deletions

diff --git a/generator/coastlines_generator.cpp b/generator/coastlines_generator.cpp
index 25abb6c597..182beec5d7 100644
--- a/generator/coastlines_generator.cpp
+++ b/generator/coastlines_generator.cpp
@@ -1,6 +1,5 @@
 #include "coastlines_generator.hpp"
 #include "feature_builder.hpp"
-#include "tesselator.hpp"
 
 #include "../indexer/point_to_int64.hpp"
 
@@ -17,9 +16,12 @@ typedef m2::PointI PointT;
 typedef m2::RectI RectT;
 
 
-CoastlineFeaturesGenerator::CoastlineFeaturesGenerator(uint32_t coastType, int level)
-  : m_merger(POINT_COORD_BITS), m_coastType(coastType), m_Level(level)
+CoastlineFeaturesGenerator::CoastlineFeaturesGenerator(uint32_t coastType,
+                                                       int lowLevel, int highLevel, int maxPoints)
+  : m_merger(POINT_COORD_BITS), m_coastType(coastType),
+    m_lowLevel(lowLevel), m_highLevel(highLevel), m_maxPoints(maxPoints)
 {
+  ASSERT_LESS_OR_EQUAL ( m_lowLevel, m_highLevel, () );
 }
 
 namespace
@@ -36,14 +38,16 @@ namespace
     return PointT(static_cast<int32_t>(pu.x), static_cast<int32_t>(pu.y));
   }
 
-  class DoCreateRegion
+  template <class TreeT> class DoCreateRegion
   {
+    TreeT & m_tree;
+
     RegionT m_rgn;
     m2::PointD m_pt;
     bool m_exist;
 
   public:
-    DoCreateRegion() : m_exist(false) {}
+    DoCreateRegion(TreeT & tree) : m_tree(tree), m_exist(false) {}
 
     bool operator()(m2::PointD const & p)
     {
@@ -62,39 +66,22 @@ namespace
       return true;
     }
 
-    template <class TreeT> void Add(TreeT & tree)
+    void EndRegion()
     {
-      tree.Add(m_rgn, GetLimitRect(m_rgn));
-    }
-  };
+      m_tree.Add(m_rgn, GetLimitRect(m_rgn));
 
-  /*
-  template <class ContainerT> class DoAccumulate
-  {
-    ContainerT & m_list;
-  public:
-    DoAccumulate(ContainerT & lst) : m_list(lst)
-    {
-      m_list.push_back(typename ContainerT::value_type());
-    }
-    bool operator() (m2::PointD const & p)
-    {
-      m_list.back().push_back(p);
-      return true;
+      m_rgn = RegionT();
+      m_exist = false;
     }
   };
-  */
 }
 
 void CoastlineFeaturesGenerator::AddRegionToTree(FeatureBuilder1 const & fb)
 {
   ASSERT ( fb.IsGeometryClosed(), () );
 
-  DoCreateRegion createRgn;
-  //DoAccumulate<RegionsT> createRgn(m_regions);
-  CHECK_EQUAL(fb.GetPolygonsCount(), 1, ());
-  fb.ForEachGeometryPoint(createRgn);
-  createRgn.Add(m_tree);
+  DoCreateRegion<TreeT> createRgn(m_tree);
+  fb.ForEachGeometryPointEx(createRgn);
 }
 
 void CoastlineFeaturesGenerator::operator()(FeatureBuilder1 const & fb)
@@ -121,41 +108,12 @@ namespace
         LOG(LINFO, ("Not merged coastline", fb));
     }
   };
-
-  /*
-  template <class TreeT> class DoMakeRegions
-  {
-    TreeT & m_tree;
-  public:
-    DoMakeRegions(TreeT & tree) : m_tree(tree) {}
-
-    void operator() (m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
-    {
-      RegionT rgn;
-      rgn.AddPoint(D2I(p1));
-      rgn.AddPoint(D2I(p2));
-      rgn.AddPoint(D2I(p3));
-      m_tree.Add(rgn, GetLimitRect(rgn));
-    }
-  };
-  */
 }
 
 void CoastlineFeaturesGenerator::Finish()
 {
   DoAddToTree doAdd(*this);
   m_merger.DoMerge(doAdd);
-
-  /*
-  LOG(LINFO, ("Start continents tesselation"));
-
-  tesselator::TrianglesInfo info;
-  tesselator::TesselateInterior(m_regions, info);
-  m_regions.clear();  // free memory
-  info.ForEachTriangle(DoMakeRegions<TreeT>(m_tree));
-
-  LOG(LINFO, ("End continents tesselation"));
-  */
 }
 
 namespace
@@ -195,39 +153,32 @@ namespace
       m_points.push_back(m2::PointD(c.first, c.second));
     }
 
-    void AssignGeometry(vector<RegionT> const & v, FeatureBuilder1 & fb)
+    size_t GetPointsCount() const
+    {
+      size_t count = 0;
+      for (size_t i = 0; i < m_res.size(); ++i)
+        count += m_res[i].GetPointsCount();
+      return count;
+    }
+
+    void AssignGeometry(FeatureBuilder1 & fb)
     {
-      for (size_t i = 0; i < v.size(); ++i)
+      for (size_t i = 0; i < m_res.size(); ++i)
       {
         m_points.clear();
-        m_points.reserve(v[i].Size() + 1);
+        m_points.reserve(m_res[i].Size() + 1);
 
-        v[i].ForEachPoint(bind<void>(ref(*this), _1));
+        m_res[i].ForEachPoint(bind<void>(ref(*this), _1));
 
         fb.AddPolygon(m_points);
       }
     }
-
-    void AssignGeometry(FeatureBuilder1 & fb)
-    {
-      AssignGeometry(m_res, fb);
-    }
-  };
-
-  class DoLogRegions
-  {
-  public:
-    void operator() (RegionT const & r)
-    {
-      LOG_SHORT(LINFO, ("Boundary", r));
-    }
   };
 }
 
-bool CoastlineFeaturesGenerator::GetFeature(size_t i, FeatureBuilder1 & fb)
+bool CoastlineFeaturesGenerator::GetFeature(CellIdT const & cell, FeatureBuilder1 & fb)
 {
   // get rect cell
-  CellIdT cell = CellIdT::FromBitsAndLevel(i, m_Level);
   double minX, minY, maxX, maxY;
   CellIdConverter<MercatorBounds, CellIdT>::GetCellBounds(cell, minX, minY, maxX, maxY);
 
@@ -242,16 +193,41 @@ bool CoastlineFeaturesGenerator::GetFeature(size_t i, FeatureBuilder1 & fb)
   DoDifference doDiff(rectR);
   m_tree.ForEachInRect(GetLimitRect(rectR), bind<void>(ref(doDiff), _1));
 
+  // Check if too many points for feature.
+  if (cell.Level() < m_highLevel && doDiff.GetPointsCount() >= m_maxPoints)
+    return false;
+
   // assign feature
-  FeatureParams params;
-  params.name.AddString(0, strings::to_string(i));
-  fb.SetParams(params);
+  fb.SetCoastCell(cell.ToInt64(CellIdT::DEPTH_LEVELS));
 
   doDiff.AssignGeometry(fb);
   fb.SetArea();
   fb.AddType(m_coastType);
-  fb.SetCoastCell(i);
 
   // should present any geometry
-  return (fb.GetPointsCount() >= 3);
+  CHECK_GREATER ( fb.GetPolygonsCount(), 0, () );
+  CHECK_GREATER_OR_EQUAL ( fb.GetPointsCount(),  3, () );
+
+  return true;
+}
+
+void CoastlineFeaturesGenerator::GetFeatures(size_t i, vector<FeatureBuilder1> & vecFb)
+{
+  vector<CellIdT> stCells;
+  stCells.push_back(CellIdT::FromBitsAndLevel(i, m_lowLevel));
+
+  while (!stCells.empty())
+  {
+    CellIdT const cell = stCells.back();
+    stCells.pop_back();
+
+    vecFb.push_back(FeatureBuilder1());
+    if (!GetFeature(cell, vecFb.back()))
+    {
+      vecFb.pop_back();
+
+      for (int8_t i = 0; i < 4; ++i)
+        stCells.push_back(cell.Child(i));
+    }
+  }
 }
diff --git a/generator/coastlines_generator.hpp b/generator/coastlines_generator.hpp
index f96e99dd5f..f52ccd52ca 100644
--- a/generator/coastlines_generator.hpp
+++ b/generator/coastlines_generator.hpp
@@ -16,23 +16,23 @@ class CoastlineFeaturesGenerator
 
   FeatureMergeProcessor m_merger;
 
-  typedef list<vector<m2::PointD> > RegionsT;
-  RegionsT m_regions;
-
   typedef m4::Tree<m2::RegionI> TreeT;
   TreeT m_tree;
 
   uint32_t m_coastType;
-  int m_Level;
+  int m_lowLevel, m_highLevel, m_maxPoints;
+
+  bool GetFeature(CellIdT const & cell, FeatureBuilder1 & fb);
 
 public:
-  CoastlineFeaturesGenerator(uint32_t coastType, int level = 6);
+  CoastlineFeaturesGenerator(uint32_t coastType,
+                             int lowLevel, int highLevel, int maxPoints);
 
   void AddRegionToTree(FeatureBuilder1 const & fb);
 
   void operator() (FeatureBuilder1 const & fb);
   void Finish();
 
-  inline size_t GetFeaturesCount() const { return 1 << 2 * m_Level; }
-  bool GetFeature(size_t i, FeatureBuilder1 & fb);
+  inline size_t GetCellsCount() const { return 1 << 2 * m_lowLevel; }
+  void GetFeatures(size_t i, vector<FeatureBuilder1> & vecFb);
 };
diff --git a/generator/feature_builder.cpp b/generator/feature_builder.cpp
index e28187c8a6..bdc891d1fa 100644
--- a/generator/feature_builder.cpp
+++ b/generator/feature_builder.cpp
@@ -19,7 +19,7 @@ using namespace feature;
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
 FeatureBuilder1::FeatureBuilder1()
-: m_coastCell(-1U)
+: m_coastCell(-1)
 {
   m_Polygons.push_back(points_t());
 }
@@ -186,7 +186,7 @@ bool FeatureBuilder1::PreSerialize()
   }
 
   // Clear name for features with invisible texts.
-  uint32_t dummy;
+  int64_t dummy;
   if (!m_Params.name.IsEmpty() && !GetCoastCell(dummy) &&
       (feature::DrawableScaleRangeForText(GetFeatureBase()).first == -1))
   {
@@ -280,7 +280,7 @@ void FeatureBuilder1::Serialize(buffer_t & data) const
       serial::SaveOuterPath(*i, cp, sink);
   }
 
-  WriteVarUint(sink, m_coastCell);
+  WriteVarInt(sink, m_coastCell);
 
   // check for correct serialization
 #ifdef DEBUG
@@ -319,7 +319,7 @@ void FeatureBuilder1::Deserialize(buffer_t & data)
     CalcRect(m_Polygons.back(), m_LimitRect);
   }
 
-  m_coastCell = ReadVarUint<uint32_t>(source);
+  m_coastCell = ReadVarInt<int64_t>(source);
 
   CHECK ( CheckValid(), (*this) );
 }
@@ -337,6 +337,15 @@ int FeatureBuilder1::GetMinFeatureDrawScale() const
   return (minScale == -1 ? 1000 : minScale);
 }
 
+void FeatureBuilder1::SetCoastCell(int64_t cell)
+{
+  m_coastCell = cell;
+
+  FeatureParams params;
+  params.name.AddString(0, strings::to_string(cell));
+  SetParams(params);
+}
+
 string DebugPrint(FeatureBuilder1 const & f)
 {
   ostringstream out;
diff --git a/generator/feature_builder.hpp b/generator/feature_builder.hpp
index b93df2fe84..d3e2be106f 100644
--- a/generator/feature_builder.hpp
+++ b/generator/feature_builder.hpp
@@ -61,7 +61,7 @@ public:
   void Deserialize(buffer_t & data);
   //@}
 
-  ///@name Selectors.
+  /// @name Selectors.
   //@{
   inline m2::RectD GetLimitRect() const { return m_LimitRect; }
 
@@ -72,21 +72,45 @@ public:
 
   inline size_t GetPointsCount() const { return GetGeometry().size(); }
   inline size_t GetPolygonsCount() const { return m_Polygons.size(); }
+  //@}
+
+  /// @name Iterate through polygons points.
+  /// Stops processing when functor returns false.
+  //@{
+private:
+  template <class ToDo> class ToDoWrapper
+  {
+    ToDo & m_toDo;
+  public:
+    ToDoWrapper(ToDo & toDo) : m_toDo(toDo) {}
+    bool operator() (m2::PointD const & p) { return m_toDo(p); }
+    void EndRegion() {}
+  };
 
-  // stops processing when functor returns false
+public:
   template <class ToDo>
-  void ForEachGeometryPoint(ToDo & toDo) const
+  void ForEachGeometryPointEx(ToDo & toDo) const
   {
     if (m_Params.GetGeomType() == feature::GEOM_POINT)
       toDo(m_Center);
     else
     {
       for (list<points_t>::const_iterator i = m_Polygons.begin(); i != m_Polygons.end(); ++i)
+      {
         for (points_t::const_iterator j = i->begin(); j != i->end(); ++j)
           if (!toDo(*j))
             return;
+        toDo.EndRegion();
+      }
     }
   }
+
+  template <class ToDo>
+  void ForEachGeometryPoint(ToDo & toDo) const
+  {
+    ToDoWrapper<ToDo> wrapper(toDo);
+    ForEachGeometryPointEx(wrapper);
+  }
   //@}
 
   bool PreSerialize();
@@ -99,10 +123,10 @@ public:
 
   int GetMinFeatureDrawScale() const;
 
-  inline void SetCoastCell(uint32_t cell) { m_coastCell = cell; }
-  inline bool GetCoastCell(uint32_t & cell) const
+  void SetCoastCell(int64_t cell);
+  inline bool GetCoastCell(int64_t & cell) const
   {
-    if (m_coastCell != -1U)
+    if (m_coastCell != -1)
     {
       cell = m_coastCell;
       return true;
@@ -138,7 +162,7 @@ protected:
   /// List of geometry polygons.
   list<points_t> m_Polygons; // Check HEADER_IS_AREA
 
-  uint32_t m_coastCell;
+  int64_t m_coastCell;
 };
 
 /// Used for serialization of features during final pass.
diff --git a/generator/feature_generator.cpp b/generator/feature_generator.cpp
index 95e89d19cd..3517929a74 100644
--- a/generator/feature_generator.cpp
+++ b/generator/feature_generator.cpp
@@ -295,7 +295,7 @@ public:
     else
     {
       // 6 - is cell level for oceans covering
-      m_coasts.reset(new CoastlineFeaturesGenerator(m_coastType, 6));
+      m_coasts.reset(new CoastlineFeaturesGenerator(m_coastType, 4, 10, 20000));
 
       m_coastsHolder.reset(new FeaturesCollector(m_srcCoastsFile));
     }
@@ -338,13 +338,16 @@ public:
     {
       m_coasts->Finish();
 
-      size_t const count = m_coasts->GetFeaturesCount();
+      size_t const count = m_coasts->GetCellsCount();
       LOG(LINFO, ("Generating coastline polygons", count));
+
       for (size_t i = 0; i < count; ++i)
       {
-        FeatureBuilder1 fb;
-        if (m_coasts->GetFeature(i, fb))
-          (*m_coastsHolder)(fb);
+        vector<FeatureBuilder1> vecFb;
+        m_coasts->GetFeatures(i, vecFb);
+
+        for (size_t j = 0; j < vecFb.size(); ++j)
+          (*m_coastsHolder)(vecFb[j]);
       }
     }
     else if (m_coastsHolder)
diff --git a/generator/feature_sorter.cpp b/generator/feature_sorter.cpp
index 635c980e51..5b78ec9833 100644
--- a/generator/feature_sorter.cpp
+++ b/generator/feature_sorter.cpp
@@ -376,8 +376,8 @@ namespace feature
     void SimplifyPoints(points_t const & in, points_t & out, int level,
                         FeatureBuilder2 const & fb)
     {
-      uint32_t cellID;
-      if ((level >= scales::GetUpperWorldScale()) && fb.GetCoastCell(cellID))
+      int64_t dummy;
+      if ((level >= scales::GetUpperWorldScale()) && fb.GetCoastCell(dummy))
       {
         // Note! Do such special simplification only for upper world level and countries levels.
         // There is no need for this simplification in small world levels.