Refactored some geometry functions.

Correct implementation of feature::GetMinDistanceMeters().

12 files changed, 132 insertions, 94 deletions

diff --git a/geometry/covering_utils.hpp b/geometry/covering_utils.hpp
index 83d9c06cb4..24556eead2 100644
--- a/geometry/covering_utils.hpp
+++ b/geometry/covering_utils.hpp
@@ -1,10 +1,14 @@
 #pragma once
-#include "geometry/point2d.hpp"
+#include "point2d.hpp"
+#include "robust_orientation.hpp"
+#include "triangle2d.hpp"
+
 #include "base/assert.hpp"
 #include "base/base.hpp"
 #include "base/buffer_vector.hpp"
 #include "base/logging.hpp"
 #include "base/math.hpp"
+
 #include "std/algorithm.hpp"
 
 namespace covering
@@ -35,7 +39,7 @@ inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell,
     m2::PointD(xy.first + r, xy.second - r)
   };
   for (int i = 0; i < 4; ++i)
-    if (m2::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1]))
+    if (m2::robust::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1]))
       return CELL_OBJECT_INTERSECT;
   if (xy.first - r <= a.x && a.x <= xy.first + r && xy.second - r <= a.y && a.y <= xy.second + r)
     return OBJECT_INSIDE_CELL;
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index d51bfbb054..c53293ca49 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -18,6 +18,7 @@ SOURCES += \
   robust_orientation.cpp \
   screenbase.cpp \
   spline.cpp \
+  triangle2d.cpp \
 
 HEADERS += \
   angles.hpp \
diff --git a/geometry/geometry_tests/point_test.cpp b/geometry/geometry_tests/point_test.cpp
index 116c8ef246..0c15ef621b 100644
--- a/geometry/geometry_tests/point_test.cpp
+++ b/geometry/geometry_tests/point_test.cpp
@@ -1,7 +1,9 @@
-#include "base/SRC_FIRST.hpp"
 #include "testing/testing.hpp"
+
 #include "geometry/geometry_tests/equality.hpp"
 #include "geometry/point2d.hpp"
+#include "geometry/triangle2d.hpp"
+
 
 UNIT_TEST(Point_Rotate)
 {
diff --git a/geometry/geometry_tests/polygon_test.cpp b/geometry/geometry_tests/polygon_test.cpp
index 8fd6d5970d..6f62603c97 100644
--- a/geometry/geometry_tests/polygon_test.cpp
+++ b/geometry/geometry_tests/polygon_test.cpp
@@ -9,10 +9,9 @@
 #include "std/algorithm.hpp"
 
 
-namespace
-{
-  typedef m2::PointD P;
-}
+namespace { typedef m2::PointD P; }
+
+using namespace m2::robust;
 
 UNIT_TEST(IsSegmentInCone)
 {
diff --git a/geometry/geometry_tests/robust_test.cpp b/geometry/geometry_tests/robust_test.cpp
index 04e5f356c2..0eb3d79091 100644
--- a/geometry/geometry_tests/robust_test.cpp
+++ b/geometry/geometry_tests/robust_test.cpp
@@ -1,20 +1,47 @@
 #include "testing/testing.hpp"
 
 #include "geometry/robust_orientation.hpp"
+#include "geometry/triangle2d.hpp"
 
 
-typedef m2::PointD P;
+using namespace m2::robust;
 
 namespace
 {
+  typedef m2::PointD P;
+
   template <typename IterT> void CheckSelfIntersections(IterT beg, IterT end, bool res)
   {
-    TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), res, ());
+    TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ());
     typedef std::reverse_iterator<IterT> ReverseIterT;
-    TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ());
+    TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ());
   }
 }
 
