[search] [geometry] Fixed IsPointInsideTriangle() for degenerate triangles.

3 files changed, 91 insertions, 10 deletions

diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index c53293ca49..9f297dacbf 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -17,6 +17,7 @@ SOURCES += \
   region2d/binary_operators.cpp \
   robust_orientation.cpp \
   screenbase.cpp \
+  segment2d.cpp \
   spline.cpp \
   triangle2d.cpp \
 
@@ -43,6 +44,7 @@ HEADERS += \
   region2d/boost_concept.hpp \
   robust_orientation.hpp \
   screenbase.hpp \
+  segment2d.hpp \
   simplification.hpp \
   spline.hpp \
   transformations.hpp \
diff --git a/geometry/geometry_tests/robust_test.cpp b/geometry/geometry_tests/robust_test.cpp
index f0ed0c2e19..d20703361f 100644
--- a/geometry/geometry_tests/robust_test.cpp
+++ b/geometry/geometry_tests/robust_test.cpp
@@ -1,6 +1,7 @@
 #include "testing/testing.hpp"
 
 #include "geometry/robust_orientation.hpp"
+#include "geometry/segment2d.hpp"
 #include "geometry/triangle2d.hpp"
 
 
@@ -8,15 +9,26 @@ using namespace m2::robust;
 
 namespace
 {
-  using P = m2::PointD;
+using P = m2::PointD;
 
-  template <typename IterT> void CheckSelfIntersections(IterT beg, IterT end, bool res)
-  {
-    TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ());
-    using ReverseIterT = reverse_iterator<IterT>;
-    TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ());
-  }
+template <typename IterT>
+void CheckSelfIntersections(IterT beg, IterT end, bool res)
+{
+  TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ());
+  using ReverseIterT = reverse_iterator<IterT>;
+  TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ());
+}
+
+bool InsideSegment(P const & p, P const ps[])
+{
+  return IsPointInsideSegment(p, ps[0], ps[1]);
+}
+
+bool InsideTriangle(P const & p, P const ps[])
+{
+  return IsPointInsideTriangle(p, ps[0], ps[1], ps[2]);
 }
+}  // namespace
 
 UNIT_TEST(OrientedS_Smoke)
 {
@@ -25,6 +37,34 @@ UNIT_TEST(OrientedS_Smoke)
   TEST(OrientedS(arr[2], arr[0], arr[1]) < 0, ());
 }
 
+UNIT_TEST(Segment_Smoke)
+{
+  double constexpr eps = 1.0E-10;
+  {
+    P ps[] = {{0, 0}, {1, 0}};
+    TEST(InsideSegment(ps[0], ps), ());
+    TEST(InsideSegment(ps[1], ps), ());
+    TEST(InsideSegment(P(0.5, 0), ps), ());
+
+    TEST(InsideSegment(P(eps, 0), ps), ());
+    TEST(InsideSegment(P(1.0 - eps, 0), ps), ());
+
+    TEST(!InsideSegment(P(-eps, 0), ps), ());
+    TEST(!InsideSegment(P(1.0 + eps, 0), ps), ());
+    TEST(!InsideSegment(P(eps, eps), ps), ());
+    TEST(!InsideSegment(P(eps, -eps), ps), ());
+  }
+
+  {
+    P ps[] = {{10, 10}, {10, 10}};
+    TEST(InsideSegment(ps[0], ps), ());
+    TEST(InsideSegment(ps[1], ps), ());
+    TEST(!InsideSegment(P(10 - eps, 10), ps), ());
+    TEST(!InsideSegment(P(10 + eps, 10), ps), ());
+    TEST(!InsideSegment(P(0, 0), ps), ());
+  }
+}
+
 UNIT_TEST(Triangle_Smoke)
 {
   P arr[] = {{0, 0}, {0, 3}, {3, 0}};
@@ -42,6 +82,38 @@ UNIT_TEST(Triangle_Smoke)
   TEST(!IsPointInsideTriangle({2, 1 + eps}, arr[0], arr[1], arr[2]), ());
 }
 
+UNIT_TEST(Triangle_PointInsideSegment)
+{
+  double constexpr eps = 1.0E-10;
+
+  P ps[] = {{0, 0}, {0, 1}, {0, 1}};
+  TEST(InsideTriangle(ps[0], ps), ());
+  TEST(InsideTriangle(ps[1], ps), ());
+  TEST(InsideTriangle(ps[2], ps), ());
+  TEST(InsideTriangle(P(0, eps), ps), ());
+  TEST(InsideTriangle(P(0, 1.0 - eps), ps), ());
+
+  TEST(!InsideTriangle(P(0, -eps), ps), ());
+  TEST(!InsideTriangle(P(0, 1.0 + eps), ps), ());
+  TEST(!InsideTriangle(P(-eps, eps), ps), ());
+  TEST(!InsideTriangle(P(eps, eps), ps), ());
+}
+
+UNIT_TEST(Triangle_PointInsidePoint)
+{
+  double constexpr eps = 1.0E-10;
+
+  P ps[] = {{0, 0}, {0, 0}, {0, 0}};
+  TEST(InsideTriangle(ps[0], ps), ());
+  TEST(InsideTriangle(ps[1], ps), ());
+  TEST(InsideTriangle(ps[2], ps), ());
+
+  TEST(!InsideTriangle(P(0, eps), ps), ());
+  TEST(!InsideTriangle(P(0, -eps), ps), ());
+  TEST(!InsideTriangle(P(-eps, eps), ps), ());
+  TEST(!InsideTriangle(P(eps, eps), ps), ());
+}
+
 UNIT_TEST(PolygonSelfIntersections_IntersectSmoke)
 {
   {
diff --git a/geometry/triangle2d.cpp b/geometry/triangle2d.cpp
index ba790a084d..cbecf3a7f4 100644
--- a/geometry/triangle2d.cpp
+++ b/geometry/triangle2d.cpp
@@ -1,13 +1,12 @@
 #include "triangle2d.hpp"
 
 #include "robust_orientation.hpp"
+#include "segment2d.hpp"
 
+using namespace m2::robust;
 
 namespace m2
 {
-
-using namespace robust;
-
 bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
                            m2::PointD const & p2, m2::PointD const & p3)
 {
@@ -15,6 +14,14 @@ bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
   double const s2 = OrientedS(p2, p3, pt);
   double const s3 = OrientedS(p3, p1, pt);
 
+  // In the case of degenerate triangles we need to check that pt lies
+  // on (p1, p2), (p2, p3) or (p3, p1).
+  if (s1 == 0.0 && s2 == 0.0 && s3 == 0.0)
+  {
+    return IsPointInsideSegment(pt, p1, p2) || IsPointInsideSegment(pt, p2, p3) ||
+           IsPointInsideSegment(pt, p3, p1);
+  }
+
   return ((s1 >= 0.0 && s2 >= 0.0 && s3 >= 0.0) ||
           (s1 <= 0.0 && s2 <= 0.0 && s3 <= 0.0));
 }