Added bounding area for adding organization

2 files changed, 90 insertions, 0 deletions

diff --git a/geometry/triangle2d.cpp b/geometry/triangle2d.cpp
index 1bd0f56f4c..78e005b0da 100644
--- a/geometry/triangle2d.cpp
+++ b/geometry/triangle2d.cpp
@@ -1,8 +1,14 @@
 #include "triangle2d.hpp"
 
+#include "distance.hpp"
 #include "robust_orientation.hpp"
 #include "segment2d.hpp"
 
+#include "base/math.hpp"
+
+#include "std/chrono.hpp"
+#include "std/random.hpp"
+
 using namespace m2::robust;
 
 namespace m2
@@ -37,4 +43,60 @@ bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
           (s1 < 0.0 && s2 < 0.0 && s3 < 0.0));
 }
 
+bool IsPointInsideTriangles(m2::PointD const & pt, vector<m2::TriangleD> const & v)
+{
+  for (auto const & triangle : v)
+  {
+    if (IsPointInsideTriangle(pt, triangle.p1(), triangle.p2(), triangle.p3()))
+      return true;
+  }
+  return false;
+}
+
+m2::PointD GetRandomPointInsideTriangle(m2::TriangleD const & t)
+{
+  size_t kDistribMax = 1000;
+
+  default_random_engine engine(system_clock::now().time_since_epoch().count());
+  uniform_int_distribution<> distrib(0, kDistribMax);
+  double const r1 = sqrt(static_cast<double>(distrib(engine)) / kDistribMax);
+  double const r2 = static_cast<double>(distrib(engine)) / kDistribMax;
+  return t.m_points[0] * (1.0 - r1) + t.m_points[1] * r1 * (1.0 - r2) + t.m_points[2] * r2 * r1;
+}
+
+m2::PointD GetRandomPointInsideTriangles(vector<m2::TriangleD> const & v)
+{
+  if (v.empty())
+    return m2::PointD();
+
+  default_random_engine engine(system_clock::now().time_since_epoch().count());
+  uniform_int_distribution<> distrib(0, v.size() - 1);
+  return GetRandomPointInsideTriangle(v[distrib(engine)]);
+}
+
+m2::PointD GetNearestPointToTriangles(m2::PointD const & pt, vector<m2::TriangleD> const & v)
+{
+  auto distToLine = m2::DistanceToLineSquare<m2::PointD>();
+  int minT = -1;
+  int minI = -1;
+  double minDist = numeric_limits<double>::max();
+  for (int t = 0; t < static_cast<int>(v.size()); t++)
+  {
+    for (int i = 0; i < 3; i++)
+    {
+      distToLine.SetBounds(v[t].m_points[i], v[t].m_points[(i + 1) % 3]);
+      double const dist = distToLine(pt);
+      if (dist < minDist)
+      {
+        minDist = dist;
+        minT = t;
+        minI = i;
+      }
+    }
+  }
+  auto projectToLine = m2::ProjectionToSection<m2::PointD>();
+  projectToLine.SetBounds(v[minT].m_points[minI], v[minT].m_points[(minI + 1) % 3]);
+  return projectToLine(pt);
+}
+
 } // namespace m2;
diff --git a/geometry/triangle2d.hpp b/geometry/triangle2d.hpp
index 6dbfebde85..aa06cb9079 100644
--- a/geometry/triangle2d.hpp
+++ b/geometry/triangle2d.hpp
@@ -2,15 +2,41 @@
 
 #include "point2d.hpp"
 
+#include "std/vector.hpp"
+
 namespace m2
 {
 
+template <typename T> struct Triangle
+{
+  Point<T> m_points[3];
+
+  Triangle(Point<T> const & p1, Point<T> const & p2, Point<T> const & p3)
+  {
+    m_points[0] = p1;
+    m_points[1] = p2;
+    m_points[2] = p3;
+  }
+
+  Point<T> const & p1() const { return m_points[0]; }
+  Point<T> const & p2() const { return m_points[1]; }
+  Point<T> const & p3() const { return m_points[2]; }
+};
+
+using TriangleF = Triangle<float>;
+using TriangleD = Triangle<double>;
+
 template <class T>
 double GetTriangleArea(Point<T> const & p1, Point<T> const & p2, Point<T> const & p3)
 {
   return 0.5 * fabs((p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y));
 }
 
+m2::PointD GetRandomPointInsideTriangle(m2::TriangleD const & t);
+m2::PointD GetRandomPointInsideTriangles(vector<m2::TriangleD> const & v);
+
+m2::PointD GetNearestPointToTriangles(m2::PointD const & pt, vector<m2::TriangleD> const & v);
+
 /// @param[in] pt - Point to check
 /// @param[in] p1, p2, p3 - Triangle
 //@{
@@ -19,6 +45,8 @@ bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
 
 bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1,
                                    m2::PointD const & p2, m2::PointD const & p3);
+
+bool IsPointInsideTriangles(m2::PointD const & pt, vector<m2::TriangleD> const & v);
 //@}
 
 } // namespace m2