+UNIT_TEST(OrientedS_Smoke)
+{
+  m2::PointD arr[] = {{-1, -1}, {0, 0}, {1, -1}};
+  TEST(OrientedS(arr[0], arr[2], arr[1]) > 0, ());
+  TEST(OrientedS(arr[2], arr[0], arr[1]) < 0, ());
+}
+
+UNIT_TEST(Triangle_Smoke)
+{
+  m2::PointD arr[] = {{0, 0}, {0, 3}, {3, 0}};
+
+  TEST(IsPointInsideTriangle(arr[0], arr[0], arr[1], arr[2]), ());
+  TEST(IsPointInsideTriangle(arr[1], arr[0], arr[1], arr[2]), ());
+  TEST(IsPointInsideTriangle(arr[2], arr[0], arr[1], arr[2]), ());
+  TEST(IsPointInsideTriangle({1, 1}, arr[0], arr[1], arr[2]), ());
+  TEST(IsPointInsideTriangle({1, 2}, arr[0], arr[1], arr[2]), ());
+  TEST(IsPointInsideTriangle({2, 1}, arr[0], arr[1], arr[2]), ());
+
+  double constexpr eps = 1.0E-10;
+  TEST(!IsPointInsideTriangle({-eps, -eps}, arr[0], arr[1], arr[2]), ());
+  TEST(!IsPointInsideTriangle({1 + eps, 2}, arr[0], arr[1], arr[2]), ());
+  TEST(!IsPointInsideTriangle({2, 1 + eps}, arr[0], arr[1], arr[2]), ());
+}
+
 UNIT_TEST(PolygonSelfIntersections_IntersectSmoke)
 {
   {
diff --git a/geometry/geometry_tests/segments_intersect_test.cpp b/geometry/geometry_tests/segments_intersect_test.cpp
index a92c62c163..d10369864f 100644
--- a/geometry/geometry_tests/segments_intersect_test.cpp
+++ b/geometry/geometry_tests/segments_intersect_test.cpp
@@ -1,18 +1,20 @@
 #include "testing/testing.hpp"
-#include "geometry/point2d.hpp"
+
+#include "geometry/robust_orientation.hpp"
+
 
 typedef m2::PointD P;
 
 bool SegmentsIntersect(P a, P b, P c, P d)
 {
-  bool res = m2::SegmentsIntersect(a, b, c, d);
-  TEST_EQUAL(res, m2::SegmentsIntersect(a, b, d, c), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(b, a, c, d), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(b, a, d, c), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(c, d, a, b), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(c, d, b, a), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(d, c, a, b), (a, b, c, d));
-  TEST_EQUAL(res, m2::SegmentsIntersect(d, c, b, a), (a, b, c, d));
+  bool const res = m2::robust::SegmentsIntersect(a, b, c, d);
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(a, b, d, c), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(b, a, c, d), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(b, a, d, c), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(c, d, a, b), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(c, d, b, a), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(d, c, a, b), (a, b, c, d));
+  TEST_EQUAL(res, m2::robust::SegmentsIntersect(d, c, b, a), (a, b, c, d));
   return res;
 }
 
diff --git a/geometry/point2d.hpp b/geometry/point2d.hpp
index 23a3597966..142a5c0641 100644
--- a/geometry/point2d.hpp
+++ b/geometry/point2d.hpp
@@ -245,78 +245,6 @@ namespace m2
     return res;
   }
 
