Area and line features clipped by tile rect.

5 files changed, 350 insertions, 0 deletions

diff --git a/geometry/clipping.cpp b/geometry/clipping.cpp
new file mode 100644
index 0000000000..0e708cc680
--- /dev/null
+++ b/geometry/clipping.cpp
@@ -0,0 +1,117 @@
+#include "clipping.hpp"
+
+#include "std/vector.hpp"
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/geometries/linestring.hpp>
+#include <boost/geometry/geometries/point_xy.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
+
+namespace m2
+{
+
+using TPoint = boost::geometry::model::d2::point_xy<double>;
+using TPolygon = boost::geometry::model::polygon<TPoint>;
+using TLine = boost::geometry::model::linestring<TPoint>;
+
+void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1,
+                        m2::PointD const & p2, m2::PointD const & p3,
+                        ClipTriangleByRectResultIt const & resultIterator)
+{
+  if (resultIterator == nullptr)
+    return;
+
+  if (rect.IsPointInside(p1) && rect.IsPointInside(p2) && rect.IsPointInside(p3))
+  {
+    resultIterator(p1, p2, p3);
+    return;
+  }
+
+  m2::PointD const rt = rect.RightTop();
+  m2::PointD const rb = rect.RightBottom();
+  m2::PointD const lt = rect.LeftTop();
+  m2::PointD const lb = rect.LeftBottom();
+  TPolygon rectanglePoly;
+  boost::geometry::assign_points(rectanglePoly,
+                                 vector<TPoint>{ TPoint(lt.x, lt.y), TPoint(rt.x, rt.y),
+                                                 TPoint(rb.x, rb.y), TPoint(lb.x, lb.y),
+                                                 TPoint(lt.x, lt.y) });
+  TPolygon trianglePoly;
+  boost::geometry::assign_points(trianglePoly,
+                                 vector<TPoint>{ TPoint(p1.x, p1.y), TPoint(p2.x, p2.y),
+                                                 TPoint(p3.x, p3.y), TPoint(p1.x, p1.y) });
+  vector<TPolygon> output;
+  if (!boost::geometry::intersection(rectanglePoly, trianglePoly, output) || output.empty())
+    return;
+
+  ASSERT_EQUAL(output.size(), 1, ());
+  m2::PointD firstPoint;
+  m2::PointD curPoint;
+  m2::PointD prevPoint;
+  size_t counter = 0;
+  size_t const pointsCount = boost::geometry::num_points(output.front());
+  boost::geometry::for_each_point(output.front(), [&resultIterator, &firstPoint,
+                                  &curPoint, &prevPoint, &counter, &pointsCount](TPoint const & p)
+  {
+    if (counter == 0)
+    {
+      firstPoint = m2::PointD(p.x(), p.y());
+      curPoint = firstPoint;
+    }
+    else
+    {
+      prevPoint = curPoint;
+      curPoint = m2::PointD(p.x(), p.y());
+    }
+    counter++;
+
+    if (counter > 2 && counter < pointsCount)
+      resultIterator(firstPoint, prevPoint, curPoint);
+  });
+}
+
+vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, m2::SharedSpline const & spline)
+{
+  vector<m2::SharedSpline> result;
+
+  m2::RectD splineRect;
+  for (m2::PointD const & p : spline->GetPath())
+    splineRect.Add(p);
+
+  if (rect.IsRectInside(splineRect))
+  {
+    result.push_back(spline);
+    return result;
+  }
+
+  m2::PointD const rt = rect.RightTop();
+  m2::PointD const rb = rect.RightBottom();
+  m2::PointD const lt = rect.LeftTop();
+  m2::PointD const lb = rect.LeftBottom();
+  TPolygon rectanglePoly;
+  boost::geometry::assign_points(rectanglePoly,
+                                 vector<TPoint>{ TPoint(lt.x, lt.y), TPoint(rt.x, rt.y),
+                                                 TPoint(rb.x, rb.y), TPoint(lb.x, lb.y),
+                                                 TPoint(lt.x, lt.y) });
+  TLine line;
+  line.reserve(spline->GetSize());
+  for (m2::PointD const & p : spline->GetPath())
+    line.push_back(TPoint(p.x, p.y));
+
+  vector<TLine> output;
+  if (!boost::geometry::intersection(rectanglePoly, line, output) || output.empty())
+    return result;
+
+  for (TLine const & outLine : output)
+  {
+    m2::SharedSpline s;
+    s.Reset(new m2::Spline(outLine.size()));
+    for (TPoint const & p : outLine)
+      s->AddPoint(m2::PointD(p.x(), p.y()));
+    result.push_back(move(s));
+  }
+
+  return result;
+}
+
+} // namespace m2;
diff --git a/geometry/clipping.hpp b/geometry/clipping.hpp
new file mode 100644
index 0000000000..58b7691d44
--- /dev/null
+++ b/geometry/clipping.hpp
@@ -0,0 +1,20 @@
+#pragma once
+
+#include "rect2d.hpp"
+#include "spline.hpp"
+#include "triangle2d.hpp"
+
+#include "std/function.hpp"
+
+namespace m2
+{
+
+using ClipTriangleByRectResultIt = function<void(m2::PointD const &, m2::PointD const &, m2::PointD const &)>;
+
+void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1,
+                        m2::PointD const & p2, m2::PointD const & p3,
+                        ClipTriangleByRectResultIt const & resultIterator);
+
+vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, m2::SharedSpline const & spline);
+
+} // namespace m2
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index ff07f193ff..bc560f64dd 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -11,6 +11,7 @@ include($$ROOT_DIR/common.pri)
 SOURCES += \
   algorithm.cpp \
   angles.cpp \
