Clipping triangles by rect algorithm changed.

3 files changed, 172 insertions, 51 deletions

diff --git a/geometry/clipping.cpp b/geometry/clipping.cpp
index 0e708cc680..5faa3d215a 100644
--- a/geometry/clipping.cpp
+++ b/geometry/clipping.cpp
@@ -1,4 +1,5 @@
 #include "clipping.hpp"
+#include "rect_intersect.hpp"
 
 #include "std/vector.hpp"
 
@@ -14,60 +15,126 @@ using TPoint = boost::geometry::model::d2::point_xy<double>;
 using TPolygon = boost::geometry::model::polygon<TPoint>;
 using TLine = boost::geometry::model::linestring<TPoint>;
 
+using AddPoligonPoint = function<void(m2::PointD const &)>;
+using InsertCorners = function<void(int, int)>;
+
+bool IntersectEdge(m2::RectD const & rect, m2::PointD const & pp1, m2::PointD const & pp2,
+                   InsertCorners const & insertCorners, AddPoligonPoint const & addPoligonPoint,
+                   int prevClipCode, int nextClipCode, int & firstClipCode, int & lastClipCode)
+{
+  m2::PointD p1 = pp1;
+  m2::PointD p2 = pp2;
+
+  if (m2::Intersect(rect, p1, p2, firstClipCode, lastClipCode))
+  {
+    if (firstClipCode != 0 && prevClipCode != 0 && ((firstClipCode & prevClipCode) == 0))
+      insertCorners(prevClipCode, firstClipCode);
+
+    addPoligonPoint(p1);
+    addPoligonPoint(p2);
+
+    if (lastClipCode != 0 && nextClipCode != 0 && ((lastClipCode & nextClipCode) == 0) &&
+        firstClipCode != lastClipCode && prevClipCode != nextClipCode)
+      insertCorners(lastClipCode, nextClipCode);
+
+    return true;
+  }
+  else if (prevClipCode != 0 && nextClipCode != 0)
+  {
+    insertCorners(prevClipCode, nextClipCode);
+  }
+  return false;
+}
+
+int GetRectSideIndex(int code)
+{
+  if (code == m2::detail::LEFT)
+    return 0;
+  if (code == m2::detail::TOP)
+    return 1;
+  if (code == m2::detail::RIGHT)
+    return 2;
+  return 3;
+}
+
 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;
+  const int kAveragePoligonSize = 3;
+  const double kEps = 1e-8;
+
+  vector<m2::PointD> poligon;
+  poligon.reserve(kAveragePoligonSize);
+  auto const addPoligonPoint = [&poligon, kEps](m2::PointD const & pt)
+  {
+    if (poligon.empty() || !poligon.back().EqualDxDy(pt, kEps))
+      poligon.push_back(pt);
+  };
 
-  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)
+  vector<m2::PointD> const corners = { rect.LeftTop(), rect.RightTop(), rect.RightBottom(), rect.LeftBottom() };
+  auto const insertCorners = [&corners, rect, p1, p2, p3, addPoligonPoint](int code1, int code2)
   {
-    if (counter == 0)
+    int cornerInd = GetRectSideIndex(code1);
+    int endCornerInd = GetRectSideIndex(code2);
+
+    if (!IsPointInsideTriangle(corners[cornerInd], p1, p2, p3))
     {
-      firstPoint = m2::PointD(p.x(), p.y());
-      curPoint = firstPoint;
+      if (!IsPointInsideTriangle(corners[endCornerInd], p1, p2, p3))
+        return;
+      swap(cornerInd, endCornerInd);
     }
-    else
+
+    while (cornerInd != endCornerInd)
+    {
+      addPoligonPoint(corners[cornerInd]);
+      cornerInd = (cornerInd + 1) % 4;
+    }
+  };
+
+  int firstClipCode[3];
+  int lastClipCode[3];
+  bool intersected[3];
+
+  intersected[0] = IntersectEdge(rect, p1, p2, insertCorners, addPoligonPoint,
+                                 0, 0, firstClipCode[0], lastClipCode[0]);
+
+  intersected[1] = IntersectEdge(rect, p2, p3, insertCorners, addPoligonPoint,
+                                 lastClipCode[0], 0, firstClipCode[1], lastClipCode[1]);
+
+  intersected[2] = IntersectEdge(rect, p3, p1, insertCorners, addPoligonPoint,
+                                 lastClipCode[1] != 0 ? lastClipCode[1] : lastClipCode[0],
+                                 firstClipCode[0] != 0 ? firstClipCode[0] : firstClipCode[1],
+                                 firstClipCode[2], lastClipCode[2]);
+
+  int const intersectCount = intersected[0] + intersected[1] + intersected[2];
+  if (intersectCount == 0)
+  {
+    if (IsPointInsideTriangle(rect.Center(), p1, p2, p3))
     {
-      prevPoint = curPoint;
-      curPoint = m2::PointD(p.x(), p.y());
+      resultIterator(rect.LeftTop(), rect.RightTop(), rect.RightBottom());
+      resultIterator(rect.RightBottom(), rect.LeftBottom(), rect.LeftTop());
     }
-    counter++;
+    return;
+  }
+
+  if (intersectCount == 1 && intersected[2])
+    insertCorners(lastClipCode[2], firstClipCode[2]);
+
+  if (!poligon.empty() && poligon.back().EqualDxDy(poligon[0], kEps))
+    poligon.pop_back();
+
+  if (poligon.size() < 3)
+    return;
 