-  template <typename T>
-  bool IsPointInsideTriangle(Point<T> const & p,
-                                     Point<T> const & a, Point<T> const & b, Point<T> const & c)
-  {
-    T const cpab = CrossProduct(b - a, p - a);
-    T const cpbc = CrossProduct(c - b, p - b);
-    T const cpca = CrossProduct(a - c, p - c);
-    return (cpab <= 0 && cpbc <= 0 && cpca <= 0) || (cpab >= 0 && cpbc >= 0 && cpca >= 0);
-  }
-
-  template <typename T>
-  bool IsPointStrictlyInsideTriangle(Point<T> const & p,
-                                     Point<T> const & a, Point<T> const & b, Point<T> const & c)
-  {
-    T const cpab = CrossProduct(b - a, p - a);
-    T const cpbc = CrossProduct(c - b, p - b);
-    T const cpca = CrossProduct(a - c, p - c);
-    return (cpab < 0 && cpbc < 0 && cpca < 0) || (cpab > 0 && cpbc > 0 && cpca > 0);
-  }
-
-  template <typename T>
-  bool SegmentsIntersect(Point<T> const & a, Point<T> const & b,
-                         Point<T> const & c, Point<T> const & d)
-  {
-    return
-        max(a.x, b.x) >= min(c.x, d.x) &&
-        min(a.x, b.x) <= max(c.x, d.x) &&
-        max(a.y, b.y) >= min(c.y, d.y) &&
-        min(a.y, b.y) <= max(c.y, d.y) &&
-        CrossProduct(c - a, b - a) * CrossProduct(d - a, b - a) <= 0 &&
-        CrossProduct(a - c, d - c) * CrossProduct(b - c, d - c) <= 0;
-  }
-
-  /// Is segment (v, v1) in cone (vPrev, v, vNext)?
-  /// @precondition Orientation CCW!!!
-  template <typename PointT> bool IsSegmentInCone(PointT v, PointT v1, PointT vPrev, PointT vNext)
-  {
-    PointT const diff = v1 - v;
-    PointT const edgeL = vPrev - v;
-    PointT const edgeR = vNext - v;
-    double const cpLR = CrossProduct(edgeR, edgeL);
-
-    if (my::AlmostEqualULPs(cpLR,  0.0))
-    {
-      // Points vPrev, v, vNext placed on one line;
-      // use property that polygon has CCW orientation.
-      return CrossProduct(vNext - vPrev, v1 - vPrev) > 0.0;
-    }
-
-    if (cpLR > 0)
-    {
-      // vertex is convex
-      return CrossProduct(diff, edgeR) < 0 && CrossProduct(diff, edgeL) > 0.0;
-    }
-    else
-    {
-      // vertex is reflex
-      return CrossProduct(diff, edgeR) < 0 || CrossProduct(diff, edgeL) > 0.0;
-    }
-  }
-
-  template <typename PointT>
-  int GetOrientation(PointT const & p1, PointT const & p2, PointT const & pt)
-  {
-    double const sa = CrossProduct(p1 - pt, p2 - pt);
-    if (sa > 0.0)
-      return 1;
-    if (sa < 0.0)
-      return -1;
-    return 0;
-  }
-
   template <typename T> string DebugPrint(m2::Point<T> const & p)
   {
     ostringstream out;
diff --git a/geometry/polygon.hpp b/geometry/polygon.hpp
index 6274795c13..57272b29b6 100644
--- a/geometry/polygon.hpp
+++ b/geometry/polygon.hpp
@@ -91,7 +91,7 @@ template <typename IterT> bool IsPolygonCCW(IterT beg, IterT end)
   IterT iNext = NextIterInCycle(iRes, beg, end);
   cp =  m2::robust::OrientedS(*iPrev, *iRes, *iNext);
 
-  ASSERT_NOT_EQUAL ( cp, 0.0, (*iPrev, *iRes, *iNext) );
+  ASSERT_NOT_EQUAL(cp, 0.0, (*iPrev, *iRes, *iNext));
   return (cp > 0.0);
 }
 
@@ -109,7 +109,7 @@ bool IsDiagonalVisible(IterT beg, IterT end, IterT i0, IterT i1)
   if (prev == i1 || next == i1)
     return true;
 
-  if (!m2::IsSegmentInCone(*i0, *i1, *prev, *next))
+  if (!m2::robust::IsSegmentInCone(*i0, *i1, *prev, *next))
     return false;
 
   for (IterT j0 = beg, j1 = PrevIterInCycle(beg, beg, end); j0 != end; j1 = j0++)
diff --git a/geometry/robust_orientation.cpp b/geometry/robust_orientation.cpp
index e7f2e99aad..98987e5096 100644
--- a/geometry/robust_orientation.cpp
+++ b/geometry/robust_orientation.cpp
@@ -38,6 +38,30 @@ namespace m2 { namespace robust
     return orient2d(a, b, c);
   }
 
