Finding and writing exit nodes

2 files changed, 59 insertions, 0 deletions

diff --git a/geometry/geometry_tests/region_test.cpp b/geometry/geometry_tests/region_test.cpp
index c075a8838a..d35570a92f 100644
--- a/geometry/geometry_tests/region_test.cpp
+++ b/geometry/geometry_tests/region_test.cpp
@@ -193,3 +193,22 @@ UNIT_TEST(Region_ForEachPoint)
 
   TEST_EQUAL(res, P(11.5, 14.5), ());
 }
+
+UNIT_TEST(Region_point_at_border_test)
+{
+  typedef m2::PointF P;
+  P const points[] = { P(0.0, 1.0), P(0.0, 10.0), P(10.0, 10.0), P(10.0, 1.0) };
+  m2::Region<P> region(points, points + ARRAY_SIZE(points));
+
+  P p1(0, 0);
+  P p2(5.0, 5.0);
+  P p3(0.0, 1.0);
+  P p4(5.0, 1.0);
+  P p5(5.0, 1.01);
+
+  TEST(!region.atBorder(p1, 0.01), ("Point lies outside border"));
+  TEST(!region.atBorder(p2, 0.01), ("Point lies inside but not at border"));
+  TEST(region.atBorder(p3, 0.01), ("Point has same point with border"));
+  TEST(region.atBorder(p4, 0.01), ("Point lies at border"));
+  TEST(region.atBorder(p5, 0.01), ("Point lies at delta interval near border"));
+}
diff --git a/geometry/region2d.hpp b/geometry/region2d.hpp
index 3c60874b66..94931d7c4d 100644
--- a/geometry/region2d.hpp
+++ b/geometry/region2d.hpp
@@ -2,6 +2,7 @@
 
 #include "point2d.hpp"
 #include "rect2d.hpp"
+#include "distance.hpp"
 
 #include "../std/vector.hpp"
 #include "../std/algorithm.hpp"
@@ -192,6 +193,45 @@ namespace m2
       return Contains(pt, typename TraitsT::EqualType());
     }
 
+    /// Slow point at border realisation
+    template <class EqualF>
+    bool atBorder(PointT const & pt, double const delta, EqualF equalF) const
+    {
+      if (!m_rect.IsPointInside(pt))
+        return false;
+
+      const double squareDelta = delta*delta;
+
+      size_t const numPoints = m_points.size();
+
+      typedef typename TraitsT::BigType BigCoordT;
+      typedef Point<BigCoordT> BigPointT;
+
+      PointT prev = m_points[numPoints - 1];
+      DistanceToLineSquare<PointT> distance;
+      for (size_t i = 0; i < numPoints; ++i)
+      {
+        PointT const curr = m_points[i];
+
+        // Borders often has same points with ways
+        if (equalF.EqualPoints(m_points[i], pt))
+          return true;
+
+        distance.SetBounds(prev, curr);
+        if (distance(pt) < squareDelta)
+          return true;
+
+        prev = curr;
+      }
+
+        return false; // outside
+    }
+
+    bool atBorder(PointT const & pt, double const delta) const
+    {
+      return atBorder(pt, delta, typename TraitsT::EqualType());
+    }
+
   private:
     void CalcLimitRect()
     {