+  clipping.cpp \
   distance_on_sphere.cpp \
   latlon.cpp \
   mercator.cpp \
@@ -25,6 +26,7 @@ SOURCES += \
 HEADERS += \
   algorithm.hpp \
   angles.hpp \
+  clipping.hpp \
   any_rect2d.hpp \
   avg_vector.hpp \
   cellid.hpp \
diff --git a/geometry/geometry_tests/clipping_test.cpp b/geometry/geometry_tests/clipping_test.cpp
new file mode 100644
index 0000000000..bfe740d296
--- /dev/null
+++ b/geometry/geometry_tests/clipping_test.cpp
@@ -0,0 +1,210 @@
+#include "testing/testing.hpp"
+
+#include "geometry/clipping.hpp"
+
+namespace
+{
+
+bool CompareTriangleLists(vector<m2::PointD> const & list1, vector<m2::PointD> const & list2)
+{
+  if (list1.size() != list2.size())
+    return false;
+
+  double const kEps = 1e-5;
+  for (size_t i = 0; i < list1.size(); i++)
+    if (!list1[i].EqualDxDy(list2[i], kEps))
+      return false;
+
+  return true;
+}
+
+bool CompareSplineLists(vector<m2::SharedSpline> const & list1, vector<m2::SharedSpline> const & list2)
+{
+  if (list1.size() != list2.size())
+    return false;
+
+  double const kEps = 1e-5;
+  for (size_t i = 0; i < list1.size(); i++)
+  {
+    auto & path1 = list1[i]->GetPath();
+    auto & path2 = list2[i]->GetPath();
+    if (path1.size() != path2.size())
+      return false;
+
+    for (size_t j = 0; j < path1.size(); j++)
+      if (!path1[j].EqualDxDy(path2[j], kEps))
+        return false;
+  }
+
+  return true;
+}
+
+vector<m2::SharedSpline> ConstructSplineList(vector<vector<m2::PointD>> const & segments)
+{
+  vector<m2::SharedSpline> result;
+  result.reserve(segments.size());
+  for (size_t i = 0; i < segments.size(); i++)
+  {
+    m2::SharedSpline s;
+    s.Reset(new m2::Spline(segments[i].size()));
+    for (size_t j = 0; j < segments[i].size(); j++)
+      s->AddPoint(segments[i][j]);
+    result.push_back(move(s));
+  }
+  return result;
+}
+
+} // namespace
+
+UNIT_TEST(Clipping_ClipTriangleByRect)
+{
+  m2::RectD r(-1.0, -1.0, 1.0, 1.0);
+
+  // Completely inside.
+  vector<m2::PointD> result1;
+  m2::ClipTriangleByRect(r, m2::PointD(0.5, 0.5), m2::PointD(0.5, -0.5), m2::PointD(0.0, 0.0),
+                         [&result1](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result1.push_back(p1);
+    result1.push_back(p2);
+    result1.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult1 = { m2::PointD(0.5, 0.5), m2::PointD(0.5, -0.5), m2::PointD(0.0, 0.0) };
+  TEST(CompareTriangleLists(result1, expectedResult1), (result1, expectedResult1));
+
+  // 1 point inside.
+  vector<m2::PointD> result2;
+  m2::ClipTriangleByRect(r, m2::PointD(0.0, 0.0), m2::PointD(2.0, 2.0), m2::PointD(2.0, -2.0),
+                         [&result2](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result2.push_back(p1);
+    result2.push_back(p2);
+    result2.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult2 = { m2::PointD(1.0, 1.0), m2::PointD(1.0, -1.0), m2::PointD(0.0, 0.0) };
+  TEST(CompareTriangleLists(result2, expectedResult2), (result2, expectedResult2));
+
+  // 2 points inside.
+  vector<m2::PointD> result3;
+  m2::ClipTriangleByRect(r, m2::PointD(0.0, 0.5), m2::PointD(2.0, 0.0), m2::PointD(0.0, -0.5),
+                         [&result3](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result3.push_back(p1);
+    result3.push_back(p2);
+    result3.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult3 = { m2::PointD(1.0, 0.25), m2::PointD(1.0, -0.25), m2::PointD(0.0, -0.5),
+                                         m2::PointD(1.0, 0.25), m2::PointD(0.0, -0.5), m2::PointD(0.0, 0.5) };
+  TEST(CompareTriangleLists(result3, expectedResult3), (result3, expectedResult3));
+
+  // 2 edges clipping.
+  vector<m2::PointD> result4;
+  m2::ClipTriangleByRect(r, m2::PointD(0.0, 0.0), m2::PointD(0.0, 1.5), m2::PointD(1.5, 0.0),
+                         [&result4](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result4.push_back(p1);
+    result4.push_back(p2);
+    result4.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult4 = { m2::PointD(0.0, 1.0), m2::PointD(0.5, 1.0), m2::PointD(1.0, 0.5),
+                                         m2::PointD(0.0, 1.0), m2::PointD(1.0, 0.5), m2::PointD(1.0, 0.0),
+                                         m2::PointD(0.0, 1.0), m2::PointD(1.0, 0.0), m2::PointD(0.0, 0.0) };
+  TEST(CompareTriangleLists(result4, expectedResult4), (result4, expectedResult4));
+
+  // 3 edges clipping.
+  vector<m2::PointD> result5;
+  m2::ClipTriangleByRect(r, m2::PointD(-1.5, 0.0), m2::PointD(0.0, 1.5), m2::PointD(1.5, 0.0),
+                         [&result5](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result5.push_back(p1);
+    result5.push_back(p2);
+    result5.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult5 = { m2::PointD(-0.5, 1.0), m2::PointD(0.5, 1.0), m2::PointD(1.0, 0.5),
+                                         m2::PointD(-0.5, 1.0), m2::PointD(1.0, 0.5), m2::PointD(1.0, 0.0),
+                                         m2::PointD(-0.5, 1.0), m2::PointD(1.0, 0.0), m2::PointD(-1.0, 0.0),
+                                         m2::PointD(-0.5, 1.0), m2::PointD(-1.0, 0.0), m2::PointD(-1.0, 0.5) };
+  TEST(CompareTriangleLists(result5, expectedResult5), (result5, expectedResult5));
+
+  // Completely outside.
+  vector<m2::PointD> result6;
+  m2::ClipTriangleByRect(r, m2::PointD(1.5, 1.5), m2::PointD(1.5, -1.5), m2::PointD(2.0, 0.0),
+                         [&result6](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result6.push_back(p1);
+    result6.push_back(p2);
+    result6.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult6 = {};
+  TEST(CompareTriangleLists(result6, expectedResult6), (result6, expectedResult6));
+
+  // Clip with an angle of rect.
+  vector<m2::PointD> result7;
+  m2::ClipTriangleByRect(r, m2::PointD(0.5, 0.5), m2::PointD(0.5, 2.0), m2::PointD(2.0, 0.5),
+                         [&result7](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result7.push_back(p1);
+    result7.push_back(p2);
+    result7.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult7 = { m2::PointD(0.5, 1.0), m2::PointD(1.0, 1.0), m2::PointD(1.0, 0.5),
+                                         m2::PointD(0.5, 1.0), m2::PointD(1.0, 0.5), m2::PointD(0.5, 0.5) };
+  TEST(CompareTriangleLists(result7, expectedResult7), (result7, expectedResult7));
+
+  // Triangle covers rect.
+  vector<m2::PointD> result8;
+  m2::ClipTriangleByRect(r, m2::PointD(0.0, 3.0), m2::PointD(5.0, -2.0), m2::PointD(-5.0, -2.0),
+                         [&result8](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result8.push_back(p1);
+    result8.push_back(p2);
+    result8.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult8 = { m2::PointD(-1.0, 1.0), m2::PointD(1.0, 1.0), m2::PointD(1.0, -1.0),
+                                         m2::PointD(-1.0, 1.0), m2::PointD(1.0, -1.0), m2::PointD(-1.0, -1.0) };
+  TEST(CompareTriangleLists(result8, expectedResult8), (result8, expectedResult8));
+}
+
+UNIT_TEST(Clipping_ClipSplineByRect)
+{
+  m2::RectD r(-1.0, -1.0, 1.0, 1.0);
+
+  // Intersection.
+  m2::SharedSpline spline1;
+  spline1.Reset(new m2::Spline(2));
+  spline1->AddPoint(m2::PointD(-2.0, 0.0));
+  spline1->AddPoint(m2::PointD(2.0, 1.0));
+  vector<m2::SharedSpline> result1 = m2::ClipSplineByRect(r, spline1);
+  vector<m2::SharedSpline> expectedResult1 = ConstructSplineList({ { m2::PointD(-1.0, 0.25), m2::PointD(1.0, 0.75) } });
+  TEST(CompareSplineLists(result1, expectedResult1), ());
+
+  // Intersection. Several segments.
+  m2::SharedSpline spline2;
+  spline2.Reset(new m2::Spline(4));
+  spline2->AddPoint(m2::PointD(-2.0, 0.0));
+  spline2->AddPoint(m2::PointD(2.0, 1.0));
+  spline2->AddPoint(m2::PointD(0.5, -2.0));
+  spline2->AddPoint(m2::PointD(-0.5, -0.5));
+  vector<m2::SharedSpline> result2 = m2::ClipSplineByRect(r, spline2);
+  vector<m2::SharedSpline> expectedResult2 = ConstructSplineList({ { m2::PointD(-1.0, 0.25), m2::PointD(1.0, 0.75) },
+                                                                   { m2::PointD(-0.166666666, -1.0), m2::PointD(-0.5, -0.5) } });
+  TEST(CompareSplineLists(result2, expectedResult2), ());
+
+  // Completely outside.
+  m2::SharedSpline spline3;
+  spline3.Reset(new m2::Spline(2));
+  spline3->AddPoint(m2::PointD(-2.0, 2.0));
+  spline3->AddPoint(m2::PointD(2.0, 3.0));
+  vector<m2::SharedSpline> result3 = m2::ClipSplineByRect(r, spline3);
+  vector<m2::SharedSpline> expectedResult3 = {};
+  TEST(CompareSplineLists(result3, expectedResult3), ());
+
+  // Completely inside.
+  m2::SharedSpline spline4;
+  spline4.Reset(new m2::Spline(2));
+  spline4->AddPoint(m2::PointD(-0.5, 0.0));
+  spline4->AddPoint(m2::PointD(0.5, 0.5));
+  vector<m2::SharedSpline> result4 = m2::ClipSplineByRect(r, spline4);
+  vector<m2::SharedSpline> expectedResult4 = ConstructSplineList({ { m2::PointD(-0.5, 0.0), m2::PointD(0.5, 0.5) } });
+  TEST(CompareSplineLists(result4, expectedResult4), ());
+}
diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro
index 050968f793..8164b90f71 100644
--- a/geometry/geometry_tests/geometry_tests.pro
+++ b/geometry/geometry_tests/geometry_tests.pro
@@ -23,6 +23,7 @@ SOURCES += \
   angle_test.cpp \
   anyrect_test.cpp \
   cellid_test.cpp \
+  clipping_test.cpp \
   common_test.cpp \
   covering_test.cpp \
   distance_on_sphere_test.cpp \