+  bool IsSegmentInCone(PointD const & v, PointD const & v1,
+                       PointD const & vPrev, PointD const & vNext)
+  {
+    double const cpLR = OrientedS(vPrev, vNext, v);
+
+    if (cpLR == 0.0)
+    {
+      // Points vPrev, v, vNext placed on one line;
+      // use property that polygon has CCW orientation.
+      return OrientedS(vPrev, vNext, v1) > 0.0;
+    }
+
+    if (cpLR < 0)
+    {
+      // vertex is concave
+      return OrientedS(v, vPrev, v1) < 0 && OrientedS(v, vNext, v1) > 0.0;
+    }
+    else
+    {
+      // vertex is convex
+      return OrientedS(v, vPrev, v1) < 0 || OrientedS(v, vNext, v1) > 0.0;
+    }
+  }
+
   bool SegmentsIntersect(PointD const & a, PointD const & b,
                          PointD const & c, PointD const & d)
   {
diff --git a/geometry/robust_orientation.hpp b/geometry/robust_orientation.hpp
index f2fb074c92..e4f81b65db 100644
--- a/geometry/robust_orientation.hpp
+++ b/geometry/robust_orientation.hpp
@@ -9,8 +9,16 @@ namespace m2 { namespace robust
 {
   bool Init();
 
+  /// @return > 0, (p1, p2, p) - is CCW (left oriented)
+  ///         < 0, (p1, p2, p) - is CW (right oriented)
+  /// Same as CrossProduct(p1 - p, p2 - p), but uses robust calculations.
   double OrientedS(PointD const & p1, PointD const & p2, PointD const & p);
 
+  /// Is segment (v, v1) in cone (vPrev, v, vNext)?
+  /// @precondition (vPrev, v, vNext) is CCW.
+  bool IsSegmentInCone(PointD const & v, PointD const & v1,
+                       PointD const & vPrev, PointD const & vNext);
+
   bool SegmentsIntersect(PointD const & p1, PointD const & p2,
                          PointD const & p3, PointD const & p4);
 
diff --git a/geometry/triangle2d.cpp b/geometry/triangle2d.cpp
new file mode 100644
index 0000000000..ba790a084d
--- /dev/null
+++ b/geometry/triangle2d.cpp
@@ -0,0 +1,33 @@
+#include "triangle2d.hpp"
+
+#include "robust_orientation.hpp"
+
+
+namespace m2
+{
+
+using namespace robust;
+
+bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
+                           m2::PointD const & p2, m2::PointD const & p3)
+{
+  double const s1 = OrientedS(p1, p2, pt);
+  double const s2 = OrientedS(p2, p3, pt);
+  double const s3 = OrientedS(p3, p1, pt);
+
+  return ((s1 >= 0.0 && s2 >= 0.0 && s3 >= 0.0) ||
+          (s1 <= 0.0 && s2 <= 0.0 && s3 <= 0.0));
+}
+
+bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
+                                   m2::PointD const & p2, m2::PointD const & p3)
+{
+  double const s1 = OrientedS(p1, p2, pt);
+  double const s2 = OrientedS(p2, p3, pt);
+  double const s3 = OrientedS(p3, p1, pt);
+
+  return ((s1 > 0.0 && s2 > 0.0 && s3 > 0.0) ||
+          (s1 < 0.0 && s2 < 0.0 && s3 < 0.0));
+}
+
+} // namespace m2;
diff --git a/geometry/triangle2d.hpp b/geometry/triangle2d.hpp
index 7cd828b96c..6dbfebde85 100644
--- a/geometry/triangle2d.hpp
+++ b/geometry/triangle2d.hpp
@@ -11,4 +11,14 @@ double GetTriangleArea(Point<T> const & p1, Point<T> const & p2, Point<T> const
   return 0.5 * fabs((p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y));
 }
 
-}
+/// @param[in] pt - Point to check
+/// @param[in] p1, p2, p3 - Triangle
+//@{
+bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
+                           m2::PointD const & p2, m2::PointD const & p3);
+
+bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
+                                   m2::PointD const & p2, m2::PointD const & p3);
+//@}
+
+} // namespace m2