Fix infinite loop in rect-section interaction.

Add unit tests.
Russian to english comments.

2 files changed, 29 insertions, 17 deletions

diff --git a/geometry/geometry_tests/intersect_test.cpp b/geometry/geometry_tests/intersect_test.cpp
index 052e09334a..ddec9a3ef8 100644
--- a/geometry/geometry_tests/intersect_test.cpp
+++ b/geometry/geometry_tests/intersect_test.cpp
@@ -171,3 +171,12 @@ UNIT_TEST(IntersectRect_Point)
     }
   }
 }
+
+UNIT_TEST(IntersectRect_NAN)
+{
+  m2::RectD r(-47.622792787168442885, -8.5438097219402173721, 134.06976090684074165, 9.0000000000000337508);
+  m2::PointD p1(134.06976090684077008, 9.0000000000001847411);
+  m2::PointD p2(134.06976090684074165, -8.5438097219401640814);
+
+  m2::Intersect(r, p1, p2);
+}
diff --git a/geometry/rect_intersect.hpp b/geometry/rect_intersect.hpp
index 2897b8f772..86cb903335 100644
--- a/geometry/rect_intersect.hpp
+++ b/geometry/rect_intersect.hpp
@@ -7,18 +7,20 @@ namespace m2
 {
   namespace detail
   {
-    static const int LEFT = 1;    // äâîè÷íîå 0001
-    static const int RIGHT = 2;   // äâîè÷íîå 0010
-    static const int BOT = 4;     // äâîè÷íîå 0100
-    static const int TOP = 8;     // äâîè÷íîå 1000
+    // bit masks for code kinds
+    static const int LEFT = 1;
+    static const int RIGHT = 2;
+    static const int BOT = 4;
+    static const int TOP = 8;
 
+    // return accumulated bit mask for point-rect interaction
     template <class T>
     int vcode(m2::Rect<T> const & r, m2::Point<T> const & p)
     {
-      return ((p.x < r.minX() ? LEFT : 0)  +    // +1 åñëè òî÷êà ëåâåå ïðÿìîóãîëüíèêà
-              (p.x > r.maxX() ? RIGHT : 0) +    // +2 åñëè òî÷êà ïðàâåå ïðÿìîóãîëüíèêà
-              (p.y < r.minY() ? BOT : 0)   +    // +4 åñëè òî÷êà íèæå ïðÿìîóãîëüíèêà
-              (p.y > r.maxY() ? TOP : 0));      // +8 åñëè òî÷êà âûøå ïðÿìîóãîëüíèêà
+      return ((p.x < r.minX() ? LEFT : 0)  +
+              (p.x > r.maxX() ? RIGHT : 0) +
+              (p.y < r.minY() ? BOT : 0)   +
+              (p.y > r.maxY() ? TOP : 0));
     }
   }
 
@@ -27,16 +29,16 @@ namespace m2
   {
     int code[2] = { detail::vcode(r, p1), detail::vcode(r, p2) };
 
-    // ïîêà îäíà èç òî÷åê îòðåçêà âíå ïðÿìîóãîëüíèêà
+    // do while one of the point is out of rect
     while (code[0] || code[1])
     {
       if (code[0] & code[1])
       {
-        // åñëè îáå òî÷êè ñ îäíîé ñòîðîíû ïðÿìîóãîëüíèêà, òî îòðåçîê íå ïåðåñåêàåò ïðÿìîóãîëüíèê
+        // both point area on the one side of rect
         return false;
       }
 
-      // âûáèðàåì òî÷êó c ñ íåíóëåâûì êîäîì
+      // choose point with non-zero code
       m2::Point<T> * pp;
       int i;
       if (code[0])
@@ -50,37 +52,38 @@ namespace m2
         pp = &p2;
       }
 
-      // åñëè pp ëåâåå r, òî ïåðåäâèãàåì pp íà ïðÿìóþ x = r->x_min
-      // åñëè pp ïðàâåå r, òî ïåðåäâèãàåì pp íà ïðÿìóþ x = r->x_max
+      // added points compare to avoid NAN numbers
       if (code[i] & detail::LEFT)
       {
+        if (p1 == p2) return false;
         pp->y += (p1.y - p2.y) * (r.minX() - pp->x) / (p1.x - p2.x);
         pp->x = r.minX();
       }
       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();
       }
 
-      // åñëè pp íèæå r, òî ïåðåäâèãàåì pp íà ïðÿìóþ y = r->y_min
-      // åñëè pp âûøå r, òî ïåðåäâèãàåì pp íà ïðÿìóþ y = r->y_max
       if (code[i] & detail::BOT)
       {
+        if (p1 == p2) return false;
         pp->x += (p1.x - p2.x) * (r.minY() - pp->y) / (p1.y - p2.y);
         pp->y = r.minY();
       }
       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();
       }
 
-      // îáíîâëÿåì êîä
+      // update code with new point
       code[i] = detail::vcode(r, *pp);
     }
 
-    // îáà êîäà ðàâíû 0, ñëåäîâàòåëüíî îáå òî÷êè â ïðÿìîóãîëüíèêå
+    // both codes are equal to zero => points area inside rect
     return true;
   }
 }