-    if (counter > 2 && counter < pointsCount)
-      resultIterator(firstPoint, prevPoint, curPoint);
-  });
+  for (size_t i = 0; i < poligon.size() - 2; ++i)
+    resultIterator(poligon[0], poligon[i + 1], poligon[i + 2]);
 }
 
 vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, m2::SharedSpline const & spline)
diff --git a/geometry/geometry_tests/clipping_test.cpp b/geometry/geometry_tests/clipping_test.cpp
index bfe740d296..212dbc7051 100644
--- a/geometry/geometry_tests/clipping_test.cpp
+++ b/geometry/geometry_tests/clipping_test.cpp
@@ -81,7 +81,7 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+  vector<m2::PointD> expectedResult2 = { m2::PointD(0.0, 0.0), m2::PointD(1.0, 1.0), m2::PointD(1.0, -1.0) };
   TEST(CompareTriangleLists(result2, expectedResult2), (result2, expectedResult2));
 
   // 2 points inside.
@@ -93,8 +93,8 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+  vector<m2::PointD> expectedResult3 = { m2::PointD(0.0, 0.5), 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) };
   TEST(CompareTriangleLists(result3, expectedResult3), (result3, expectedResult3));
 
   // 2 edges clipping.
@@ -106,9 +106,9 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+  vector<m2::PointD> expectedResult4 = { m2::PointD(0.0, 0.0), m2::PointD(0.0, 1.0), m2::PointD(0.5, 1.0),
+                                         m2::PointD(0.0, 0.0), m2::PointD(0.5, 1.0), m2::PointD(1.0, 0.5),
+                                         m2::PointD(0.0, 0.0), m2::PointD(1.0, 0.5), m2::PointD(1.0, 0.0) };
   TEST(CompareTriangleLists(result4, expectedResult4), (result4, expectedResult4));
 
   // 3 edges clipping.
@@ -120,10 +120,10 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+  vector<m2::PointD> expectedResult5 = { m2::PointD(-1.0, 0.5), 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.5), m2::PointD(1.0, 0.5), m2::PointD(1.0, 0.0),
+                                         m2::PointD(-1.0, 0.5), m2::PointD(1.0, 0.0), m2::PointD(-1.0, 0.0) };
   TEST(CompareTriangleLists(result5, expectedResult5), (result5, expectedResult5));
 
   // Completely outside.
@@ -147,8 +147,8 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+  vector<m2::PointD> expectedResult7 = { m2::PointD(0.5, 0.5), m2::PointD(0.5, 1.0), m2::PointD(1.0, 1.0),
+                                         m2::PointD(0.5, 0.5), m2::PointD(1.0, 1.0), m2::PointD(1.0, 0.5) };
   TEST(CompareTriangleLists(result7, expectedResult7), (result7, expectedResult7));
 
   // Triangle covers rect.
@@ -161,8 +161,47 @@ UNIT_TEST(Clipping_ClipTriangleByRect)
     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) };
+                                         m2::PointD(1.0, -1.0), m2::PointD(-1.0, -1.0), m2::PointD(-1.0, 1.0) };
   TEST(CompareTriangleLists(result8, expectedResult8), (result8, expectedResult8));
+
+  // Clip with an angle of rect.
+  vector<m2::PointD> result9;
+  m2::ClipTriangleByRect(r, m2::PointD(1.5, 0.0), m2::PointD(1.5, -1.5), m2::PointD(0.0, -1.5),
+                         [&result9](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result9.push_back(p1);
+    result9.push_back(p2);
+    result9.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult9 = { m2::PointD(0.5, -1.0), m2::PointD(1.0, -0.5), m2::PointD(1.0, -1.0) };
+  TEST(CompareTriangleLists(result9, expectedResult9), (result9, expectedResult9));
+
+  // Clip with an angle of rect.
+  vector<m2::PointD> result10;
+  m2::ClipTriangleByRect(r, m2::PointD(-2.0, -0.5), m2::PointD(-0.5, -0.5), m2::PointD(-0.5, -2.0),
+                         [&result10](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result10.push_back(p1);
+    result10.push_back(p2);
+    result10.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult10 = { m2::PointD(-1.0, -0.5), m2::PointD(-0.5, -0.5), m2::PointD(-0.5, -1.0),
+                                          m2::PointD(-1.0, -0.5), m2::PointD(-0.5, -1.0), m2::PointD(-1.0, -1.0) };
+  TEST(CompareTriangleLists(result10, expectedResult10), (result10, expectedResult10));
+
+  // Clip with 3 angles of rect.
+  vector<m2::PointD> result11;
+  m2::ClipTriangleByRect(r, m2::PointD(2.0, -3.0), m2::PointD(-2.0, 1.0), m2::PointD(2.0, 2.0),
+                         [&result11](m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3)
+  {
+    result11.push_back(p1);
+    result11.push_back(p2);
+    result11.push_back(p3);
+  });
+  vector<m2::PointD> expectedResult11 = { m2::PointD(0.0, -1.0), m2::PointD(-1.0, 0.0), m2::PointD(-1.0, 1.0),
+                                          m2::PointD(0.0, -1.0), m2::PointD(-1.0, 1.0), m2::PointD(1.0, 1.0),
+                                          m2::PointD(0.0, -1.0), m2::PointD(1.0, 1.0), m2::PointD(1.0, -1.0) };
+  TEST(CompareTriangleLists(result11, expectedResult11), (result11, expectedResult11));
 }
 
 UNIT_TEST(Clipping_ClipSplineByRect)
diff --git a/geometry/rect_intersect.hpp b/geometry/rect_intersect.hpp
index 8378ac7fc6..445e2381ed 100644
--- a/geometry/rect_intersect.hpp
+++ b/geometry/rect_intersect.hpp
@@ -25,8 +25,10 @@ namespace m2
   }
 
   template <class T>
-  bool Intersect(m2::Rect<T> const & r, m2::Point<T> & p1, m2::Point<T> & p2)
+  bool Intersect(m2::Rect<T> const & r, m2::Point<T> & p1, m2::Point<T> & p2, int & code1, int & code2)
   {
+    code1 = code2 = 0;
+    int codeClip[2] = { 0, 0 };
     int code[2] = { detail::vcode(r, p1), detail::vcode(r, p2) };
 
     // do while one of the point is out of rect
@@ -58,12 +60,14 @@ namespace m2
         if (p1 == p2) return false;
         pp->y += (p1.y - p2.y) * (r.minX() - pp->x) / (p1.x - p2.x);
         pp->x = r.minX();
+        codeClip[i] = detail::LEFT;
       }
       else if (code[i] & detail::RIGHT)
       {
         if (p1 == p2) return false;
         pp->y += (p1.y - p2.y) * (r.maxX() - pp->x) / (p1.x - p2.x);
         pp->x = r.maxX();
+        codeClip[i] = detail::RIGHT;
       }
 
       if (code[i] & detail::BOT)
@@ -71,19 +75,30 @@ namespace m2
         if (p1 == p2) return false;
         pp->x += (p1.x - p2.x) * (r.minY() - pp->y) / (p1.y - p2.y);
         pp->y = r.minY();
+        codeClip[i] = detail::BOT;
       }
       else if (code[i] & detail::TOP)
       {
         if (p1 == p2) return false;
         pp->x += (p1.x - p2.x) * (r.maxY() - pp->y) / (p1.y - p2.y);
         pp->y = r.maxY();
+        codeClip[i] = detail::TOP;
       }
 
       // update code with new point
       code[i] = detail::vcode(r, *pp);
     }
 
+    code1 = codeClip[0];
+    code2 = codeClip[1];
     // both codes are equal to zero => points area inside rect
     return true;
   }
+
+  template <class T>
+  bool Intersect(m2::Rect<T> const & r, m2::Point<T> & p1, m2::Point<T> & p2)
+  {
+    int code1, code2;
+    return Intersect(r, p1, p2, code1, code2);
+  }
 }